ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 56

2020

Вып. 2

УДК 621.391.1 : 519.72

А. Макур, Л. Чжэн

СРАВНЕНИЕ КОЭФФИЦИЕНТОВ СЖАТИЯ ДЛЯ f-ДИВЕРГЕНЦИЙ1,2

Коэффициенты сжатия - это зависящие от распределений константы, ис-

пользующиеся для улучшения стандартных неравенств об обработке данных

для f-дивергенций (или относительных f-энтропий) и приводящие к так назы-

ваемым “сильным” неравенствам об обработке данных. Для любого двумерного

совместного распределения, т.е. пары, состоящей из вектора вероятностей и сто-

хастической матрицы, известно, что коэффициенты сжатия для f-дивергенций

ограничены сверху единицей, а снизу - коэффициентом сжатия для χ²-дивер-

генции. Мы показываем, что верхняя граница достигается, когда совместное

распределение разложимо, а нижней можно достичь, устремляя f-дивергенции

на входе для коэффициентов сжатия к нулю. Затем устанавливается линей-

ная верхняя граница на коэффициенты сжатия совместных распределений для

некоторого класса f-дивергенций через коэффициенты сжатия для χ²-дивер-

генции, причем эта граница уточняется для выделенного специального случая

дивергенции Кульбака- Лейблера (КЛ-дивергенции). Далее дается альтерна-

тивное доказательство того факта, что коэффициенты сжатия для КЛ- и χ²-ди-

вергенций совпадают для двумерных гауссовских распределений (где для пер-

вого коэффициента может налагаться ограничение на второй момент). Наконец,

обобщается известный результат о том, что коэффициенты сжатия для стоха-

стических матриц (после вычисления экстремума по всевозможным векторам

вероятностей) для всех нелинейных операторно выпуклых f-дивергенций рав-

ны. В частности, доказывается, что так называемый предпорядок “меньшего

искажения” на стохастических матрицах эквивалентным образом характеризу-

ется любой нелинейной операторно выпуклой f-дивергенцией. Как приложение

этой характеризации, выводится также обобщение сильного неравенства Само-

родницкого об обработке данных.

Ключевые слова: коэффициент сжатия, f-дивергенция/относительная f-энтро-

пия, сильное неравенство об обработке данных, предпорядок меньшего искаже-

ния, максимальная корреляция.

DOI: 10.31857/S0555292320020011

§ 1. Введение

Коэффициенты сжатия для f-дивергенций (или относительных f-энтропий) ши-

роко изучались в теории информации [1-8], статистике [9-13], анализе цепей Марко-

ва в теории вероятностей [14-16], а также в теории матриц [17-19], причем особен-

но важными частными случаями являются расстояние по вариации, дивергенция

Кульбака - Лейблера (КЛ-дивергенция) и взаимная информация, а также χ²-дивер-

генция. Как будет показано на примерах, эти коэффициенты - зависящие от распре-

¹ Работа выполнена при финансовой поддержке фонда NSF (грант 1216476) и стипендии компа-

нии Хьюлетт-Паккард.

² Весьма предварительная версия настоящей статьи была представлена в докладе [1].

делений константы, использующиеся для улучшения обычных неравенств об обра-

ботке данных для f-дивергенций и приводящие к так называемым “сильным” нера-

венствам об обработке данных. Коэффициенты сжатия для f-дивергенций бывают

двух типов: относящиеся к парам из вектора вероятностей и стохастической матри-

цы, т.е. совместным распределениям, и относящиеся только к стохастическим мат-

рицам, т.е. условным распределениям. Цель настоящей статьи в широком смысле -

изучить различные неравенства и равенства между коэффициентами сжатия в обеих

постановках. В постановке, связанной с совместными распределениями, мы главным

образом устанавливаем общие границы на коэффициенты сжатия для определенных

классов f-дивергенций, а также выводим специфические границы на коэффициен-

ты сжатия для КЛ-дивергенции через коэффициенты сжатия для χ²-дивергенции

(или квадрата максимальной корреляции Хиршфельда - Гебелейна - Реньи). С дру-

гой стороны, в постановке, связанной со стохастическими матрицами, мы обобщаем

известную эквивалентность некоторых определенных коэффициентов сжатия, до-

казывая эквивалентность характеризации предпорядка “меньшего искажения” (less

noisy preorder) на стохастических матрицах [20].

Более точно, настоящая статья включают в себя следующее:

Полностью независимый обзор результатов о коэффициентах сжатия в § 2 (в ко-

тором мы в основном рассматриваем свойства коэффициентов сжатия, а не их

применения).

Обобщения известных свойств коэффициентов сжатия для совместных распре-

делений, такие как результат о разложимости в теореме 1 (или в п. 3 предложе-

ния 3), мета-сильное неравенство об обработке данных в п. 6 предложения 3 и

характеризация коэффициента сжатия для χ²-дивергенции через коэффициен-

ты сжатия для f-дивергенций при стремлении f-дивергенции на входе к нулю

в теореме 2 (что явно объясняет интуитивное понимание нижней границы на

максимальную корреляцию в п. 7 предложения 3).

Зависящие от распределений нижние границы на КЛ-дивергенцию и некоторые

классы f-дивергенций через χ²-дивергенцию в леммах 2 и 5 соответственно (эти

границы используются для доказательства дальнейших линейных верхних гра-

ниц на коэффициенты сжатия).

Линейные верхние границы на коэффициенты сжатия совместных распределе-

ний для КЛ-дивергенции и некоторые классы f-дивергенций через коэффициент

сжатия для χ²-дивергенции в теоремах 3, 4 и следствии 1.

Альтернативное доказательство известной эквивалентности между коэффициен-

тами сжатия для КЛ- и χ²-дивергенций двумерных гауссовских распределений

в §5, которое также устанавливает эквивалентность при дополнительном огра-

ничении на среднюю мощность (или второй момент) - см. теорему 5.

Эквивалентные характеризации предпорядка меньшего искажения на стохасти-

ческих матрицах через нелинейные операторно выпуклые f-дивергенции в тео-

реме 6. Эта теорема обобщает известный из литературы важный результат о том,

что коэффициенты сжатия для всех нелинейных операторно выпуклых f-дивер-

генций для заданной стохастической матрицы равны (см. предложение 6).

Применения наших основных результатов, такие как обобщение сильного нера-

венства Самородницкого об обработке данных на нелинейную операторно вы-

пуклую f-информацию в теореме 7, а также простое доказательство в предло-

жении 7 того факта, что скорость сходимости к стационарному состоянию для

КЛ-дивергенции определяется коэффициентом сжатия для χ²-дивергенции для

эргодической обратимой цепи Маркова.

Структура статьи. Кратко обрисуем дальнейшее изложение. Вначале в § 2 при-

веден обзор все разрастающейся литературы по коэффициентам сжатия. В этом па-

раграфе собраны формальные определения и важнейшие свойства обоих вышеупо-

мянутых вариантов коэффициентов сжатия, а также вкратце описано их появление

в изучении эргодичности. Затем в § 3 сформулированы и пояснены наши основные

результаты и рассмотрена относящаяся к этому литература. В § 4 представлены

некоторые полезные границы, связывающие f-дивергенции и χ²-дивергенцию, ко-

торые будут использованы для вывода линейных верхних границ на коэффициенты

сжатия совместных распределений для некоторого класса f-дивергенций и КЛ-ди-

вергенции. В продолжение этого сюжета в § 5 доказана эквивалентность некоторых

коэффициентов сжатия двумерных гауссовских распределений. В § 6 доказывает-

ся эквивалентность характеризаций предпорядка меньшего искажения на стохасти-

ческих матрицах через нелинейные операторно выпуклые f-дивергенции, а затем

выводится обобщение сильного неравенства Самородницкого об обработке данных.

Наконец, в § 7 даются заключительные замечания и намечаются направления даль-

нейших исследований.

§2. Обзор результатов по коэффициентам сжатия

Здесь мы определим коэффициенты сжатия для f-дивергенций и изложим неко-

торые известные факты о них. Вначале в п. 2.1 вводятся предварительные опре-

деления и обозначения, относящиеся к f-дивергенциям, а в последующих пунктах

вкратце изложим первые необходимые сведения о коэффициентах сжатия и сильных

неравенствах об обработке данных.

2.1. f-дивергенция. Рассмотрим дискретное пространство элементарных собы-

тий X ≜ {1, . . . , |X |} мощности 2 ≤ |X | < +∞, элементы которого будем без огра-

(

ничения общности считать натуральными числами. Через P_X ⊆

R^|X|)∗ обозначим

(

вероятностный симплекс в

R^|X|)∗, состоящий из всех вероятностных мер на X , где

(

R^|X|)∗ - двойственное к R|X | векторное пространство, состоящее из всех векторов-

строк длины |X |. Мы понимаем P_X как множество всевозможных распределений

случайной величины X со значениями X , и будем представлять каждую вероят-

ностную меру P_X ∈ P_X в виде вектора-строки

(

P_X = (P_X(1), . . . , P_X(|X|)) ∈

R^|X|)∗.

Через

P^◦X ≜ {P_X ∈ P_X : ∀x ∈ X, P_X(x) > 0}

обозначим относительную внутренность множества P_X . Популярным “расстоянием”

между вероятностными мерами в теории информации и статистике является по-

нятие f-дивергенции, независимо введенное в [21, 22] и в [23]. (Это понятие также

независимо появлялось в [24], [25] и [26, 27].)

Определение 1 (f-дивергенция [21-23]). Для заданной выпуклой функции

f : (0,∞) → R, такой что f(1) = 0, f-дивергенцией вероятностной меры P_X ∈ P_X

относительно вероятностной меры R_X ∈ P_X называется величина

[

∑

⁽R_X(x)⁾

⁽R_X(X)^)]

D_f (R_X ∥P_X) ≜

P_X(x)f

=EPX f

(1)

P_X(x)

P_X(X)

x∈X

где через EPX [ · ] обозначено математическое ожидание относительно P_X и в силу

непрерывности и некоторых других соображений (подробнее см. в [28, § 3]) приня-

ты соглашения f(0) = lim f(t) (в том числе, возможно, равный бесконечности),

t→0⁺

0f(0/0) = 0 и 0f(r/0) = lim

pf(r/p) = r lim pf(1/p) для всех r > 0 (этот предел

p→0⁺

также может быть равен бесконечности).

Понятие f-дивергенции обобщает несколько известных мер расхождения (дивер-

генции), используемых в теории информации, статистике и теории вероятностей.

Приведем несколько примеров:

Расстояние по вариации: Для f(t) =

|t - 1| соответствующая f-дивергенция

является расстоянием по вариации (total variation (TV) distance):

∥R_X - P_X∥_TV ≜ max|RX (A) - PX (A)| =

∥R_X - P_X∥₁ ,

(2)

A⊆X

∑

где P_X (A) =

P_X(x) для любой A ⊆ X, через ∥·∥_p обозначена ℓ^p-норма,

x∈A

p ∈ [1,∞], причем второе равенство, как и некоторые другие характеризации

расстояния по вариации, доказано в [29, гл. 4].

Дивергенция Кульбака - Лейблера (КЛ-дивергенция)[30, § 2]: Для функции f(t) =

= tlog(t), где log(·) здесь и далее - натуральный логарифм (по основанию e), со-

ответствующая f-дивергенция является КЛ-дивергенцией (или относительной

энтропией):

∑

⁽R_X(x)⁾

D(R_X ∥ P_X ) ≜

R_X(x)log

(3)

P_X(x)

x∈X

χ²-дивергенция (Неймана) [31]: Для f(t) = (t -1)² или f(t) = t² - 1 соответству-

ющая f-дивергенция является χ²-дивергенцией:

∑

(R_X (x) - P_X (x))²

χ²(R_X ∥P_X) ≜

(4)

P_X(x)

x∈X

Существуют и другие варианты χ²-дивергенции - см., например, [32], где описа-

ны варианты Пирсона и Вайды, а также их связь с f-дивергенциями.

Дивергенция Хеллингера порядка α ∈ (0, ∞) \ {1} [33, определение 2.10]: Для

t^α - 1

f (t) =

соответствующая f-дивергенция является дивергенцией Хеллинге-

α-1

ра (или дивергенцией Цаллиса) порядка α:

)

(∑

H_α(R_X ∥P_X) ≜

R_X(x)^αP_X(x)1-α - 1 ,

(5)

α-1

x∈X

где

H1(R_X ∥P_X) - квадрат расстояния Хеллингера,H₂(R_X ∥P_X) = χ²(R_X ∥P_X)

– это χ²-дивергенция, а случай α = 1 в смысле аналитического продолжения

соответствует КЛ-дивергенции H₁(R_X ∥P_X) = D(R_X ∥P_X) (см. [34, § II]).

Дивергенция Винце - Ле Кама порядка λ ∈ (0, 1) [35-37]: для функции f(t) =

(t - 1)

= λ(1-λ)

соответствующая f-дивергенция - это дивергенция Винце -

λt + (1 - λ)

Ле Кама порядка λ:

∑

(R_X (x) - P_X (x))²

LC_λ(R_X ∥P_X) ≜ λ(1 - λ)

λR_X (x) + (1 - λ)P_X (x)

x∈X

)

( λ

χ²(R_X ∥λR_X + (1 - λ)P_X),

(6)

1-λ

где частный случай при λ =

известен как расстояние Винце -Ле Кама (или

triangular discrimination).

Хотя в общем случае f-дивергенции не являются метриками³, они обладают

несколькими полезными свойствами. Для изложения некоторых из эти свойств обо-

значим через Y ≜ {1, . . . , |Y|} другой дискретный алфавит, где 2 ≤ |Y| < +∞,

и введем соответствующий вероятностный симплекс P_Y возможных вероятностных

мер для случайной величины Y со значениями в Y. Кроме того, пусть P_Y|X - множе-

ство всех |X|×|Y| стохастических по строкам матриц в пространстве R^|X|×|Y|. Всюду

далее мы отождествляем условное распределение Y при заданном X (или “дискрет-

ный канал”) P_Y|X со стохастической по строкам матрицей вероятностей перехода

W ∈ P_Y|X (т.е. PY |X = W), где x-й строкой матрицы W для любого x ∈ X является

условная вероятностная мера PY|X=x ∈ P_Y . Мы интерпретируем W : P_X → P_Y как

отображение, переводящее вероятностные меры P_X ∈ P_X на входе в вероятност-

ные меры P_Y = P_X W ∈ P_Y на выходе путем умножения слева. Ниже перечислены

некоторые хорошо известные свойства f-дивергенций (см. [21, 22]):

1. Неотрицательность и рефлексивность: Для любых R_X, P_X ∈ P_X справедливо

D_f (R_X ∥P_X) ≥ 0 (согласно неравенству Йенсена), причем при R_X = P_X име-

ет место равенство. Кроме того, если f строго выпукла в единице, т.е. λf(x) +

+ (1 - λ)f(y) > f(1) для всех x, y ∈ (0, ∞) и λ ∈ (0, 1), таких что λx+ (1 - λ)y = 1,

то равенство имеет место тогда и только тогда, когда R_X = P_X. (Заметим, что

во всех приведенных выше примерах f-дивергенции функция f строго выпукла

в единице.)

2. Аффинная инвариантность: Рассмотрим любую аффинную функцию α(t) =

= a(t - 1), где a ∈ R. Ясно, что D_α(R_X ∥P_X) = 0 для любых R_X, P_X ∈ P_X . Сле-

довательно, f и f + α задают одну и ту же f-дивергенцию, т.е. Df+α(R_X ∥ P_X ) =

= D_f(R_X ∥P_X) для любых R_X,P_X ∈ P_X (где f + α определяется поточечным

сложением).

3. Двойственность Чисара: Для функции f рассмотрим ее сопряженную по Чисару

функцию

)

⁽1

f^∗ : (0, ∞) → R, f^∗(t) = tf

которая также выпукла, строго выпукла в единице тогда и только тогда, ко-

гда f строго выпукла в единице, и удовлетворяет равенству f^∗∗ = f. Тогда

D_f∗(P_X ∥R_X) = D_f (R_X ∥P_X) для любых R_X, P_X ∈ P_X .

4. Совместная выпуклость: Отображение (R_X, P_X) → D_f (R_X ∥P_X) выпукло по

паре вероятностных мер на входе.

5. Неравенство об обработке данных (см. [23,24]): Для любой W ∈ P_Y|X и любых

R_X, P_X ∈ P_X справедливо (в силу выпуклости соответствующих функций)

D_f (R_XW ∥P_XW) ≤ D_f (R_X ∥P_X),

(7)

где равенство имеет место, если Y является достаточной статистикой для X,

позволяющей делать выводы о паре (R_X , P_X ) (см. [28, определение 5]). Кроме

того, если f строго выпукла и D_f (R_X ∥P_X) < ∞, то равенство имеет место тогда

и только тогда, когда Y - достаточная статистика для X, позволяющая делать

выводы о паре (R_X , P_X ) (см., например, [28, теорема 14; 38, п. 3.1]).

Хотя в [22] и [39, § 2] представлено оригинальное изложение этих свойств, боль-

шей дидактикой обладает изложение в [38, § 6]. Заметим, что в силу свойства 2 мы

рассматриваем f-дивергенции только для нелинейных функций f.

Теперь определим понятие “информации” между случайными величинами, со-

ответствующее произвольной f-дивергенции, для которой также справедливо нера-

³ Мы зачастую выделяем f-дивергенции, являющиеся метриками, называя их “расстояниями”

(например, расстояние по вариации, расстояние Хеллингера) и оставляя термин “дивергенция” для

тех f-дивергенций, которые метриками не являются (например, КЛ-дивергенция, χ²-дивергенция).

венство об обработке данных. Для случайных величин X и Y с совместной вероят-

ностной мерой P_X,Y , состоящей из (P_X , W ), взаимная f-информация между X и Y

определяется [19] (см. также [8, формула (V.8); 40, формула (11)]) как

∑

If (X; Y ) ≜ Df (PX,Y ∥ PX PY ) =

P_X(x)D_f (PY|X=x ∥P_Y ),

(8)

x∈X

где через P_X P_Y обозначено произведение распределений, определяемых маргиналь-

ными вероятностными мерами P_X и P_Y , и при этом используется соглашение, что

P_X(x)D_f (PY|X=x ∥P_Y ) = 0, если P_X(x) = 0. Для f(t) = t log(t) взаимная f-информа-

ция соответствует стандартной взаимной информации (в смысле определения Фано,

см. [41, п. 2.3; 38, п. 2.3]):

I(X; Y ) ≜ D(P_X,Y ∥ P_X P_Y ).

Более того, взаимная f-информация обладает некоторыми естественными свойства-

ми информационных мер. Например, если X и Y независимы, то I_f (X; Y ) = 0, и

верно обратное, если f строго выпукла в единице.

Пусть теперь U - еще одна случайная величина с дискретным алфавитом U ≜

≜ {1, . . ., |U|}, такая что 2 ≤ |U| < +∞. Если (U, X, Y ) имеют совместное распреде-

ление и образуют цепь Маркова U → X → Y , т.е. U условно независима от Y при

заданном X, то они удовлетворяют неравенству об обработке данных [39]

If (U; Y ) ≤ If (U; X),

(9)

где равенство имеет место, если Y - достаточная статистика для X, позволяющая

делать выводы об U (т.е. U → Y → X также образуют цепь Маркова). Более того,

если f строго выпукла и I_f (U; X) < ∞, то равенство имеет место тогда и только

тогда, когда Y - достаточная статистика для X, позволяющая делать выводы об

U. Заметим, что хотя Чисар в [39] изучал несколько другое понятие, известное как

f-информативность, соотношение (9) можно извлечь из доказательства предложе-

ния 2.1 в [39].

Не стоит и говорить, что неравенства об обработке данных (7) и (9) являются

обобщениями более известных неравенств об обработке данных для КЛ-диверген-

ции и взаимной информации (см., например, [30, теорема 4.1; 41]). Наконец, заметим,

что хотя по поводу неравенств об обработке данных (7) и (9) мы ссылаемся на рабо-

ты [21-24] и [39], соответственно, оба этих неравенства были независимо доказаны

в [26,27]. В частности, в [27] изучались обобщенные информационные функционалы,

и частный случай из [27, теорема 5.1] дает D_f (P_U P_Y ∥ P_U,Y ) ≤ D_f (P_U P_X ∥ P_U,X ) для

любой цепи Маркова U → X → Y . По двойственности Чисара для f-дивергенций

отсюда вытекает (9).

В заключение этого пункта вкратце опишем “локально квадратичное поведение”

f-дивергенций. Локальные аппроксимации f-дивергенций важны с геометрической

точки зрения, поскольку они преобразуют окрестности стохастических многообра-

зий с определенными f-дивергенциями в качестве метрики в пространства со ска-

лярным произведением, где метрика задается информацией Фишера - Рао [42-44].

Рассмотрим некоторую выделенную вероятностную меру P_X

∈ P^◦X (задающую

“центр локальной окрестности” рассматриваемых вероятностных мер) и любую дру-

гую вероятностную меру R_X ∈ P_X . Определим вектор сферического возмущения

меры R_X относительно P_X :

(√

K_X ≜ (R_X - P_X)diag

P_X

)-1,

(10)

где

√· означает поэлементное извлечение квадратного корня из компонент векто-

ра, а через diag(·) обозначена диагональная матрица с соответствующими компо-

нентами вектора на главной диагонали. С помощью вектора K_X можно построить

траекторию сферически возмущенных вероятностных мер:

(√

)

R(ε)X = P_X + εK_X diag

P_X

(11)

= (1 - ε)P_X + εR_X ,

(12)

параметризованную параметром ε ∈ (0, 1), которая соответствует выпуклым ком-

бинациям R_X и P_X . Заметим, что K_X задает направление траектории (11), а па-

раметр ε контролирует близость между R(ε)X и P_X . Равенство (11) объясняет, поче-

му K_X называется вектором “сферического возмущения”; вектор K_X пропорциона-

√

(ε)

лен члену первого порядка по ε → 0 возмущения между векторами

√P_X,

являющимися вложениями вероятностных мер R(ε)X и P_X в единичную сферу в про-

(

странстве

R^|X|)∗.

Теперь предположим, что функция f : (0, ∞) → R, задающая рассматриваемую

f-дивергенцию, дважды дифференцируема в единице и f^′′(1) > 0. Тогда с помощью

формулы Тэйлора можно показать, что эта f-дивергенция локально пропорциональ-

на χ²-дивергенции (см. [45, § 4], или [41] для случая КЛ-дивергенции):

(

)

f^′′(1)

D_f

R(ε)X ∥P_X

ε²χ²(R_X ∥P_X) + o(ε²) =

(13)

f^′′(1)

ε² ∥K_X∥²² + o(ε²),

(14)

где используется стандартная o-символика Бахмана - Ландау. Локальная аппрокси-

мация в (14) несколько более удобна, чем в (13). Действительно, можно построить

(

траекторию (11) с помощью сферического вектора возмущения K_X ∈

R^|X|)∗, ко-

торый удовлетворяет условию ортогональности

√P_X K^TX = 0, но не имеет вид (10).

Для достаточно малого ε = 0 (зависящего от P_X и K_X ), векторы R(ε)X, определен-

ные в (11), на самом деле являются вероятностными мерами в P_X .⁴ Таким обра-

зом, аппроксимация в (14) оставется верной, поскольку она относится к режиму,

когда ε → 0.

Непосредственной проверкой можно также убедиться, что f-дивергенции, для

которых f^′′(1) > 0, локально симметричны, т.е.

(

)

(

)

D_f

R(ε)X ∥P_X

=D_f

P_X ∥R(ε)X

+ o(ε²).

Поэтому они напоминают стандартную евклидову метрику в “окрестности” вероят-

ностных мер вокруг заданной вероятностной меры в P^◦X . Отметим, что преимуще-

ство использования сферических возмущений

{

}

(

√

K_X ∈

R^|X|)∗ :

P_XK^TX = 0

вместо аддитивных возмущений (например, R_X -P_X ) состоит в том, что они образу-

ют пространство со стандартным евклидовым скалярным произведением. Это позво-

ляет видоизменить (13) с использо(√ние) ℓ2-нормы KX вместо взвешенной ℓ2-нормы

аддитивного возмущения K_X diag

P_X

. Это позволяет сделать обозначения более

удобными и упростить вычисления - см. наше доказательство теоремы 2. Наконец,

заметим, что идеи возмущения, подобные (11), использовались ранее в различных

контекстах, некоторые примеры этого можно найти в [42, 43, 46, 47].

⁴ Хотя компоненты вектора R(ε)X в сумме всегда равны 1, поскольку√P_XK^TX = 0, для больших

(по абсолютной величине) значений ε некоторые из его компонент могут быть отрицательными.

2.2. Коэффициенты сжатия совместных распределений. Неравенства об обработ-

ке данных (7) и (9) можно максимально усилить до так называемых сильных нера-

венствах об обработке данных (СНОД), вводя в них некоторые константы, извест-

ные как коэффициенты сжатия. Как было отмечено выше, имеется два варианта

коэффициентов сжатия: первый зависит от пары, состоящей из вектора вероятно-

стей и стохастической матрицы, т.е. совместного распределения, а второй - только

от стохастической матрицы, т.е. условного распределения. В этом пункте мы введем

коэффициенты первого типа, а коэффициенты второго типа обсудим позже.

Определение 2 (коэффициент сжатия для совместного распределения [1,6,8,

11,15]). Для любой вероятностной меры на входе P_X ∈ P_X и любой стохастической

матрицы P_Y|X = W ∈ P_Y|X коэффициентом сжатия для фиксированной f-дивер-

генции называется

D_f (R_XW ∥P_XW)

η_f (P_X, P_Y|X) ≜

sup

D_f (R_X ∥P_X)

RX∈PX

0<D_f (RX ∥PX )<+∞

где супремум берется по всем вероятностным мерам R_X , удовлетворяющим ограни-

чению 0 < D_f (R_X ∥ P_X ) < +∞. При этом, если X или Y постоянна почти наверное

(п.н.), полагаем η_f (P_X , P_Y|X ) = 0.

Используя определение 2, из неравенства об обработке данных для f-диверген-

ций (7) можно вывести следующее СНОД:

D_f (R_XW ∥P_XW) ≤ η_f (P_X, P_Y|X)D_f (R_X ∥P_X),

(15)

справедливое для всех R_X ∈ P_X при фиксированных P_X ∈ P_X и W ∈ P_Y|X . Следу-

ющее предложение показывает, что неравенство об обработке данных для взаимной

f-информации можно улучшить таким же образом.

Предложение 1 (коэффициент сжатия для взаимной f-информации [8, тео-

рема V.2]). Для любой вероятностной меры на входе PX ∈ PX, любой стоха-

стической матрицы P_Y|X ∈ P_Y|X и любой выпуклой дифференцируемой функции

f : (0,∞) → R с равномерно ограниченной производной в некоторой окрестности

единицы, такой что f(1) = 0, имеет место равенство

If (U; Y )

η_f (P_X, P_Y|X) =

sup

P_U|X : U→X→Y

If (U; X)

0<I_f (U;X)<+∞

где супремум берется по всем стохастическим матрицам P_U|X ∈ P_U|X и конеч-

ным алфавитам U случайной величины U, таким что U → X → Y образуют

цепь Маркова. (Заметим, что в этой экстремальной задаче достаточно взять

|U| = 2.)

Предложение 1 доказано в [8, теорема V.2]. Частный случай этого результата

для КЛ-дивергенции был доказан в [4] (для случая конечного алфавита) и в [6]

(для произвольного алфавита). Интуитивно вариационная задача в предложении 1

определяет вероятностную модель, которая делает Y как можно более близкой к до-

статочной статистике для X относительно U (см. комментарий после формулы (9)).

Кроме того, этот результат показывает, что при условиях регулярности коэффици-

ент сжатия для любой f-дивергенции изящным образом объединяет неравенства об

обработке данных для f-дивергенции и соответствующей взаимной f-информации,

будучи наилучшим множителем, который можно добавить в каждое из них. Дей-

ствительно, когда случайные величины U → X → Y образуют цепь Маркова, можно

записать СНОД-версию неравенства (9):

If (U; Y ) ≤ ηf (PX , PY |X )If (U; X),

(16)

справедливую для любого условного распределения P_U|X ∈ P_U|X при фиксирован-

ных P_X ∈ P_X и P_Y|X ∈ P_Y|X . Заметим, что даже если условия предложения 1 не

выполнены, неравенство (16) по-прежнему справедливо (хотя η_f (P_X , P_Y|X ) может

уже не быть наилучшей возможной мультипликативной константой в (9)).

Два коэффициента сжатия будут особенно важны для нас. Первый - это коэф-

фициент сжатия для КЛ-дивергенции:

D(R_X W ∥ P_X W )

η_KL(P_X, P_Y|X) =

sup

(17)

D(R_X ∥ P_X )

RX∈PX

0<D(RX ∥PX)<+∞

Эта величина связана с фундаментальным понятием гиперсжимаемости в тео-

рии вероятностей и статистике [15]. Гиперсжимаемостью называется явление, когда

некоторые операторы условного математического ожидания являются сжимаемы-

ми, даже если функциональное пространство входов имеет (вероятностную) L^q-нор-

му, в то время как функциональное пространство выходов имеет (вероятностную)

L^p-норму, где 1 ≤ q < p (см., например, [5]). Это понятие находит применения

в теории информации, поскольку гиперсжимаемые величины часто обладают свой-

ствами тензоризации, что позволяет получать однобуквенные характеризации для

них. В [5, 15] показано, что величину η_KL(P_X , P_Y|X ) можно определить как наклон

секущей нижней границы области гиперсжимаемости (соответствующей совместной

вероятностной мере P_X,Y ) на бесконечности.

Коэффициент сжатия для КЛ-дивергенции объясняет поразительную дихото-

мию между экстремальными задачами в определении 2 и предложении 1. Чтобы

пояснить этот контраст, вначале рассмотрим частный случай предложения 1 для

КЛ-дивергенции и стандартной взаимной информации [4,6]:

I(U; Y )

η_KL(P_X, P_Y|X) =

sup

(18)

PU ,PX |U : U→X→Y

I(U; X)

I(U;X)>0

где оптимизация проводится (что эквивалентно) по всем P_U ∈ P_U , таким что U =

= {0, 1} (без ограничения общности, см. [6, Приложение B]), и всем P_X|U ∈ P_X|U ,

таким что для маргинальных распределений P_X = P_U P_X|U . Теперь напомним при-

мер из работы [4], где U = {0, 1}, X ∼ Bernoulli(1/2) (т.е. P_X = (1/2, 1/2)), а P_Y|X -

матрица “асимметричного канала со стиранием”. В этом численном примере супре-

{

мум в (18) достигается на последовательностях вероятностных мер

P(k)X|U=0 ∈ P_X :

}

{

}

{

}

k ∈ N

P(k)X|U=1 ∈ P_X : k ∈ N

P(k)U ∈ P_U : k ∈ N

, где N ≜ {0, 1, 2, . . .},

удовлетворяющим условиям

lim

P(k)U(1) = 0,

(19)

k→∞

(

)

(

)

lim

P(k)X|U=0 ∥P_X

= 0 < liminf

P(k)X|U=1 ∥P_X

(20)

k→∞

(

)

(

)

P(k)

∥P_Y

P(k)

∥P_Y

Y |U=0

Y |U=1

lim sup

(

) < η_KL(PX,PY |X) = lim

(

(21)

k→∞ D

P(k)X|U=0 ∥P_X

^k→∞ D

P(k)

∥P_X

X|U=1

где P_Y = P_X P_Y|X и P(k)Y|U=u = P(k)X|U=uP_Y|X для u ∈ U. Этот пример показывает, что

в общем случае, хотя максимум в (18) достигается [2] при I(U; X) → 0, супремум

в (17) часто достигается на последовательности вероятностных мер

{

}

R(k)X ∈ P_X \ {P_X} : k ∈ N

которая не стремится к P_X (из-за невыпуклости этой экстремальной задачи). На

первый взгляд, это противоречит интуиции, поскольку неравенство об обработке

данных (7) обращается в равенство при R_X = P_X . Однако в теореме 2 (приведенной

в п. 3.1) будет показано, что максимизация отношения КЛ-дивергенций с ограниче-

нием D(R_X ∥ P_X ) → 0 на самом деле позволяет достичь η_χ2(P_X , P_Y|X ), что зачастую

строго меньше [4], чем η_KL(P_X, P_Y|X). Поэтому имеется резкий контраст между по-

ведением оптимизационных задач в (17) и (18).

Второй важный коэффициент сжатия - это коэффициент сжатия для χ²-дивер-

генции:

χ²(R_XW ∥P_XW)

η_χ2 (P_X, P_Y|X) =

sup

(22)

RX∈PX

χ²(R_X ∥P_X)

0<χ²(RX ∥PX )<+∞

тесно связанный с обобщением коэффициента корреляции Пирсона между X и Y ,

известным как максимальная корреляция Хиршфельда - Гебелейна - Реньи, или про-

сто максимальная корреляция [9-12]. Дадим определение максимальной корреля-

ции, которая является мерой статистической зависимости, удовлетворяющей семи

естественным аксиомам (некоторые из них будут приведены ниже в предложении 3),

которым должны удовлетворять такие меры [12].

Определение 3 (максимальная корреляция [9-12]). Для двух совместно рас-

пределенных случайных величин X ∈ X и Y ∈ Y максимальной корреляцией между

X и Y называется

ρ(X; Y ) ≜

sup

E[f(X)g(Y )],

f : X→R, g: Y→R

E[f(X)]=E[g(Y )]=0

E[f(X)²]=E[g(Y )²]=1

где супремум берется по всем (измеримым по Борелю) функциям f и g с нулевым

средним и единичной дисперсией. При этом, если X или Y постоянна п.н., то не

существует функций f и g, удовлетворяющих этим условиям, и по определению

полагаем ρ(X; Y ) = 0.

Можно показать, что коэффициент сжатия для χ²-дивергенций в точности равен

квадрату максимальной корреляции [11]:

η_χ2 (P_X, P_Y|X) = ρ(X; Y )².

(23)

Кроме того, следующее предложение показывает, что максимальную корреляцию

можно описать как некоторое сингулярное число; впервые это было показано в [9,12]

в несколько других видах (см. также [1, 4, 13, 40] и [48, теорема 3.2.4]).

Предложение

2 (максимальная корреляция как сингулярное число [9, 12]).

Для заданных случайных величин X ∈ X и Y ∈ Y с совместной вероятностной

мерой P_X,Y , состоящей из (P_X, W), можно определить матрицу дивергенций пе-

реходов (МДП )

(√

)

(√

)_†

B ≜ diag

P_X

W diag

P_Y

(24)

где через † обозначено псевдообращение Мура - Пенроуза. Тогда максимальная кор-

реляция ρ(X; Y ) равна второму по величине сингулярному числу матрицы B.

Для полноты изложения доказательство этого предложения приведено в Прило-

жении A. Из предложения 2 и равенства (23) видно, что коэффициент сжатия для

χ²-дивергенции на самом деле равен квадрату второго собственного числа МДП B.

Используя принцип минимакса Куранта - Фишера - Вейля (см. [49, теоремы 4.2.6

и 7.3.8]), это можно представить в виде



^B^T x2

η_χ2 (P_X, P_Y|X) = max

(25)

x∈R^|X|\{0}√

∥x∥²

PXx=0

где через 0 обозначен нулевой вектор соответствующей размерности, а

√P_XT - пра-

вый сингулярный вектор матрицы B^T , соответствующий ее максимальному сингу-

лярному числу, равному единице (см. Приложение A).

Разложения по сингулярным числам для МДП и их связь с χ²-дивергенцией хо-

рошо изучены в статистике. Например, в области анализа соответствий, основан-

ной Хиршфельдом в 1935 г. [9], рассматриваются зависимости между категорными

случайными величинами. В частности, в простом анализе соответствий двумерные

вероятностные меры P_X,Y рассматриваются как факторная таблица, и зависимость

между X и Y раскладывается по так называемым главным компонентам инерции

с помощью разложения по сингулярным числам матрицы B, см. работы [50; 51, § 2]

и библиографию в них. В [9] с помощью этого наблюдения было получено модаль-

ное разложение взаимной χ²-информации (или среднеквадратичной сопряженно-

сти Пирсона χ²(P_X,Y ∥ P_X P_Y )). Хотя в прошлом анализ соответствий использовался

просто как техника визуализации данных, теперь он является частью более широ-

кого инструментария геометрического анализа данных. Недавно в [40] в контексте

теории информации и теории оценивания были изучены главные компоненты инер-

ции, являющиеся собственными значениями матрицы Грама B^T B. Они обобщают

первые главные компоненты инерции (т.е. квадраты максимальной корреляции) до

величины, известной как k-корреляция, k ∈ {1, . . ., min{|X|, |Y|}-1}, которая равна

(k+1)-норме Ки Фаня матрицы B^T B минус 1. Там же доказаны некоторые свойства

k-корреляции, такие как выпуклость и неравенство об обработке данных [40, § II],

и представлены некоторые приложения. В альтернативном направлении в [52] иссле-

дованы нейронные сети, позволяющие приближенно выполнить анализ соответствий

в больших масштабах.

В то время как в анализе соответствий рассматриваются категорные случайные

величины, зависимость между общими (некатегорными) случайными величинами

изучается в близкой области исследований - анализе и идентификации так называ-

емых распределений Ланкастера [53,54]. Для заданного совместного распределения

P_X,Y на произведении измеримых пространств X ×Y пусть P_X и P_Y - маргинальные

распределения на X и Y соответственно, P_X P_Y - произведение этих распределений,

а L²(X, P_X) (соответственно, L²(Y, PY )) - гильбертово пространство интегрируемых

с квадратом вещественнозначных функций на X (соответственно, на Y) со скаляр-

ным произведением, заданным распределением P_X (соответственно, P_Y ). Предполо-

жим, что χ²(P_X,Y ∥ P_X P_Y ) < ∞, откуда следует, что P_X,Y абсолютно непрерывно от-

носительно P_X P_Y , и пусть dP_X,Y /dP_X P_Y - производная Радона - Никодима от P_X,Y

относительно P_XP_Y . Для такой постановки в [53] доказано, что существуют ортонор-

мированные базисы {f_j ∈ L²(X , P_X ) : 0 ≤ j < |X |} и {g_k ∈ L²(Y, P_Y ) : 0 ≤ k < |Y|}

и некоторая последовательность {σ_k ≥ 0 : 0 ≤ k < min{|X |, |Y|}} неотрицательных

корреляций, такие что P_X,Y является распределением Ланкастера, для которого

справедливо разложение

dP_X,Y

∑

(x, y) =

σ_kf_k(x)g_k(y).

(26)

dP_X P

k=0

Если X и Y конечны, разложение (26) в точности повторяет структуру разложения

по сингулярным числам матрицы B, соответствующей P_X,Y . Дальнейшие ссылки по

этой довольно общей области можно найти в [55; 56, п. II-D].

Еще одно направление исследований состоит в изучении вычислительных аспек-

тов разложений МДП. Известным методом вычисления разложений по сингулярным

числам МДП является алгоритм чередующихся условных математических ожида-

ний (ACE) (см. оригинальный алгоритм в контексте параметрической регрессии

в [57] и его вариант в контексте выделения признаков и понижения размерности

в [58]). По сути, алгоритм ACE использует степенной метод, или, в более общем

виде, метод ортогональных итераций (см. [59, п. 7.3.2; 60, п. 4.4.3; 61, п. 4.4]), для

оценки сингулярных векторов МДП. Оказывается, что такие сингулярные векторы,

соответствующие наибольшим сингулярным числам, можно выделять как “более ин-

формативные” функции вклада. Этот подход был использован в [62] для получения

результатов о скрытых марковских моделях в контексте обработки изображений,

a в [63] он был описан как средство универсального выделения признаков. В работах

[61, п. 4.5; 63] можно найти дальнейшие подробности о связях между разложения-

ми по сингулярным числам МДП и другими известными понятиями в статистике и

машинном обучении, такими как метод главных компонент [64, 65], анализ кано-

нической корреляции [66] и отображения диффузии [67].

После того как мы ввели необходимые нам коэффициенты сжатия, приведем

теперь несколько свойств коэффициентов сжатия для f-дивергенций; многие из них

хорошо известны либо легко доказываются, но некоторые, насколько нам известно,

ранее в литературе не встречались.

Предложение

3 (свойства коэффициентов сжатия совместных распределе-

ний). Коэффициент сжатия для f-дивергенции обладает следующими свойства-

ми:

1. (Нормировка): Для любой совместной вероятностной меры P_X,Y , состоящей

из P_X ∈ P_X и P_Y|X ∈ P_Y|X , выполнено 0 ≤ η_f (P_X, P_Y|X) ≤ 1;

2. (Независимость): Рассмотрим случайные величины X и Y с совместной вероят-

ностной мерой P_X,Y , состоящей из P_X ∈ P_X и P_Y|X = W ∈ P_Y|X . Если X и Y

независимы, т.е. W имеет единичный ранг, то η_f (P_X, P_Y|X) = 0. Наоборот,

если f строго выпукла в единице и η_f (P_X , P_Y|X ) = 0, то X и Y независимы;

3. (Разложимость): Рассмотрим произвольную совместную вероятностную меру

P_X,Y , маргинальные вероятностные меры которой таковы, что P_X ∈ P^◦X и

P_Y ∈ P^◦Y, и пусть f дважды дифференцируема в единице, причем f^′′(1) > 0. Если

мера P_X,Y разложима, то η_f (P_X, P_Y|X) = 1. Наоборот, если f также строго

выпукла, f(0) < ∞ и η_f (P_X , P_Y|X ) = 1, то P_X,Y разложима. (Это свойство

описано в теореме 1 в п. 3.1, где также определено понятие “разложимости”.)

4. (Выпуклость [8, предложение III.3]): Для любой фиксированной P_X ∈ P^◦X функ-

ция P_Y|X ∋ P_Y|X → η_f (P_X , P_Y|X ) выпукла по стохастической матрице P_Y|X ;

5. (Тензоризация [8, теорема III.9]): Если f порождает субаддитивную и однород-

ную f-энтропию (где f-энтропия любой неотрицательной случайной величи-

ны Z, такой что E[f(Z)] < ∞, определяется как Ent_f (Z) ≜ E[f(Z)] - f(E[Z]),

см. [8, § II]), и при этом

{

}

и PYi ∈ P^◦ при i ∈ {1,...,n}_Y

PXi,Yi : PXi ∈ P^Xi

- независимые совместные вероятностные меры, то

(

)

η_f

P_Xn

,P_Yn

= max

|Xn1

η_f (PXi , PYi |Xi),

1≤i≤n

где Xn1 = (X₁, . . . , X_n) и Yn1 = (Y₁, . . . , Y_n);

6. (Субмультипликативность): Если U → X → Y - дискретные случайные величи-

ны с конечным числом значений, образующие цепь Маркова, то

η_f (P_U , P_Y|U ) ≤ η_f (P_U , P_X|U )η_f (P_X, P_Y|X).

При этом для любой фиксированной совместной вероятностной меры P_X,Y ,

такой что X - не постоянная п.н., справедливо

η_f (P_U , P_Y|U

)

η_f (P_X, P_Y|X) =

sup

P_U|X : U→X→Y

η_f (P_U , P_X|U )

η_f (PU ,PX|U )>0

где супремум берется по всевозможным конечным множествам значений U

случайной величины U и по всем условным распределениям P_U|X ∈ P_U|X , таким

что U → X → Y образуют цепь Маркова;

7. (Нижняя граница максимальной корреляции [1, теорема 5; 8, теорема III.3; 7,

теорема 2]): Рассмотрим произвольную совместную вероятностную меру P_X,Y ,

маргинальные вероятностные меры которой таковы, что P_X ∈ P^◦X и P_Y ∈ P^◦Y .

Если f дважды дифференцируема в единице и f^′′(1) > 0, то

η_χ2 (P_X, P_Y|X) = ρ(X; Y )² ≤ η_f (P_X, P_Y|X).

(Усиление этого свойства приведено в теореме 2 в п. 3.1.)

В Приложении B приведены некоторые доказательства, а также соответству-

ющие ссылки, уточняющие эти результаты. Теперь сделаем несколько замечаний.

Во-первых, насколько нам известно, п. 3 предложения ранее не появлялся в литера-

туре в такой общности; были известны лишь случаи η_χ2 и η_KL (см. [13,15]).

Во-вторых, так как пп. 1-3 предложения 3 показывают, что коэффициенты сжа-

тия являются нормализованными мерами статистической зависимости между слу-

чайными величинами, можно рассматривать субмультипликативность из п. 6 как

мета-СНОД для коэффициентов сжатия по аналогии с (16). На самом деле, п. 6

также показывает, что коэффициентом сжатия в СНОД для η_f является сама ве-

личина η_f . Этот аспект пункта 6, хотя и довольно простой, также, насколько нам

известно, никогда в явном виде не встречался в литературе в такой степени общно-

сти; лишь случай η_χ2 был представлен в [68, лемма 6].

В-третьих, вариант неравенства об обработке данных для η_KL, приведенный в [15]

(см. также [5, п. II-A]) справедлив и для общих η_f . Действительно, если U

→

→ X → Y → V - дискретные случайные величины с конечными множествами

значений, образующие цепь Маркова, то немедленным следствием пп. 1 и 6 предло-

жения 3 является следующее свойство монотонности:

η_f (P_U , P_V|U ) ≤ η_f (P_X, P_Y|X).

(27)

В-четвертых, нижняя грань максимальной корреляции в п. 7 предложения 3 до-

стигается. Например, пусть f(t) = t log(t), и рассмотрим две равномерные бернулли-

евские случайные величины (X, Y ) с P_X = (1/2, 1/2) и с условным распределением

P_Y|X, заданным матрицей “двоичного симметричного канала”

[

]

1-α α

P_Y|X =⁰

(28)

1-α

где α ∈ [0, 1] - вероятность ошибки в канале. В [15] доказано, что в этом случае

нижняя грань максимальной корреляции выполнена с равенством:

η_KL(P_X, P_Y|X) = η_χ2(P_X, P_Y|X) = (1 - 2α)²,

(29)

где η_χ2 (P_X , P_Y|X ) = (1 - 2α)² можно легко вычислить с помощью характеризации

максимальной корреляции через сингулярные числа из предложения 2. Еще один

пример: пусть P_Y|X = E_β ∈ PX∪{e}|X -матрица “|X |-ичного канала со стиранием”

с вероятностью стирания β ∈ [0, 1] и символом стирания e:

E_β =

[

(1 - β)I β1 ],

(30)

где I ∈ R^|X|×|X| - единичная матрица, а 1 ∈ R^|X| - вектор-столбец из всех единиц.

Непосредственной проверкой легко убедиться, что

D_f (R_XE_β ∥P_XE_β) = (1 - β) × D_f(R_X ∥P_X)

для любых R_X , P_X ∈ P_X . Поэтому для любой вероятностной меры на входе P_X ∈ P_X

и любой f-дивергенции имеем η_f (P_X , P_Y|X ) = 1 - β.

Наконец, отметим, что хотя п. 7 предложения 3 был независимо доказан авто-

рами ранее в [1, теорема 5] с помощью идеи аппроксимации f-дивергенции, эта же

идея использовалась в [8, теорема III.3; 7, теорема 2] для доказательства этого ре-

зультата. Кроме того, эта идея вытекает из доказательства теоремы 5.4 работы [17]

(приведенной далее в п. 6 предложения 5).

2.3. Коэффициенты эргодичности. Прежде чем перейти к обсуждению коэффи-

циентов сжатия, зависящих только от стохастических матриц, вкратце опишем бо-

лее общее понятие коэффициентов эргодичности. Впервые они возникли в контексте

изучения эргодичности и скоростей сходимости неоднородных (по времени) цепей

Маркова с конечными пространствами состояний (см. [69, § 1]). Они определяются

следующим образом.

Определение 4 (коэффициент эргодичности [16, определение 4.6]). Коэффи-

циентом эргодичности называется непрерывная скалярная функция η : PY|X →

→ [0, 1], где P_Y|X имеет фиксированную размерность (и снабжено стандартной то-

пологией, индуцированной нормой Фробениуса). Этот коэффициент называется соб-

ственным, если для любого W ∈ P_Y|X равенство η(W) = 0 выполнено тогда и толь-

ко тогда, когда W = 1P_Y для некоторой вероятностной меры P_Y ∈ P_Y (т.е. W имеет

единичный ранг).

Полезным свойством собственных коэффициентов эргодичности является взаи-

мосвязь со слабой эргодичностью. Рассмотрим последовательность стохастических

по строкам матриц {W_k ∈ P_X|X : k ∈ N}, задающих неоднородную цепь Маркова

на пространстве состояний X . Введем обозначение для последовательного произве-

дения этих матриц в количестве r ≥ 1, начиная с номера p ∈ N:

∏

T(p,r) ≜

Wp+i.

(31)

i=0

Цепь Маркова {W_k ∈ P_X|X : k ∈ N} называется слабо эргодической (в смысле

Колмогорова), если для всех x₁, x₂, x₃ ∈ X и всех p ∈ N [16, определение 4.4]

(

)

lim

= 0.

(32)

[T(p,r)]x1,x3 - [T(p,r)]x2,x3

r→∞

Это определение формализует интуитивное представление, что для эргодической це-

пи Маркова строки таких произведений должны становиться равными при r → ∞.

(Отметим, что если предельная строка стохастической матрицы lim

T(p,r) суще-

r→∞

ствует для всех p ∈ N, то цепь Маркова называется сильно эргодической [16, опре-

деление 4.5].) В следующем предложении утверждается, что слабую эргодичность

можно эквивалентным образом определить через собственные коэффициенты эрго-

дичности.

Предложение 4 (слабая эргодичность [16, лемма 4.1]). Пусть η: PX|X →

→ [0, 1] - собственный коэффициент эргодичности. Тогда неоднородная цепь Мар-

кова {W_k ∈ P_X|X : k ∈ N} слабо эргодична тогда и только тогда, когда

∀p ∈ N, lim

η(T(p,r)) = 0.

r→∞

Чтобы пояснить интуитивный смысл этого результата, заметим, что для слабо

эргодической цепи Маркова T(p,r) становится (приблизительно) матрицей единич-

ного ранга при r → ∞. Таким образом, следует ожидать, что lim

η(T(p,r)) = 0,

r→∞

поскольку собственный коэффициент эргодичности непрерывен и равен нулю, ко-

гда его аргумент имеет единичный ранг. Формальное доказательство предложения 4

можно найти в [16, лемма 4.1]. О дальнейшем развитии подобных идей см. работы

[69; 16, гл. 3 и 4; 70; 71, гл. 3] и библиографию в них.

Одним из первых и наиболее примечательных примеров собственных коэффи-

циентов эргодичности являются коэффициенты сжатия Добрушина⁵. Для заданной

стохастической по строкам матрицы P_Y|X = W ∈ P_Y|X ее коэффициент сжатия

Добрушина определяется как константа Липшица отображения P_X ∋ P_X → P_X W

относительно ℓ¹-нормы (или расстояния по вариации) [14]:

∥R_XW - P_XW∥_TV

η_TV(W) ≜ sup

(33)

RX,PX ∈PX

∥R_X - P_X∥_TV

RX=PX

= max

∥vW∥₁ =

(34)

v∈(R^|X|)^∗

∥v∥₁=1, v1=0

= max

∥R_XW - P_XW∥_TV =

(35)

RX,PX ∈PX



= max

^PY|X=x - PY|X=x′



(36)

x,x^′∈X

∑

{

}

= 1 - min

min

P_Y|X(y |x), P_Y|X(y |x^′)

(37)

x,x^′∈X

y∈Y

где различные эквивалентные характеризации (34), (35), (36) (двухточечная харак-

теризация Добрушина [14]) и (37) (характеризация аффинности [73; 29, форму-

ла (4.13)]) определения (33) можно либо найти в работе [16, гл. 4.3], либо легко

ввести из ее результатов. Формула (37) показывает, что η_TV(W) < 1 тогда и только

тогда, когда W является скремблирующей матрицей (т.е. никакие две строки W не

ортогональны) [16, c. 82]. (Из этого также следует, что η_TV(W ) < 1 тогда и только

тогда, когда пропускная способность с нулевой ошибкой для P_Y|X равна нулю [74].)

Вдобавок к свойствам собственных коэффициентов эргодичности величина η_TV

обладает также следующими свойствами:

1. Непрерывность по Липшицу [70, теорема 3.4, замечание 3.5]: Для любых V, W ∈

∈ P_Y|X справедливо неравенство |η_TV(V )-η_TV(W)| ≤ ∥V - W∥_∞, где через ∥·∥_∞

обозначена индуцированная ℓ^∞-норма, или максимальная сумма модулей по стро-

ке применительно к матрице;

⁵ Следуя библиографической дискуссии в [16, с. 144-147], авторами коэффициента сжатия Доб-

рушина (или, эквивалентно, коэффициента эргодичности Добрушина) можно также считать (по

крайней мере, частично) Дёблина и Маркова. В литературе этот коэффициент встречался под

названием коэффициент сжатия Дёблина и возникал в лемме Маркова о сжатии (см., напри-

мер, [72, c. 619]).

2. Субмультипликативность [16, лемма 4.3]: Для любых V ∈ P_X|U и W ∈ P_Y|X

справедливо неравенство η_TV(V W ) ≤ η_TV(V )η_TV(W );

3. Граница субдоминантного собственного числа [69, c. 584, формула (9)]: Для лю-

бой W ∈ P_X|X неравенство η_TV(W) ≥ |λ| справедливо для любого субдоминант-

ного собственного числа λ = 1 матрицы W .

Благодаря двум последним свойствам η_TV становится удобным инструментом для

исследования неоднородных цепей Маркова. Как указано в [70, § 1], для однородной

цепи Маркова W ∈ P_X|X со стационарной вероятностной мерой π ∈ P_X хорошо из-

вестно, что модуль второго по абсолютной величине собственного значения матри-

цы W , обозначаемый через μ(W ), отвечает за скорость сходимости к стационарному

состоянию. Действительно, если μ(W) < 1, то μ(Wⁿ) = μ(W)ⁿ, и lim Wⁿ = 1π со

n→∞

скоростью, определяемой величиной μ(W ). Однако для неоднородной цепи Марко-

∏

ва в общем случае {W_k ∈ P_X|X : k ∈ N}, μ(T(0,n)) =

μ(W_i), поскольку модуль

i=0

второго собственного числа не мультипликативен. Последние два свойства η_TV пока-

зывают, что эта величина является адекватной заменой модуля второго собственного

числа при изучении неоднородных цепей Маркова, поскольку

∏

μ(T(0,n)) ≤ η_TV(T(0,n)) ≤

η_TV(W_i).

i=0

2.4. Коэффициенты сжатия стохастических матриц. Коэффициенты сжатия сто-

хастических матриц для f-дивергенций образуют широкий класс коэффициентов

эргодичности. Они определяются аналогично формуле (33), но с использованием

других f-дивергенций вместо расстояния по вариации.

Определение 5 (коэффициент сжатия стохастической матрицы [14-17]). Для

любой стохастической матрицы P_Y|X = W ∈ P_Y|X ее коэффициент сжатия для

заданной f-дивергенции равен

D_f(R_XW ∥P_XW)

η_f (P_Y|X) ≜

sup

= sup η_f (P_X, P_Y|X),

RX,PX ∈PX

D_f(R_X ∥P_X)

PX∈PX

0<D_f (RX ∥PX )<+∞

где супремум берется по всем вероятностным мерам R_X и P_X , таким что 0 <

< D_f(R_X ∥P_X) < +∞. Если при этом Y постоянна п.н., то по определению полагаем

η_f (P_Y|X) = 0.

Из этого определения немедленно вытекают СНОД для коэффициентов сжатия

стохастических матриц, аналогичные неравенствам (15) и (16). Кроме того, для ко-

эффициентов сжатия стохастических матриц также справедлив вариант предложе-

ния 1. Действительно, из определения 5 и предложения 1, получаем, что для любой

стохастической матрицы P_Y|X ∈ P_Y|X и любой выпуклой дифференцируемой функ-

ции f : (0, ∞) → R с равномерно ограниченной производной в некоторой окрестности

единицы, такой что f(1) = 0, справедливо

If (U; Y )

η_f (P_Y|X) =

sup

(38)

PU,X : U→X→Y

If (U; X)

0<I_f (U;X)<+∞

где супремум берется по всем совместным вероятностным мерам P_U,X (состоящим

из P_U ∈ P_U и P_X|U ∈ P_X|U ) и конечным алфавитам U случайной величины U,

такой что U → X → Y образуют цепь Маркова. Частный случай этого результата

для КЛ-дивергенции можно найти в [75, c. 345, задача 15.12] (случай конечного

алфавита) и [7] (общий случай).

Имеется два важных примера коэффициентов сжатия стохастических матриц:

коэффициент сжатия Добрушина для расстояния по вариации (определенный в (33))

и коэффициент сжатия для КЛ-дивергенции. Как и выше, для заданной P_Y|X ∈

∈ P_Y|X обозначаем через η_TV(PY |X), η_KL(PY |X), и η_χ2(PY |X) коэффициент сжатия

P_Y|X для расстояния по вариации, КЛ-дивергенции и χ²-дивергенции соответствен-

но. В [15] доказано, что для любой стохастической матрицы P_Y|X ∈ P_Y|X верно

равенство

η_KL(P_Y|X) = η_χ2 (P_Y|X).

(39)

Таким образом, при изучении коэффициентов сжатия стохастических матриц не

требуется рассматривать η_KL и η_χ2 по отдельности. Заметим, что альтернативное

доказательство равенства (39) (справедливое для общих измеримых пространств)

дано в [7, теорема 3]. Кроме того, менее известное наблюдение состоит в том, что

правильное обобщение на произвольную размерность техники доказательства из [76,

лемма 1, теорема 1] (где аналитически вычисляется η_KL для любой стохастической

матрицы размера 2 × 2) также позволяет доказать равенство (39). Следует отме-

тить, что основным результатом работы [76] является индуктивный подход к оцен-

ке сверху для η_KL в байесовских сетях (или направленных ациклических графах).

Суть этого подхода прекрасно изложена в [7], где также приведены доказательства

его обобщения на расстояние по вариации (с помощью представления Гольдштейна

расстояния по вариации между двумя совместными распределениями через одно-

временное максимальное склеивание [77]) и описана его связь с задачей перколяции

узлов.

Теперь перечислим некоторые известные свойства коэффициентов сжатия стоха-

стических матриц.

Предложение 5 (свойства коэффициентов сжатия стохастических матриц).

Коэффициент сжатия для f-дивергенции обладает следующими свойствами:

1. (Нормировка): Для любой стохастической матрицы P_Y|X ∈ P_Y|X справедливо

неравенство 0 ≤ η_f (P_Y|X) ≤ 1;

2. (Независимость [17, § 4]): Рассмотрим стохастическую матрицу P_Y|X ∈ P_Y|X .

Если P_Y|X имеет единичный ранг, т.е. X и Y независимы, то η_f (P_Y|X ) = 0.

Наоборот, если f строго выпукла в единице и η_f (P_Y|X ) = 0, то P_Y|X имеет

единичный ранг;

3. (Скремблирование [17, теорема 4.2]): Для заданной стохастической матрицы

P_Y|X ∈ P_Y|X матрица P_Y|X является скремблирующей тогда и только тогда,

когда η_f (P_Y|X ) < 1;

4. (Выпуклость [17, § 4; 8, предложение III.3]): Функция P_Y|X ∋ P_Y|X → η_f (P_Y|X)

выпукла;

5. (Субмультипликативность [17, § 4]): Если U → X → Y

- дискретные случай-

ные величины с конечными множествами значений, образующие цепь Маркова,

т.е. стохастические матрицы условных распределений таковы, что PY|U =

= P_X|UPY |X, то

η_f (P_Y|U ) ≤ η_f (P_X|U )η_f (P_Y|X);

6. (Нижняя граница χ²-дивергенции [17, теорема 5.4; 19, предложение II.6.15]): Рас-

смотрим стохастическую матрицу P_Y|X ∈ P_Y|X . Если f дважды дифференци-

руема в единице и f^′′(1) > 0, то

η_χ2 (P_Y|X) ≤ η_f (P_Y|X);

7. (Верхняя граница расстояния по вариации [17, теорема 4.1; 19, предложение

II.4.10]): Для любой стохастической матрицы P_Y|X ∈ P_Y|X справедливо нера-

венство

η_f (P_Y|X) ≤ η_TV(P_Y|X).

Доказательства этих результатов мы опускаем, поскольку они либо аналогич-

ны соответствующим доказательствам в предложении 3, либо даны в указанных

ссылках. Пункты 1, 2 и 4 предложения 5 означают, что коэффициенты сжатия сто-

хастических матриц для f-дивергенций часто являются собственными коэффициен-

тами эргодичности. (Действительно, из выпуклости отображения P_Y|X → η_f (P_Y|X )

в п. 4 предложения 5 следует, что это отображение непрерывно на внутренней об-

ласти P_Y|X .) Заметим, что п. 3 показывает, что η_f (P_Y|X ) = 1 тогда и только тогда,

когда η_TV(P_Y|X ) = 1 [17, теорема 4.2], и непосредственной проверкой легко убе-

диться, что η_f (P_Y|X ) = 1 тогда и только тогда, когда пропускная способность при

нулевой ошибке для P_Y|X строго положительна [74]. Отметим также, что результат

об экстремальном значении, аналогичный п. 6 предложения 3, хотя и менее содер-

жательный, можно вывести из п. 5 предложения 5.

В то время как соотношение (39) показывает, что в п. 6 предложения 5 легко

может достигаться равенство, неравенство в п. 7 часто бывает строгим. Например,

когда P_Y|X = W - стохастическая матрица размера 2 × 2 с параметрами a, b ∈ [0, 1]

[

]

1-a a

W =

(40)

1-b

непосредственной проверкой легко убедиться, что η_KL(P_Y|X ) ≤ η_TV(P_Y|X ), где нера-

венство обычно бывает строгим, поскольку

(√

√

)₂

η_KL(P_Y|X) = 1 -

a(1 - b) +

b(1 - a)

(41)

η_TV(P_Y|X) = |1 - a - b|,

(42)

где равенство (41) доказано в [76, теорема 1], а (42) легко получить с помощью (36).

Более того, в частном случае, где P_Y|X имеет вид (28), получаем [15]

η_KL(P_Y|X) = (1 - 2α)² ≤ |1 - 2α| = η_TV(P_Y|X).

(43)

С другой стороны, как показано в конце п. 2.2, η_f (P_Y|X ) = 1 - β для любой f-ди-

вергенции, когда P_Y|X = E_β ∈ PX∪{e}|X .

Ввиду п. 6 и равенства (39) естественно задаться вопросом, существуют ли другие

f-дивергенции, коэффициенты сжатия которых (для стохастических матриц) также

равны η_χ2 . Следующий результат из [18, теорема 1], обобщающий соотношение (39),

дает ответ на этой вопрос.

Предложение 6 (коэффициенты сжатия для операторно выпуклых f-дивер-

генций [18, теорема 1; 19]). Для любой нелинейной операторно выпуклой функции

f : (0,∞) → R, такой что f(1) = 0, и любой стохастической матрицы PY |X ∈

∈ P_Y|X справедливо равенство

η_f (P_Y|X) = η_χ2 (P_Y|X).

Доказательство теоремы 1 из [18] основано на элегантном интегральном пред-

ставлении операторно выпуклых функций (см. п. 6.1). Такие представления явля-

ются мощным инструментом для доказательства неравенств между коэффициен-

тами сжатия, и мы воспользуемся ими для обобщения предложения 6 в п. 3.4. На

самом деле, п. 7 предложения 5 также можно доказать с помощью интегрального

представления (см. [8, теорема III.1]).

В заключение этого пункта укажем на дополнительный обзор по коэффициентам

сжатия [7, § 2], где, в частности, имеются ссылки на различные приложения этих

идей в существующей литературе.

§ 3. Основные результаты и их обсуждение

В настоящей статье мы в основном будем сравнивать между собой различные

коэффициенты сжатия. В частности, мы будем интересоваться следующими основ-

ными вопросами:

Когда коэффициенты сжатия совместных распределений достигают своей

верхней границы, равной единице? В теореме 1 (п. 3.1) мы покажем, что это про-

исходит, когда совместные распределения разложимы.

Можно ли достичь нижней границы максимальной корреляции из п. 7 пред-

ложения 3 путем наложения дополнительных ограничений в экстремальной

задаче, определяющей коэффициенты сжатия совместных распределений? Да,

можно потребовать, чтобы f-дивергенция на входе была малой, как показано

в теореме 2 (п. 3.1).

Обычно мы оцениваем η_KL(P_X, P_Y|X) снизу через η_χ2(P_X, P_Y|X) (предложение 3,

п. 7), а сверху - через η_TV(P_Y|X) (предложение 5, п. 7). Существует ли простая

верхняя граница на η_KL(P_X, P_Y|X) через η_χ2 (P_X, P_Y|X)? Да, две такие границы

приведены в следствии 1 и теореме 4 в п. 3.2.

Можно ли обобщить эту верхнюю границу для КЛ-дивергенции на другие f-ди-

вергенции? Да, более общая граница представлена в теореме 3 (п. 3.2).

Когда X и Y совместно гауссовские, с помощью характеризации взаимной ин-

формации, данной в (18), можно установить [2, теорема 7], что

η_KL(P_X, P_Y|X) = η_χ2(P_X, P_Y|X).

Существует ли простое доказательство этого результата, опирающееся непо-

средственно на определение η_KL? Выполняется ли это равенство, если на-

ложить дополнительное ограничение по мощности в экстремальной задаче

для η_KL? Да, в п. 3.3 мы рассмотрим гауссовский случай, и в теореме 5 дока-

жем это равенство для η_KL с ограничением по мощности. Наше доказательство

также устанавливает это известное равенство с помощью определения η_KL через

КЛ-дивергенцию.

Коэффициенты сжатия стохастических матриц тесно связаны с предпорядком

меньшего искажения на стохастических матрицах [7, § 6]. Можно ли обобщить

результат предложения 6 и получить новые сведения о предпорядке меньше-

го искажения? Да, в п. 3.4 мы вводим предпорядок меньшего искажения, и в

теореме 6 получаем целый класс его эквивалентных характеризаций. Мы также

приводим пример применения теоремы 6 в теореме 7, обобщающей СНОД Само-

родницкого.

Границы, которые мы выведем в ответ на вопросы 3-5, имеют вид верхней границы в

η_χ2 (P_X, P_Y|X) ≤ η_f (P_X, P_Y|X) ≤ Cη_χ2 (P_X, P_Y|X),

(44)

где первое неравенство - это просто нижняя граница максимальной корреляции из

п. 7 предложения 3, а константа C зависит от P_X,Y и f; заметим, что C = 1 в по-

становке вопроса 5. Будем называть такие границы линейными границами между

коэффициентами сжатия совместных распределений. Наши основные результаты

сформулированы в нескольких следующих пунктах.

3.1. Свойства коэффициентов сжатия совместных распределений. В этом пункте,

как и в п. 3.2, мы будем предполагать, что заданы случайные величины X ∈ X и

Y ∈ Y с совместной вероятностной мерой PX,Y , состоящей из P_X ∈ P_X и PY |X =

= W ∈ P_Y|X, причем маргинальные вероятностные меры таковы, что P_X ∈ P^◦X

и PY = PXW ∈ P◦Y. В этом пункте приведены два результата. В первом из них

переформулирован п. 3 предложения 3.

Начнем с необходимого определения: совместная вероятностная мера P_X,Y назы-

вается разложимой, если существуют функции h: X → R и g: Y → R, такие что

h(X) = g(Y ) п.н. и Var(h(X)) > 0, где через Var(·) обозначена дисперсия. Эквива-

лентным образом, P_X,Y разложима тогда и только тогда, когда неориентированный

двудольный граф с непересекающимися множествами вершин X и Y и множеством

ребер {(x, y) ∈ X × Y : P_Y|X (y | x) > 0} имеет две или более компоненты связно-

сти (см. [15, § 1]). Эта комбинаторная характеризация разложимости имеет место,

поскольку h и g существуют тогда и только тогда, когда матрица W имеет блочно-

диагональную структуру после соответствующей перестановки ее строк и столбцов

(где блоки определяются множествами прообразов h и g), и эти блоки соответствуют

компонентам связности ассоциированного двудольного графа.

С помощью понятия разложимости можно описать, когда коэффициенты сжатия

совместных распределений равны единице.

Теорема 1 (свойство разложимости). Пусть задана дважды дифференцируе-

мая в единице выпуклая функция f : (0, ∞) → R, такая что f(1) = 0 и f^′′(1) > 0.

Тогда справедливо следующее:

1. Если P_X,Y разложима, то η_f (P_X, P_Y|X) = 1;

2. Если f строго выпукла и удовлетворяет условию f(0) = lim f(t) < ∞, то из

t→0⁺

равенства η_f (P_X , P_Y|X ) = 1 следует, что P_X,Y разложима.

Теорема 1 доказана в Приложении C. Как отмечалось выше, этот результат был

ранее известен только для случаев η_χ2 и η_KL [13, 15]. Заметим также, что в слу-

чае η_f (P_X , P_Y|X ) = 1 можно проверить, что пропускная способность при нулевой

ошибке для P_Y|X строго положительна [74].

Наш второй результат - уточнение п. 7 предложения 3, он показывает, что при

стремлении f-дивергенции на входе к нулю общие коэффициенты сжатия превра-

щаются в коэффициенты сжатия для χ²-дивергенции.

Теорема 2 (локальная аппроксимация коэффициентов сжатия). Пусть дана

выпуклая функция f : (0, ∞) → R, строго выпуклая в единице и дважды дифферен-

цируемая в единице, такая что f(1) = 0 и f^′′(1) > 0. Тогда

D_f (R_XW ∥P_XW)

η_χ2 (P_X, P_Y|X) = lim

sup

δ→0⁺

D_f (R_X ∥P_X)

RX∈PX

0<D_f (RX ∥PX )≤δ

Доказательство приведено в Приложении D; заметим, что частный случай тео-

ремы 2 для КЛ-дивергенции был представлен вместе с наброском доказательства

в [1, теорема 3]. Теперь уместно сделать несколько замечаний. Во-первых, отметим,

что в доказательстве п. 7 предложения 3 в Приложении B (как и в независимых

доказательствах в [8, теорема III.2] и [7, теорема 2]) уже содержится идея о том, что

оптимизация η_f (P_X , P_Y|X ) по локальным возмущениям P_X дает η_χ2(P_X , P_Y|X ) в си-

лу (14) и (25). Однако это доказательство (с незначительными видоизменениями)

показывает лишь, что величина η_χ2 (P_X , P_Y|X ) ограничена сверху правой частью ра-

венства из теоремы 2. Хотя интуитивно может быть и ясно, что эта верхняя грани

достигается с равенством, формальное доказательство содержит несколько техни-

ческих деталей, как показано в Приложении D.

Во-вторых, теорема 2 очевидным образом показывает, что нижняя граница мак-

симальной корреляции в п. 7 предложения 3 может быть достигнута, когда в задаче

оптимизации для η_f (P_X , P_Y|X ) наложено дополнительное ограничение, что f-ди-

вергенция на входе мала. Поэтому из теоремы 2 вытекает нижняя граница мак-

симальной корреляции. Эта идея оказалась важна при сравнении η_χ2 (P_X , P_Y|X )

и η_KL(P_X, P_Y|X) в статистическом контексте [78, с. 5].

В-третьих, теорему 2 можно рассматривать как минимаксную характеризацию

η_χ2 (P_X, P_Y|X), поскольку супремум отношения f-дивергенций является невозраста-

ющей функцией δ, и поэтому предел (при δ → 0⁺) можно заменить на инфимум (по

всем δ > 0).

В-четвертых, при выполнении условий предложения 1 и теоремы 2 непосред-

ственной проверкой легко убедиться, что

If (U; Y )

η_χ2 (P_X, P_Y|X) = lim

sup

(45)

δ→0⁺ P_U|X : U→X→Y

If (U; X)

0<I_f (U;X)≤δ

где супремум берется по всем стохастическим матрицам P_U|X ∈ P_U|X , таким что

U = {0,1}, U ∼ Bernoulli(1/2) и U → X → Y образуют цепь Маркова. Таким об-

разом, ограничение на малость f-дивергенции на входе в определении η_f (P_X , P_Y|X )

через f-дивергенцию соответствует условиям малой I_f (U; X) и U ∼ Bernoulli(1/2)

в (45).

Наконец, рассмотрим траекторию вероятностных мер на входе

(√

)

R(ε)X = P_X + εK^∗X diag

P_X

(

где ε > 0 достаточно мало, а K^∗X ∈

R^|X|)∗ - левый сингулярный вектор, соответ-

ствующий второму по величине сингулярному числу МДП B (см. (25)). Как по-

казывает доказательство в Приложении D, эта траектория удовлетворяет условию

(

)

lim

D_f

R(ε)X ∥P_X

= 0 и достигает значения η_χ2(P_X,PY |X) в теореме 2:

ε→0

(

)

D_f

R(ε)W∥PXW

lim

(

)

= η_χ2 (P_X , PY |X

(46)

ε→0

D_f

R(ε)

∥P_X

Соответствующей траекторией условных распределений для (45) является P(ε)X|U ∈

∈ P_X|U со строками

{

}

(√

)

P(ε)X|U=u = P_X + (2u - 1)εK^∗X diag

P_X

: u ∈ {0,1} ,

где ε > 0 достаточно мало. Эта траектория удовлетворяет условию

lim

If (U; X(ε)) = 0

ε→0

и достигает значения η_χ2 (P_X , P_Y|X ) в (45):

If (U; Y(ε))

lim

= η_χ2 (P_X , PY |X ),

(47)

ε→0 I_f (U; X(ε))

где U ∼ Bernoulli(1/2), U → X(ε) → Y(ε) - случайные величины, образующие цепь

(

)

Маркова с совместной вероятностной мерой

P_U , P(ε)X|U , P_Y|X

, P(ε)Y|U

= P(ε)X|UP_Y|X,

а маргинальная вероятностная мера для X(ε) равна P_X .

3.2. Линейные границы между коэффициентами сжатия. Напомним, что мы рас-

сматриваем заданную совместную вероятностную меру P_X,Y с маргинальными ве-

роятностными мерами P_X ∈ P^◦X и P_Y ∈ P^◦Y . Наш следующий результат описывает

линейную верхнюю границу на η_f (P_X , P_Y|X ) через η_χ2 (P_X , P_Y|X ) для определенного

класса f-дивергенций.

Теорема

(граница на коэффициенты сжатия). Пусть задана выпуклая

функция f : (0, ∞) → R, трижды дифференцируемая в единице, такая что f(1) = 0,

f^′′(1) > 0 и f(0) < ∞, удовлетворяющая условию (75) для любого t ∈ (0,∞)

(см. п. 4.1). Предположим также, что разностное отношение g : (0, ∞) → R, опре-

f(t) - f(0)

деляемое как g(t) =

, выпукло вверх. Тогда

f^′(1) + f(0)

η_f (P_X, P_Y|X) ≤

η_χ2 (P_X, P_Y|X).

f^′′(1)minPX(x)

x∈X

Теорема 3 доказана в п. 4.2. Условия на f гарантируют, что получаемая f-дивер-

генция обладает свойствами КЛ-дивергенции, требуемыми в доказательстве теоре-

мы 4 (см. ниже). Таким образом, аналогичная техника доказательства работает и

для теоремы 3. Непосредственным частным случаем для КЛ-дивергенции, впервые

доказанным в [1, теорема 10], является

Следствие 1 (граница на КЛ-коэффициенты сжатия [1, теорема 10]). Спра-

ведливо неравенство

)

η_χ2 (P_X, P_Y|X

η_KL(P_X, P_Y|X) ≤

minPX(x)

x∈X

Следствие 1 можно вывести из теоремы 3, убедившись, что функция f(t) =

= tlog(t) удовлетворяет условиям теоремы 3 (см. [79]). Подробное доказательство

см. в Приложении E. Константу в верхней границе на η_KL(P_X , P_Y|X ) из следствия 1

можно улучшить, как показывает следующая

Теорема 4 (улучшенная граница на КЛ-коэффициенты сжатия). Справедливо

неравенство

)

2η_χ2 (P_X , P_Y|X

η_KL(P_X, P_Y|X) ≤

(

)

ϕ maxmin{PX (A), 1 - PX (A)} minPX(x)

A⊆X

x∈X

где функция ϕ: [0, 1/2] → R определена в (68) (см. п. 4.1).

Теорема 4 также доказана в п. 4.2, и в силу соотношения (70) в п. 4.1 эта граница

точнее, чем граница из следствия 1. Теперь уместно сделать несколько замечаний

по поводу следствия 1 и теорем 3 и 4.

Во-первых, как показано на рис. 1a, верхние границы из этих утверждений мо-

гут быть строго меньше тривиальной верхней границы, равной единице. Например,

когда (X, Y ) - равномерные бернуллиевские случайные величины с P_X = (1/2, 1/2)

и PY |X, описанные в (28), для некоторого α ∈ [0,1] (что соответствуетсечению вдоль

P_X(1) = 1/2 на рис. 1a), верхние границы из следствия 1 и теоремы 4 обе равны

2η_χ2 (P_X , P_Y|X )

η_χ2 (P_X, P_Y|X)

(

)

= 2(1 - 2α)²,

(48)

minPX(x)

ϕ maxmin{PX (A), 1 - PX (A)} minPX(x)

x∈X

A⊆X

x∈X

0,8

0,6

0,4

0,8

0,2

0,6

0,4

0,2

P_X(1)

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

(a) Графики функций η_χ2 (PX , PY |X ) (нижняя сетка), ηKL(PX , PY |X ) (вторая снизу) и

линейных верхних границ на η_KL(PX, PY |X). Верхняя сетка соответствует верхней границе

из следствия 1, а вторая сверху - более точной верхней границе из теоремы 4.

0,8

0,6

0,4

0,1

0,2

0,3

0,4

0,5

0,2

0,6

0,7

0,8

0,9

P_X(1)

(b) Графики верхних границ на отношение η_KL(PX, PY |X)/ηχ2 (PX, PY |X), соответству-

ющее нижней сетке. Границе 1/ min PX(x) из следствия 1 соответствует верхняя сетка,

x∈X

( (

)

а более точной границе 2/ ϕ maxmin{PX (A), 1 - PX (A)} min PX (x) из теоремы 4 -

A⊆X

x∈X

вторая сверху.

Рис. 1. Графики границ на коэффициенты сжатия из следствия 1 и теоремы 4 для

двух бернуллиевских случайных величин (X, Y ) с совместной вероятностной мерой,

состоящей из PX = (PX (0), PX (1)) и PY |X , заданных в (28), для вероятности пере-

хода в канале α ∈ [0, 1].

что следует из (29) и того факта, что

maxmin{PX (A), 1 - PX (A)} =

A⊆X

Эта верхняя граница точнее, чем тривиальная граница, равная 1, когда

√

2(1 - 2α)² < 1

⇐⇒

<α<

(49)

Заметим также, что эта верхняя граница не достигается с равенством при таком

сценарии, поскольку (1-2α)² = η_KL(P_X , P_Y|X ) = η_χ2 (P_X , P_Y|X ), как показано в (29).

Во-вторых, наши доказательства теорем 3 и 4 опираются на обобщения хорошо

известного неравенства Пинскера (или неравенства Чисара - Кемпермана - Кульба-

ка - Пинскера; см. [80, § V]), оценивающие сверху расстояние по вариации через

КЛ-дивергенцию и другие f-дивергенции. Таким образом, возникает естественный

вопрос: являются ли эти границы более точными, чем граница расстояния по вариа-

ции из п. 7 предложения 5? Как показывает следующий пример, в некоторых режи-

мах наши границы точнее. Пусть (X, Y ) - равномерные бернуллиевские случайные

величины с P_X = (1/2, 1/2) и P_Y|X, заданными в (28), для некоторого α ∈ [0, 1]. То-

гда (48) задает верхние границы из следствия 1 и теоремы 4, и граница расстояния

по вариации имеет вид

(50)

с учетом определения 5, п. 7 предложения 5 и соотношения (43). Следовательно,

наша граница (48) точнее, чем граница через η_TV, когда

2(1 - 2α)² < |1 - 2α|

⇐⇒

<α<

или

<α<

(51)

Поскольку наши верхние границы могут быть больше единицы (см. (49)), мы не

можем надеяться превзойти границу через η_TV (≤ 1) во всех режимах. С другой

стороны, преимуществом наших верхних границ является то, что они “подходят” к

нижней границе через η_χ2 в п. 7 предложения 3; полезное применение этого будет

показано в п. 4.3.

В-третьих, интуитивно можно ожидать, что граница между коэффициентами

сжатия должна зависеть от мощности |X | или |Y|. Поскольку минимальная вероят-

ность во всех наших верхних границах соответствует 1/minPX(x) ≥ |X|, на первый

x∈X

взгляд можно было бы интерпретировать ее как “моделирующую” |X|. К сожалению,

эта интуитивная догадка неверна. Численные результаты, представленные графи-

чески на рис. 1b, показывают, что отношение

η_KL(P_X, P_Y|X)/η_χ2 (P_X, P_Y|X)

значительно увеличивается возле граничного значения P_X , когда любая из компо-

нент P_X близка к нулю. Этот эффект, хотя и неудивительный с учетом поведения

вероятностных симплексов в их граничных точках относительно КЛ-дивергенции

в качестве расстояния, адекватно учитывается верхними границами в следствии 1

и теореме 4, поскольку величина 1/minPX(x) возрастает, когда любая из компонент

x∈X

вероятностной меры на входе стремится к нулю (см. рис. 1b). Очевидно, линейные

верхние границы на η_f (P_X, P_Y|X), выражаемые только через |X| или |Y|, этот эф-

фект отражать не могут. Это подтверждает необходимость присутствия минималь-

ной вероятности в наших линейных границах.

Наконец, заметим, что неравенство 1/minPX(x) ≥ |X| не препятствует возмож-

x∈X

ности того, что 1/ minPX(x) будет гораздо больше, чем |X|. Таким образом, при

x∈X

больших |X| наши границы могут стать слабыми (см. пример в п. 4.4). В результате

границы из теоремы 3, следствия 1 и теоремы 4, как правило, представляют интерес

в следующих случаях:

|X | и |Y| малы: рис. 1 показывает, что наши границы могут быть весьма точными,

когда |X | = |Y| = 2;

2. Слабая зависимость, т.е. I(X; Y ) мала: такая ситуация естественным образом

возникает при анализе эргодичности цепей Маркова - см. п. 4.3;

3. Произведение распределений: если соответствующая совместная вероятностная

мера является произведением, можно использовать свойство тензоризации коэф-

фициентов сжатия (п. 5 предложения 3) - см. п. 4.4.

3.3. Коэффициенты сжатия совместно гауссовских случайных величин. В этом

пункте рассмотрим коэффициенты сжатия для КЛ- и χ²-дивергенций, соответству-

ющие двумерным гауссовским распределениям. Пусть X и Y - совместно гауссов-

ские случайные величины. Их совместное распределение имеет один из трех воз-

можных видов:

1. Величины X или Y постоянны п.н., и коэффициенты сжатия определяются как

η_KL(P_X, P_Y|X) = η_χ2(P_X, P_Y|X) = 0;

2. aX + bY = c п.н. для некоторых констант a, b, c ∈ R, таких что a = 0 и b = 0.

Тогда непосредственной проверкой легко убедиться, что ρ(X; Y )=1, откуда по-

лучаем η_KL(P_X , P_Y|X ) = η_χ2 (P_X , P_Y|X ) = 1, поскольку определения 3, (23) и п. 7

предложения 3 справедливы для общих случайных величин (см. [7, формулы (9)

и (13)]);

3. Существует совместная плотность распределения P_X,Y относительно меры Ле-

бега на R². Если X и Y независимы, то η_KL(P_X, P_Y|X) = η_χ2(P_X, P_Y|X) = 0,

поскольку п. 2 предложения 3 справедлив в общем случае. Поэтому будем пред-

полагать, что X и Y зависимы.

Нас будет интересовать последний невырожденный случай. Для простоты будем

также предполагать, что X и Y имеют нулевое среднее. Тогда совместное распре-

деление величин X и Y можно представить в “инновационном виде”: Y = γX + W

для некоторой константы γ = 0 и гауссовской случайной величины W с нулевым

средним и ненулевой дисперсией, не зависящей от X. Так как для любой плотности

распределения R_X справедливо D_f (R_X ∥ P_X ) = D_f (R_γX ∥ P_γX ), то η_KL(P_X , P_Y|X ) =

= η_KL(P_γX, PY |γX) и η_χ2(P_X, PY |X) = η_χ2(P_γX, PY |γX) (где R_γX - производная плот-

ность распределения, соответствующая R_X ). Поэтому без ограничения общности

положим γ = 1 и будем рассматривать классическую модель аддитивного белого

гауссовского шума (АБГШ) [41, гл. 9]:

Y = X + W, X ⊥⊥ W,

(52)

где входом является X ∼ N (0, σ2X ) с σ2X > 0 (т.е. X имеет гауссовскую плотность

распределения P_X со средним 0 и дисперсией σ2X ), гауссовским шумом является

W ∼ N(0,σ2W) с σ2W > 0, причем X и W независимы. Это соотношение также

задает условные плотности распределения

{

}

P_Y|X =

PY|X=x = N(x, σ2W ) : x ∈ R

и маргинальную плотность распределения P_Y = N (0, σ2X + σ2W ).

Напомним, что для любой пары функций плотности распределения относительно

меры Лебега Leb на R их КЛ- и χ²-дивергенции определяются (аналогично (3) и (4))

как

⎧∫

⎪

⁽R_X(x)⁾

⎨

R_X(x)log

d Leb(x),

S_X(x)

D(R_X ∥ S_X ) ≜

(53)

⎪

Leb({x ∈ R : R_X(x) > 0, S_X(x) = 0}) = 0,

⎩

+∞

в противном случае,

⎧∫

⎪

(R_X (x) - S_X (x))²

⎨

d Leb(x),

S_X(x)

χ²(R_X ∥S_X) ≜

(54)

⎪

Leb({x ∈ R : R_X (x) > 0, S_X (x) = 0}) = 0,

⎩

+∞

в противном случае,

где используются интегралы Лебега и приняты соглашения 0 log(0/t) = 0 для любых

t ≥ 0 (следуя соображениям непрерывности) и (0 - 0)²/0 = 0. Для совместно гаус-

совской плотности распределения P_X,Y , описанной в (52), с учетом определений (53)

и (54) коэффициенты сжатия для КЛ- и χ²-дивергенций имеют вид (см. (17) и (22))

D(R_Y ∥ P_Y )

η_KL(P_X, P_Y|X) =

sup

(55)

RX: 0<D(RX ∥PX )<+∞ D(RX^∥PX⁾

χ²(R_Y ∥P_Y )

η_χ2 (P_X, P_Y|X) =

sup

(56)

χ²(R_X ∥P_X)

RX: 0<χ²(RX ∥PX )<+∞

где супремумы берутся по всем плотностям распределения R_X (отличающихся от P_X

на множестве ненулевой меры Лебега)⁶, а через R_Y обозначена маргинальная плот-

ность распределения для Y после прохождения R_X через модель АБГШ P_Y|X .

В частности, R_Y = R_X ∗ P_W , где P_W = N (0, σ2W ), а ∗ означает операцию сверт-

ки. Далее, определим коэффициент сжатия для КЛ-дивергенции при ограничении

на среднюю мощность (или ограничении на второй момент) p ≥ σ2X как

D(R_Y ∥ P_Y )

η(p)KL(P_X, P_Y|X) ≜

sup

(57)

D(R_X ∥ P_X )

RX: ERX [X²]≤p

0<D(RX ∥PX)<+∞

где супремум берется по всем плотностям распределения R_X , удовлетворяющим

ограничению на среднюю мощность ERX[X²] ≤ p. Отметим, что при p = +∞ полу-

чаем стандартный коэффициент сжатия из (55).

Из литературы хорошо известно, что η_KL(P_X, P_Y|X) = η_χ2(P_X, P_Y|X) для сов-

местно гауссовской плотности распределения P_X,Y , определенной в (52). Например,

в [2, теорема 7] этот результат доказан в контексте теории инвестиционного портфе-

ля, в [81, c. 2] доказано его обобщение в контексте гауссовской гиперсжимаемости,

а в [78, §5.2, п. 5] он доказан в попытке аксиоматизации η_KL. В то время как до-

казательства в [2, теоремы 6 и 7; 78, § 5.2, п. 5] используют характеризацию η_KL

через взаимную информацию (18) (см. [7, теорема 4]), в § 5 мы даем альтернативное

доказательство этого результата, непосредственно использующее определение η_KL

через КЛ-дивергенцию в (55). При этом наше доказательство также показывает,

что η(p)KL(P_X , P_Y|X ) равно η_χ2 (P_X , P_Y|X ) для любого p ∈ [σ2X , ∞]. Хотя этот послед-

ний результат вытекает из нашего доказательства, ранее в литературе, насколько

нам известно, он не встречался. Формально этот результат представляет следующая

Теорема 5 (гауссовские коэффициенты сжатия). Для заданной совместно га-

уссовской плотности распределения P_X,Y , определенной в (52), с маргинальной

плотностью распределения P_X = N(0, σ2X) на входе и условными плотностями

{

}

распределения P_Y|X =

PY|X=x = N(x, σ2W ) : x ∈ R

, такими что σ2X, σ2W > 0,

⁶ Если P_X - общая вероятностная мера, а P_Y|X - марковское ядро между двумя измеримыми

пространствами, то коэффициенты сжатия для КЛ- и χ²-дивергенций определяются в точности как

в (17) и (22) с помощью определений КЛ- и χ²-дивергенций с позиций теории меры [7, § 2]. В (55)

при оптимизации по всем вероятностным мерам R_X на R (с борелевской σ-алгеброй) из ограниче-

ния D(R_X ∥ P_X ) < +∞ вытекает, что R_X должна быть абсолютно непрерывной относительно гаус-

совского распределения P_X , см. [38, п. 1.6]. Следовательно, супремум в (55) можно брать по всем

плотностям распределения R_X , таким что 0 < D(R_X ∥ P_X ) < +∞. То же самое относится и к (56).

следующие величины эквивалентны:

σ2X

η_KL(P_X, P_Y|X) = η(p)KL(P_X, P_Y|X) = η_χ2 (P_X, P_Y|X) =

σ2X + σ²

где наложено ограничение на среднюю мощность p ≥ σ2X .

Как уже сказано, мы доказываем этот результат в § 5. В отличие от теоремы 5,

где η_KL(P_X , P_Y|X ), η(p)KL(P_X , P_Y|X ) и η_χ2 (P_X , P_Y|X ) могут быть строго меньше 1, ко-

эффициенты сжатия для КЛ- и χ²-дивергенций для марковского ядра АБГШ P_Y|X

(т.е. в условиях определения 5) равны 1 вне зависимости от того, накладываются ли

ограничения на второй момент (см. [6, § 1.2; 82, § 1]).

3.4. Предпорядок меньшего искажения и операторная выпуклость. Последний

наш основной результат состоит в эквивалентной характеризации предпорядка мень-

шего искажения на стохастических матрицах, обобщающей результат предложе-

ния 6. Начнем с определения предпорядка меньшего искажения. В постановке с

конечным алфавитом из п. 2.1 рассмотрим случайную величину X ∈ X на вхо-

де и две случайные величины Y

∈ Y и Z ∈ Z на выходе, где Z ≜ {1,...,|Z|},

2 ≤ |Z| < +∞.

Определение 6 (предпорядок меньшего искажения [20]). Пусть PY |X = W ∈

∈ P_Y|X и P_Z|X = V ∈ P_Z|X - две стохастические по строкам матрицы с одним

алфавитом на входе X , т.е. с одинаковым числом строк. Будем говорить, что P_Y|X

менее искажающая, чем P_Z|X, и обозначать это через P_Y|X ≽_ln P_Z|X, если

∀R_X , P_X ∈ P_X , D(R_X W ∥ P_X W ) ≥ D(R_X V ∥ P_X V ).

Непосредственной проверкой легко убедиться, что определение 6 задает предпо-

рядок на стохастических матрицах⁷. Более того, из этого определения следует, что

пара вероятностных мер R_X W и P_X W всегда “более различима”, чем пара R_X V

и P_XV , что в действительности интуитивно соответствует тому, что W “менее иска-

жающая”, чем V (если рассматривать их как стохастические ядра). Имеется несколь-

ко других эквивалентных описаний отношения ≽_ln, например, через кодирование

каналов [20, определение B, предложение 2], взаимную информацию [20, предложе-

ни 2] и функционал ван Дейка [84, теорема 2]. Подробнее о предпорядке меньшего

искажения см. работу [83, пп. I-B, I-D, II-A, IV] и библиографию в ней.

В [7, § 6] показано, что если заданная стохастическая матрица мажорируется

в смысле предпорядка меньшего искажения матрицей канала со стиранием, то это

тесно связано с коэффициентом сжатия для КЛ-дивергенции для этой стохасти-

ческой матрицы. Напомним, что через E1-β ∈ PX∪{e}|X мы обозначаем матрицу

|X |-ичного канала со стиранием с вероятностью стирания 1 - β ∈ [0, 1] (согласно

определению (30)). Из [7, предложение 15] можно вывести, что для любой стохасти-

ческой матрицы P_Y|X ∈ P_Y|X справедливо

η_KL(P_Y|X) = min{β ∈ [0, 1] : E1-β ≽_ln P_Y|X},

(58)

где множество, по которому ведется минимизация, всегда содержит β = 1, посколь-

ку по сути E₀ - единичная матрица и E₀ ≽_ln P_Y|X . В [83, п. IV-A] отмечено, что

хотя (58) показывает, что η_KL характеризует мажорирование матрицами канала со

⁷ Как указано в [83, сноска 1], мы называем отношение меньшего искажения предпорядком, а не

частичным порядком, поскольку мы не рассматриваем классы эквивалентности стохастических

по строкам матриц, например, отождествляя стохастические по строкам матрицы, полученные

перестановкой столбцов.

стиранием в смысле меньшего искажения, формула (39) показывает, что и η_χ2 ха-

рактеризует это мажорирование. Отсюда возникает вопрос: характеризует ли χ²-ди-

вергенция предпорядок меньшего искажения в общем случае? В [83, теорема 1] и [85,

теорема 1] на этот вопрос дается утвердительный ответ с помощью характеризации

отношения ≽_ln через χ²-дивергенцию, обобщая тем самым соотношение (39).

Вдохновляясь этими результатами, рассмотрим предложение 6 (см. [18, теоре-

ма 1]), показывающее, что η_KL(P_Y|X ) = η_f (P_Y|X ) для всех нелинейных оператор-

но выпуклых функций f (определенных в п. 6.1). Как и выше, отсюда возникает

вопрос: характеризуют ли нелинейные операторно выпуклые f-дивергенции пред-

порядок меньшего искажения в общем случае? Следующая теорема отвечает на

этот вопрос, обобщая как предложение 6, так и [83, теорема 1], и показывая, что

нелинейные операторно выпуклые f-дивергенции также характеризуют предпоря-

док меньшего искажения.

Теорема 6 (эквивалентные характеризации отношения ≽_ln). Рассмотрим про-

извольную нелинейную операторно выпуклую функцию f : (0, ∞) → R, такую что

f (1) = 0. Тогда для любых стохастических матриц P_Y|X = W ∈ P_Y|X и P_Z|X =

= V ∈ P_Z|X с одинаковым алфавитом на входе X отношение PY |X ≽_ln P_Z|X имеет

место тогда и только тогда, когда

∀R_X , P_X ∈ P_X , D_f (R_X W ∥ P_X W ) ≥ D_f (R_X V ∥ P_X V ).

Теорема 6 доказана в п. 6.2 с использованием техники из [18]. Хорошо известная

t^α - 1

теорема Лёвнера- Хайнца утверждает, что функции f(t) = t log(t) и f(t) =

α-1

для любого α ∈ (0, 1) ∪ (1, 2] являются операторно выпуклыми (см., например, [86,

теорема 2.6; 87, теоремы V.2.5 и V.2.10, упражнения V.2.11 и V.2.13], и можно приме-

нить свойство аффинного преобразования из п. 6.1). Следовательно, одним классом

f-дивергенций, удовлетворяющих условиям теоремы, являются дивергенции Хел-

лингера порядка α ∈ (0, 2], где случаи α = 1 и α = 2 отвечают КЛ- и χ²-диверген-

циям соответственно.

Теперь в качестве примера применения теоремы 6 докажем обобщение так назы-

ваемого СНОД Самородницкого. Следуя изложению в [7, п. 6.2], рассмотрим дис-

кретные случайные величины с конечными множествами значений U ∈ U, Xn1 =

= (X₁, . . . , X_n) и Yn1 = (Y₁, . . . , Y_n), где X_i ∈ X_i и Y_i ∈ Y_i для всех i ∈ {1, . . . , n},

а n ∈ N \ {0}. Для заданных стохастических матриц PYi|Xi ∈ PYi|Xi^,i ∈ {1,...,n},

задающих условные распределения каждой из Y_i при заданном X_i, пусть условное

распределение Yn1 ∈ Yⁿ = Y₁ × . . . × Y_n при заданном Xn1 ∈ Xⁿ = X₁ × . . . × X_n

задается произведением стохастических матриц P_Y n

|Xn1 ∈ PYn|Xn:

P_Y n

(59)

|Xn1 = PY1|X1^⊗PY2|X2^⊗...⊗PYn|Xn^,

где через ⊗ обозначено кронекерово (или тензорное) произведение. Заметим, что

такие P_Y n

|Xⁿ известны как стохастические ядра без памяти (см., например, [41,₁

формула (7.27)]). Определим коэффициент сжатия стохастической матрицы PYi|Xi

для любой f-дивергенции (см. определение 5) как

η_i ≜ η_f (P_Y

(60)

i|Xi)

для любого i ∈ {1, . . . , n}. В то время как СНОД для P_Y n|Xn характеризуется коэф-1

фициентом сжатия η_f (P_Y n|Xn), хотелось бы получить ослабленный вариант этого1

СНОД через “однобуквенные” коэффициенты сжатия {η_i : i ∈ {1, . . . , n}}.

Чтобы проиллюстрировать одно такое тензоризованное СНОД, предположим,

что η_i = η для всех i ∈ {1, . . . , n}, и зафиксируем произвольную нелинейную опера-

торно выпуклую функцию f : (0, ∞) → R, такую что f(1) = 0. С помощью предло-

жения 6 непосредственной проверкой легко убедиться, что утверждения [7, теоре-

ма 5 и следствие 6] справедливы для любой f-дивергенции с нелинейной операторно

выпуклой функцией f (а не только для КЛ-дивергенции). В результате из [7, след-

ствие 6] вытекает граница тензоризации

η_f (P_Y n

|Xⁿ) ≤ 1 - (1 - η)ⁿ,

(61)

которую можно считать аналогом п. 5 предложения 3 для коэффициентов сжатия

стохастических матриц. Таким образом, для любой пары вероятностных мер на вхо-

де R_Xn,PXn

∈ P_Xn имеется тензоризованное СНОД

D_f (R_Y n

∥P_Yn

) ≤ (1 - (1 - η)ⁿ)D_f(R_Xn

∥P_Xn),

(62)

где R_Y n

=R_Xn

P_Y n

|Xn1 ∈ PYn и PYn1 = PXn1PYn1|Xn1 ∈ PYn - вероятностные меры на

выходе после прохождения R_Xn

и P_Xn

через P_Y n|Xn соответственно. Аналогично,1

для любого совместного распределения P_U,Xn, такого что U → Xn1 → Yn1 образуют

цепь Маркова, имеется тензоризованное СНОД (см. (8) и (38))

) ≤ (1 - (1 - η)ⁿ)I_f(U;Xn1 ).

(63)

If (U;

Однако, как указано в [7, п. 6.2], “можно было бы указать более сильные тензо-

ризованные границы, если бы мы обладали лучшим знанием” о парах (R_Xn

,P_Xn)

или о распределении P_U,Xn. В этом смысле следующая теорема дает более точные

границы на D_f (R_Y n

∥P_Yn

) и I_f(U;Yn1) через однобуквенные коэффициенты сжа-

тия {η_i : i ∈ {1, . . . , n}} и величины, представляющие “среднюю” f-дивергенцию

на входе и “среднюю” взаимную f-информацию, содержащиеся в подмножествах

случайной величины Xn1, соответственно.

Теорема 7 (обобщенное СНОД Самородницкого). Рассмотрим произвольную

нелинейную операторно выпуклую функцию f : (0, ∞) → R, такую что f(1) = 0.

Пусть U ∈ U, Xn1 ∈ Xⁿ и Yn1 ∈ Yⁿ - дискретные случайные величины с заданной

стохастической матрицей-произведением P_Y n

|Xn1

∈ P_Yn_|Xn из (59). Пусть S -

случайное подмножество множества {1, . . . , n}, полученное независимым выбором

каждого элемента i ∈ {1, . . . , n} с вероятностью η_i (заданной в (60)), и пусть S

не зависит от (U, Xn1, Yn1). Тогда для любой пары вероятностных мер на входе

R_Xn

,P_Xn

∈ P_Xn имеет место неравенство

(

)

∑

D_f

R_Y n

∥P_Yn

≤

P_S(T)D_f(RXT ∥PXT ),

(64)

T⊆{1,...,n}

где P_S - распределение вероятностей для S, X_T ≜ {X_k : k ∈ T } для любого под-

множества T ⊆ {1, . . ., n}, D_f (RX∅ ∥PX∅) = 0, R_Y n

=R_Xn

P_Y n

|Xn1 ∈ PYn и PYⁿ =₁

= P_Xn

P_Y n|Xn1

∈ P_Yn. Аналогично, для любого совместного распределения P_U,Xn,

такого что U → Xn1 → Yn1 образуют цепь Маркова,

∑

) ≤ I_f(U;X_S,S) =

P_S(T)I_f (U; X_T ),

(65)

If (U;

T⊆{1,...,n}

где I_f (U; X_∅) = 0. Более того, если η_i = η для всех i ∈ {1, . . . , n}, то

∑(n)

)≤

η^k(1 - η)^n-kI_k,

(66)

If (U;

k=0

где для каждого k ∈ {0, . . . , n} величина I_k определяется как “средняя” взаимная

f-информация, содержащаяся в подмножествах Xn1 мощности k:

)-1

∑

⁽n

Ik ≜

If (U; XT ).

T⊆{1,...,n}

|T|=k

Теорема 7 будет доказана в п. 6.3 с помощью теоремы 6, следуя технике доказа-

тельства из [7]. Случай КЛ-дивергенции в теореме 7 был впервые доказан Самород-

ницким в [88] с помощью техники линейного программирования при доказательстве

частного случая гипотезы Куртада -Кумара из [89]. К ее нынешнему виду она бы-

ла приведена в [7, теорема 20, замечание 6], где также было дано более простое

доказательство. Наш результат в теореме 7 обобщает этот случай КЛ-дивергенции

на все нелинейные операторно выпуклые f-дивергенции (включая, например, все

дивергенции Хеллингера порядка α ∈ (0, 2], как отмечалось выше). Заметим также,

что случай КЛ-дивергенции имеет и другие приложения, такие как усиление леммы

Гербер (см. [90, п. 2.1]) в [7, замечание 5]. И наконец, как показано в [7, замечание 4],

если η_i = η для всех i ∈ {1, . . . , n} в теореме 7, то аппроксимация распределения

binomial(n, η) в (66) с математическим ожиданием nη дает

)≲I_nη

(67)

If (U;

для любой цепи Маркова U → Xn1 → Yn1; это показывает, что из Yn1 можно извлечь

лишь информацию об U, содержащуюся в подмножествах Xn1 мощности, ограничен-

ной величиной nη.

§ 4. Доказательства линейных границ между коэффициентами сжатия

В этом параграфе мы докажем теоремы 3 и 4. Основная идея доказательства со-

стоит в оценивании сверху и снизу f-дивергенций в числителе и знаменателе опреде-

ления 2, соответственно, через χ²-дивергенции. С этой целью в п. 4.1 мы приведем

несколько простых границ между f-дивергенциями и χ²-дивергенцией, а в п. 4.2

докажем основные результаты.

4.1. Границы на f-дивергенции через χ²-дивергенцию. Вначале приведем грани-

цы между КЛ- и χ²-дивергенцией. Для вывода нашей нижней границы на КЛ-дивер-

генцию нам понадобится следующее “зависящее от распределений уточнение нера-

венства Пинскера”, доказанное в [91].

Лемма 1 (зависящее от распределений неравенство Пинскера [91, теорема 2.1]).

Для любых вероятностных мер R_X, P_X ∈ P_X справедливо неравенство

(

)

D(R_X ∥ P_X ) ≥ ϕ maxmin{PX (A), 1 - PX (A)} ∥RX - PX ∥2TV ,

A⊆X

где функция ϕ: [0, 1/2] → R определяется как

⎧

⎨

⁽1-p⁾

log

p ∈ [0,1/2),

ϕ(p) ≜

1 - 2p

(68)

⎩

p = 1/2.

Более того, в этом неравенстве участвует оптимальная зависящая от распреде-

лений константа в том смысле, что для любого фиксированного P_X ∈ P_X

(

)

D(R_X ∥ P_X )

inf

= ϕ maxmin{PX (A), 1 - PX (A)} .

RX∈PX \{PX} ∥R_X - P_X ∥^2TV

A⊆X

Напомним (см., например, [41, лемма 11.6.1]), что неравенство Пинскера утвер-

ждает, что для любых R_X , P_X ∈ P_X

D(R_X ∥ P_X ) ≥ 2 ∥R_X - P_X ∥^2TV .

(69)

Следовательно, лемма 1 точнее, чем неравенство Пинскера, поскольку имеет место

неравенство 0 ≤ maxmin{PX (A), 1 - PX (A)} ≤ 1/2, и поэтому

A⊆X

(

)

ϕ maxmin{PX (A), 1 - PX (A)}

≥ 2,

(70)

A⊆X

где равенство имеет место тогда и только тогда, когда

maxmin{PX (A), 1 - PX (A)} =

A⊆X

(см. [91, § III]). Следующая лемма использует лемму 1 для оценки КЛ-дивергенции

снизу через χ²-дивергенцию.

Лемма 2 (нижняя граница КЛ-дивергенции). Для любых вероятностных мер

R_X, P_X ∈ P_X справедливо

(

)

ϕ maxmin{PX (A), 1 - PX (A)} minPX(x)

A⊆X

x∈X

D(R_X ∥ P_X ) ≥

χ²(R_X ∥P_X),

где функция ϕ: [0, 1/2] → R определена в (68).

Доказательство. Если R_X = P_X или minPX(x) = 0, то неравенство выпол-

x∈X

нено тривиальным образом. (Заметим, что если minPX(x) = 0 и PX(x∗) = 0 <

x∈X

< R_X(x^∗) для некоторого x^∗ ∈ X, то D(R_X ∥P_X) = χ²(R_X ∥P_X) = +∞, и можно

считать, что неравенство выполнено.) Итак, без ограничения общности будем пред-

полагать, что R_X = P_X и P_X ∈ P^◦X .

Так как χ²-дивергенция похожа на взвешенную ℓ²-норму, вначале применим лем-

му 1 и получим нижнюю границу

(

⁾∥R_X - P_X∥²¹

D(R_X ∥ P_X ) ≥ ϕ maxmin{PX (A), 1 - PX (A)}

(71)

A⊆X

где используется характеризация расстояния по вариации через ℓ¹-норму, приведен-

ная в (2). Далее с учетом (4) заметим, что



∑



RX(x) - P_X(x)

∥R_X - P_X ∥_∞

χ²(R_X ∥P_X) =

|R_X (x) - P_X (x)|



∥R_X - P_X ∥₁ .



≤

P_X(x)

minPX(x)

x∈X

Отсюда следует

∥R_X - P_X∥²¹

∥R_X - P_X∥₁

≥ χ²(R_X ∥P_X)

≥

minPX(x)

∥R_X - P_X ∥_∞

x∈X

∥S_X - Q_X∥₁

≥ χ²(R_X ∥P_X) min

SX,QX∈PX

∥S_X - Q_X ∥_∞

SX=QX

= 2χ²(R_X ∥P_X),

(72)

где использован тот факт, что

∥S_X - Q_X ∥₁

min

= 2.

(73)

SX,QX∈PX

∥S_X - Q_X∥_∞

SX=QX

Для доказательства (73) заметим, что для любых S_X , Q_X ∈ P_X (см., например,

[92, лемма 1])

∥S_X - Q_X∥_∞ ≤

∥S_X - Q_X ∥₁ ,

поскольку (S_X - Q_X )1 = 0, и это неравенство на самом деле может быть точ-

ным. Например, выберем любую вероятностную меру Q_X ∈ P^◦X и положим x₀ =

= argmin Q_X(x). Затем возьмем S_X ∈ P_X , такую что S_X(x₀) = Q_X(x₀)+δ для неко-

x∈X

торого достаточно малого δ > 0, S_X(x₁) = Q_X(x₁) - δ для некоторого x₁ ∈ X \ {x₀}

и S_X(x) = Q_X(x) для всех остальных x ∈ X \ {x₀,x₁}. При таком выборе S_X и Q_X

получаем ∥S_X - Q_X ∥_∞ = δ =

∥S_X - Q_X∥₁.

Наконец, объединяя (71) и (72), получаем

(

)

ϕ maxmin{PX (A), 1 - PX (A)} minPX(x)

A⊆X

x∈X

D(R_X ∥ P_X ) ≥

χ²(R_X ∥P_X),

что завершает доказательство. ▴

Заметим, что если применить (70) к лемме 2, или, что то же самое, использовать

стандартное неравенство Пинскера (69) вместо леммы 1 в доказательстве леммы 2,

то получим хорошо известное более слабое неравенство (см., например, [34, форму-

ла (338)])

D(R_X ∥ P_X ) ≥ minPX(x)χ2(RX ∥PX)

(74)

x∈X

для любых R_X , P_X ∈ P_X .

Стоит отметить, что систематическим методом вывода оптимальных не зави-

сящих от распределений границ между любыми двумя f-дивергенциями является

метод совместной области значений Харремоеса - Вайды [93]⁸. Однако для вывода

нижних границ на КЛ-дивергенцию через χ²-дивергенцию мы не можем исполь-

зовать эту технику, поскольку таких общих нижних границ не существует (когда

оба распределения на входе изменяются) [38, п. 7.3]. С другой стороны, зависящие

от распределений границы легко можно находить, используя подходящую технику

в каждом конкретном случае. Наше доказательство леммы 2 использует один из

таких подходов, основанный на неравенстве Пинскера.

Хотелось бы попытаться улучшить лемму 2, используя лучшие нижние грани-

цы на КЛ-дивергенцию через расстояние по вариации. Так, наилучшей возможной

границей снизу на КЛ-дивергенцию через расстояние по вариации является ниж-

няя граница их совместной области значений Харремоеса - Вайды (см. [93, рис. 1]).

Эта нижняя граница, известная как точная нижняя граница Вайды, дает наимень-

шую возможную КЛ-дивергенцию для любого значения расстояния по вариации

и полностью описывается параметрической формулой в [94, теорема 1] (см. так-

же [38, п. 7.2.2]). Хотя точная нижняя граница Вайды дает нелинейную границу

снизу на КЛ-дивергенцию через χ²-дивергенцию, эту нижнюю границу трудно при-

менить в сочетании с леммой 3 (приведенной ниже) для вывода нелинейной верхней

⁸ “Не зависящей от распределений” границей между двумя f-дивергенциями называется граница,

зависящая от распределений на входе только через соответствующие f-дивергенции.

границы на отношение КЛ-дивергенций через отношение χ²-дивергенций (см. до-

казательство теоремы 4 в п. 4.2). По этой причине мы прибегаем к использованию

простых линейных границ между КЛ- и χ²-дивергенцией, что приводит к линейной

границе в теореме 4.

Другой, более тонкой причиной использования χ²-дивергенции для доказатель-

ства линейной нижней границы на КЛ-дивергенцию явлвется возможность приме-

нить лемму 1. Хотя неравенство Пинскера и является наилучшей нижней границей

на КЛ-дивергенцию через квадрат расстояния по вариации по всем парам вероят-

ностных мер на входе (см., например, [94, формула (9)]), коэффициенты сжатия

в п. 3.2 имеют фиксированную маргинальную вероятностную меру P_X . Поэтому

можно использовать зависящее от распределений улучшение неравенства Пинскера

из леммы 1 для вывода более точной границы, чем (74).

Теперь приведем границу сверху на КЛ-дивергенцию через χ²-дивергенцию, ко-

торая тривиально следует из неравенства Йенсена. Эта граница была выведена в

контексте изучения эргодичности цепей Маркова в [95] и затем повторно получе-

на при исследовании неравенств, связанных с f-дивергенциями (см. [96, 97], а так-

же [98, теорема 5]).

Лемма 3 (верхняя граница КЛ-дивергенции [95]). Для заданных вероятност-

ных мер P_X , R_X ∈ P_X справедливо неравенство

(

)

D(R_X ∥ P_X ) ≤ log

1 + χ²(R_X ∥P_X)

≤ χ²(R_X ∥P_X).

Доказательство. Для полноты изложения приведем доказательство леммы

(см. [96]). Предположим без ограничения общности, что не существует x ∈ X , такого

что R_X (x) > P_X (x) = 0. (Если это не так, то χ²(R_X ∥ P_X ) = +∞, и неравенство

тривиальным образом выполнено.) Итак, рассматривая в качестве X носитель P_X ,

полагаем, что P_X ∈ P^◦X (гарантируя тем самым, что все дальнейшие величины будут

конечными). Так как функция x → log(x) выпукла вверх, то из неравенства Йенсена

получаем

)

∑

(∑

⁽R_X(x)⁾

R_X(x)²

D(R_X ∥ P_X ) =

R_X(x)log

≤ log

P_X(x)

x∈X

(

)

= log

1 + χ²(R_X ∥P_X)

≤ χ²(R_X ∥P_X),

где первое равенство следует из (3), третье - из (4) после некоторых преобразований,

а последнее - из хорошо известного неравенства log(1 + x) ≤ x для всех x > -1. ▴

Отметим, что первая нелинейная граница в лемме 3 покрывает метод совместной

области значений Харремоеса - Вайды [38, п. 7.3]. Хотя она и точнее, чем вторая ли-

нейная граница, в доказательстве теоремы 4 (как объяснялось выше) мы используем

именно вторую. Вторая граница также была получена в [99, лемма 6.3].

Теперь приведем границы между общими f-дивергенциями и χ²-дивергенцией.

Для вывода нашей нижней границы на f-дивергенции вначале сформулируем обоб-

щение неравенства Пинскера для f-дивергенций, доказанное в [79].

Лемма

(обобщенное неравенство Пинскера для f-дивергенции [79, теоре-

ма 3]). Пусть задана выпуклая функция f : (0, ∞) → R, трижды дифференцируемая

в единице, такая что f(1) = 0 и f^′′(1) > 0, удовлетворяющая условию

(

)

(

)

f^′′′(1)

f^′′(1)

f (t) - f^′(1)(t - 1)

(t - 1)

≥

(t - 1)²

(75)

3f^′′(1)

для любого t ∈ (0, ∞). Тогда для любых R_X , P_X ∈ P_X справедливо

D_f (R_X ∥P_X) ≥ 2f^′′(1)∥R_X - P_X∥^2TV .

Более того, в этом неравенстве участвует оптимальная константа в том смыс-

ле, что

D_f (R_X ∥P_X)

inf

= 2f^′′(1).

RX,PX ∈PX

∥R_X - P_X∥²

RX=PX

Заметим, что функция f(t) = t log(t) удовлетворяет условиям леммы 4, причем

f^′′(1) = 1, как показано в Приложении E; отсюда вытекает стандартное неравенство

Пинскера (69). Поскольку условие (75) может быть нелегко проверить для других

f-дивергенций, в [79, следствие 4] приведены достаточные условия для неравен-

ства (75). (Эти условия можно проверить и получить вариант неравенства Пинскера

для, например, дивергенций Реньи порядка α ∈ (0, 1) [79, следствие 6].) В следую-

щей лемме с помощью леммы 4 устанавливается нижняя граница на определенные

f-дивергенции через χ²-дивергенцию, что соответствует лемме 2 (или, точнее, нера-

венству (74), так как оно вытекает из стандартного неравенства Пинскера).

Лемма 5 (нижняя граница f-дивергенции). Пусть задана выпуклая функция

f : (0,∞) → R, трижды дифференцируемая в единице, такая что f(1) = 0 и

f^′′(1) > 0, удовлетворяющая условию (75) для любого t ∈ (0, ∞). Тогда для любых

вероятностных мер R_X ∈ P_X и P_X ∈ P^◦X справедливо неравенство

D_f (R_X ∥P_X) ≥ f^′′(1)minPX(x)χ2(RX ∥PX).

x∈X

Доказательство. Будем следовать доказательству леммы 2, внося необходи-

мые изменения. Предположим без ограничения общности, что R_X = P_X . Обобщен-

ное неравенство Пинскера для f-дивергенций из леммы 4 дает

f^′′(1)

D_f (R_X ∥P_X) ≥

∥R_X - P_X∥²¹ ,

используя характеризацию расстояния по вариации через ℓ¹-норму, данную в (2).

Требуемый результат получается применением (72) к этому неравенству. ▴

Заметим, что если в лемме 5 положить f(t) = t log(t), получим неравенство (74).

Наконец, приведем верхнюю границу на некоторые f-дивергенции через χ²-ди-

вергенцию, аналогичную лемме 3. Эта верхняя граница была доказана в [8, лем-

ма A.2] в предположении, что f дифференцируема, но как мы увидим ниже, нужно

лишь проверить дифференцируемость в единице. (Было бы поучительно еще раз

посмотреть на доказательство леммы 3, чтобы увидеть, как нижеследующее дока-

зательство обобщает ее на f-дивергенции.)

Лемма 6 (верхняя граница f-дивергенции [8, лемма A.2]). Пусть дана выпук-

лая функция f : (0, ∞) → R, дифференцируемая в единице, такая что f(1) = 0 и

f (0) < ∞, и пусть разностное отношение g : (0, ∞) → R, определяемое как

f (t) - f(0)

g(t) =

выпукло вверх. Тогда для любых вероятностных мер R_X , P_X ∈ P_X справедливо

неравенство

D_f (R_X ∥P_X) ≤ (f^′(1) + f(0))χ²(R_X ∥P_X).

Доказательство. Для полноты изложения приведем доказательство из [8].

Как и в доказательстве леммы 3, можно предполагать без ограничения общности,

что P_X ∈ P^◦X , так что все рассматриваемые далее величины конечны. Тогда имеет

место следующая цепочка равенств и неравенств:

∑

⁽R_X(x)⁾

D_f (R_X ∥P_X) =

P_X(x)f

P_X(x)

x∈X

)

∑

⁽R_X(x)⁾

(∑

R_X(x)²

= f(0) +

R_X(x)g

≤ f(0) + g

P_X(x)

x∈X

(

)

= f(0) + g

1 + χ²(R_X ∥P_X)

≤

(76)

≤ f(0) + g(1) + g^′(1)χ²(R_X ∥P_X) = (f^′(1) + f(0))χ²(R_X ∥P_X),

где во втором равенстве используется соглашение 0g(0) = 0, третье следует из нера-

венства Йенсена, так как функция g: (0, ∞) → R выпукла вверх, пятое также вы-

текает из выпуклости g: (0, ∞) → R, как показано в [100, п. 3.1.3], а последнее

неравенство справедливо, поскольку g(1) = -f(0) (так как f(1) = 0) и

g(1 + δ) + f(0)

f (1 + δ) + δf(0)

g^′(1) = lim

= lim

δ→0

δ(1 + δ)

(

)(

)

f (1 + δ)

= lim

f (0) + lim

=f′(1) + f(0),

δ→0 1 + δ

δ→0

что завершает доказательство. ▴

Заметим, что выражение (76) является аналогом более точной (нелинейной) гра-

ницы из леммы 3. Кроме того, отметим, что в лемме 6 можно использовать функцию

f(t)

g(t) =

(в предположении ее выпуклости вверх) вместо разностного отноше-

ния. Доказательство останется тем же, но с использованием константы f^′(1) вместо

f^′(1) + f(0). Однако мы для доказательства леммы 6 выбрали разностное отноше-

ние ввиду свойства аффинной инвариантности f-дивергенций (см. п. 2.1). Нетрудно

проверить, что величина f^′(1)+f(0) инвариантна относительно подходящих аффин-

ных сдвигов, что неверно для f^′(1). Также отметим, что константа f^′′(1) в лемме 5

инвариантна относительно соответствующих аффинных сдвигов.

4.2. Доказательства теорем 3 и 4. Напомним (см. начало п. 3.1), что мы рассмат-

риваем совместную вероятностную меру P_X,Y , состоящую из P_X ∈ P^◦X и P_Y|X =

= W ∈ P_Y|X, где P_Y = P_XW ∈ P^◦Y. Теперь с помощью лемм 2 и 3 из п. 4.1 мы

можем доказать теорему 4.

Доказательство теоремы 4. Для любой вероятностной меры R_X ∈ P_X,

такой что R_X = P_X , имеем

D(R_X W ∥ P_Y )

2χ²(R_XW ∥P_Y )

≤

(

)

D(R_X ∥ P_X )

ϕ maxmin{PX (A), 1 - PX (A)} minPX(x)χ2(RX ∥PX)

A⊆X

x∈X

в силу лемм 2 и 3. Переходя к супремуму по всем R_X = P_X в обоих частях неравен-

ства, получаем

2η_χ2 (P_X , P_Y|X

)

η_KL(P_X, P_Y|X) ≤

(

)

ϕ maxmin{PX (A), 1 - PX (A)} minPX(x)

A⊆X

x∈X

с учетом (17) и (22), что и завершает доказательство. ▴

Уместно сделать несколько замечаний. Во-первых, если в этом доказательстве

применить (74) вместо леммы 2, получим доказательство следствия 1.

Во-вторых, при доказательстве следствия 1 в [1, теорема 10] была также доказана

следующая более слабая граница сверху на η_KL(P_X, P_Y|X) (см. [1, теорема 9]):

η_KL(P_X, P_Y|X) ≤

η_χ2 (P_X, P_Y|X),

(77)

minPX(x)

x∈X

также независимо полученная в [8, формула III.19]. Наше доказательство соотно-

шения (77) в [1, теорема 9] использовало следующий в два раза худший вариант

неравенства (74) (см. [1, лемма 6]):

Q_X(x)

min

x∈X

D(S_X ∥ Q_X ) ≥

χ²(S_X ∥Q_X)

(78)

для всех S_X , Q_X ∈ P_X . Это неравенство вытекает из доказательства леммы 2 с ис-

пользованием границы ∥S_X - Q_X ∥_∞ ≤ ∥S_X - Q_X ∥₁ (не учитывающей тот факт, что

(S_X - Q_X )1 = 0) вместо (73) и последующим применением оценки (70) к получаю-

щейся нижней границе на КЛ-дивергенцию. В качестве альтернативы для полноты

изложения в Приложении F мы даем доказательство формулы (78) через диверген-

ции Брегмана (см. [1, лемма 6]). То, что границу (78) можно улучшить вдвое до

границы (74), было также указано в [34, замечание 33], где отмечалось, что наш ре-

зультат [1, теорема 9] (приведенный в (77)) можно улучшить вдвое, используя (74)

вместо (78). По-видимому, авторы работы [34] не заметили наш результат [1, теоре-

ма 10] (представленный в следствии 1), в котором в точности было приведено это

улучшение вдвое.

И наконец, отметим, что в [8, п. III-D] также приведены верхние границы на

η_KL(P_X, P_Y|X), использующие функцию ϕ: [0, 1/2] → R, что вытекает из улучшен-

ного неравенства Пинскера в [91]. Однако эти верхние границы выражены не через

η_χ2 (P_X, P_Y|X).

Теперь, объединяя результаты лемм 5 и 6 из п. 4.1, докажем теорему 3.

Доказательство теоремы 3. Условия теоремы 3 включают в себя все усло-

вия лемм 5 и 6. Следовательно, применяя леммы 5 и 6, для любой вероятностной

меры R_X ∈ P_X , такой что R_X = P_X , получаем

D_f (R_XW ∥P_Y )

(f^′(1) + f(0))χ²(R_X W ∥ P_Y )

≤

D_f (R_X ∥P_X)

f^′′(1)minPX(x)χ2(RX ∥PX)

x∈X

Переходя к супремуму по всем R_X = P_X в обеих частях этого неравенства, получаем

f^′(1) + f(0)

η_f (P_X, P_Y|X) ≤

η_χ2 (P_X, P_Y|X),

f^′′(1)minPX(x)

x∈X

где использовались определение 2 и соотношение (22), что и завершает доказатель-

ство. ▴

Отметим, что в [8, теорема III.4] приведена альтернативная линейная граница

сверху на η_f (P_X, P_Y|X) через η_χ2 (P_X, P_Y|X). Пусть f : (0, ∞) → R - дважды диффе-

ренцируемая выпуклая функция, такая что f(1) = 0 и f(0) < ∞, строго выпуклая

в единице и имеющая невозрастающую вторую производную. Если к тому же пред-

f(t) - f(0)

положить, что разностное отношение t →

выпукло вверх, то справедлива

следующая граница [8, теорема III.4]:

2(f^′(1) + f(0))

η_f (P_X, P_Y|X) ≤

η_χ2 (P_X, P_Y|X),

(79)

f^′′(1/p_⋆)

где p_⋆ = minPX(x). Следовательно, если функция f к тому же трижды диффе-

x∈X

ренцируема в единице, имеет f^′′(1) > 0 и удовлетворяет условию (75) для любого

t ∈ (0,∞), то можно усилить верхнюю границу теоремы 3 до

}

^{f^′(1) + f(0)

2(f^′(1) + f(0))

η_f (P_X, P_Y|X) ≤ min

η_χ2 (P_X, P_Y|X).

(80)

f^′′(1)p_⋆

f^′′(1/p_⋆)

Заметим, что наша граница из теоремы 3 точнее границы (79) тогда и только

тогда, когда

2(f^′(1) + f(0))

f^′(1) + f(0)

≥

⇐⇒

2f^′′(1)p_⋆ ≥ f^′′(1/p_⋆).

(81)

f^′′(1/p_⋆)

f^′′(1)p_⋆

Одной из функций, удовлетворяющих условиям теоремы 3 и неравенствам (79)

и (81), является f(t) = t log(t). Это и дает улучшение в следствии 1 (получаемом из

теоремы 3) по сравнению с неравенством (77) (получаемым из [8, теорема III.4]).

В качестве другого примера рассмотрим функцию

t^α - 1

f (t) =

α ∈ (0,2] \ {1},

α-1

задающую дивергенцию Хеллингера порядка α (см. п. 2.1). Непосредственными вы-

числениями нетрудно проверить, что эта функция удовлетворяет условиям теоре-

мы 3 и неравенству (79) (см. [79, следствие 6], [8, п. III-B, c. 3362]). В этом случае

наша граница из теоремы 3 точнее, чем (79), для всех дивергенций Хеллингера по-

рядка α, удовлетворяющих условию (81), т.е.

2f^′′(1)p_⋆ = 2αp_⋆ ≥ α(1/p_⋆)α-2 = f^′′(1/p_⋆) ⇐⇒ pα-1⋆ ≥

или, что равносильно, 0 < α ≤ 1 + (log(2)/ log(1/p_⋆)) (где α = 1 соответствует

КЛ-дивергенции - см. п. 2.1).

4.3. Эргодичность цепей Маркова. В этом пункте мы выведем из следствия 1

результат, иллюстрирующий одно из применений верхних границ на коэффициен-

ты сжатия совместных распределений через η_χ2(P_X, P_Y|X). Рассмотрим матрицу

примитивного марковского ядра W ∈ P_X|X на пространстве состояний X, задаю-

щую неприводимую и апериодическую (однородную по времени) дискретную цепь

Маркова с единственной стационарной вероятностной мерой P_X ∈ P^◦X , такой что

P_XW = P_X (см. [29, п. 1.3]). Для простоты предположим также, что W обрати-

ма (т.е. имеют место уравнения детального баланса P_X(x)[W]_x,y = P_X(y)[W]_y,x для

всех x, y ∈ X [29, п. 1.6]). Это означает, что матрица W самосопряжена относи-

тельно взвешенного скалярного произведения, задаваемого P_X, и все ее собствен-

ные значения 1 = λ₁(W ) > λ₂(W ) ≥ . . . ≥ λ_|X|(W ) > -1 вещественны. Через

μ(W ) ≜ max{|λ₂(W )|, |λ_|X|(W )|} ∈ [0, 1) обозначается модуль второго по абсолют-

ной величине собственного значения W (см. п. 2.3).

Так как эта цепь Маркова эргодична, то lim

R_XWⁿ = P_X для всех R_X ∈ P_X

n→∞

[29, теорема 4.9]. Отсюда lim

D(R_X Wⁿ ∥ P_X ) = 0 из непрерывности КЛ-диверген-

n→∞

ции [38, предложение 3.1]. Оценим скорость, с которой убывает это “расстояние до

стационарности” (измеряемое КЛ-дивергенцией). Наивный подход состоит в рекур-

сивном применении СНОД (15) для КЛ-дивергенции, что дает

D(R_X Wⁿ ∥ P_X ) ≤ η_KL(P_X , W )ⁿD(R_X ∥ P_X )

(82)

для всех R_X ∈ P_X и всех n ∈ N. С учетом (17) отсюда следует, что

lim sup η_KL(P_X , Wⁿ)ⁿ ≤ η_KL(P_X , W ),

(83)

n→∞

что оказывается довольно слабой границей на скорость в общем случае.

При больших n, поскольку R_X Wⁿ близка к P_X , интуитивно следует ожидать,

что D(R_X Wⁿ ∥ P_X ) ведет себя как χ²-дивергенция (см. (13) в п. 2.1), и это наводит

на мысль, что η_KL(P_X , Wⁿ) должна по порядку величины совпадать с η_χ2(P_X , W )ⁿ.

Это интуитивная догадка строго доказана в [17, § 6]. Действительно, когда μ(W )

строго больше модуля третьего по абсолютной величине собственного значения W ,

из [17, следствие 6.2] вытекает, что

D(R_X Wⁿ ∥ P_X )

lim

≤ μ(W )²

(84)

n→∞ D(R_X Wn-1 ∥ P_X )

для всех R_X ∈ P_X , таких что знаменатель всегда положителен. (Этот предел равен

либо 0, либо μ(W )².) Поэтому, используя сходимость по Чезаро и масштабирование,

получаем

D(R_X Wⁿ ∥ P_X )

⁽D(R_XWⁿ ∥P_X)

lim

= lim

≤ μ(W )²,

(85)

n→∞ D(R_X Wn-1 ∥ P_X )

n→∞ D(R_X ∥ P_X )

что позволяет предположить, что lim supηKL(PX, Wn)n ≤ μ(W)2. Следующий ре-

n→∞

зультат показывает, что это неравенство на самом деле точное.

Предложение 7 (скорость сходимости). Для любой неприводимой апериоди-

ческой обратимой цепи Маркова с ядром W ∈ P_X|X и стационарной вероятност-

ной мерой P_X ∈ P^◦X

lim

η_KL(P_X, Wⁿ)ⁿ = η_χ2(P_X, W) = μ(W)².

n→∞

Доказательство. Так как W обратима, а P_X - ее инвариантная мера, то

МДП

(√

)

(√

)-1

B = diag

P_X

W diag

P_X

симметрична и подобна W (см. определение (24)). Следовательно, W и B имеют

одинаковые собственные значения, и μ(W ) является вторым по величине сингуляр-

ным числом для B. Применяя предложение 2 и (23), получаем η_χ2(P_X , W ) = μ(W )²,

что доказывает второе равенство.

Аналогично, η_χ2 (P_X , Wⁿ) = μ(Wⁿ)², так как Wⁿ обратима для любого n ≥ 1.

Отсюда

η_χ2 (P_X, Wⁿ) = μ(Wⁿ)² = μ(W)2n = η_χ2(P_X, W)ⁿ,

(86)

где второе равенство справедливо, поскольку собственные значения Wⁿ являются

n-ми степенями собственных значений W. С учетом (86), п. 7 предложения 3 и

следствия 1 получаем

η_χ2 (P_X, W)

η_χ2 (P_X, W)ⁿ ≤ η_KL(P_X, Wⁿ) ≤

minPX(x)

x∈X

Остается извлечь корни n-й степени и перейти к пределу при n → ∞. ▴

Предложение 7 описывает хорошо понимаемое явление, что D(R_X Wⁿ ∥ P_X ) убы-

вает со скоростью, задаваемой величиной μ(W)² = η_χ2(P_X, W). В более широком

смысле оно показывает, что границы следствия 1 и теорем 3 и 4 полезны в режиме,

когда случайные величины X и Y слабо зависимы (например, X - начальное со-

стояние эргодической обратимой цепи Маркова, а Y - ее состояние после большого

числа шагов). В таком режиме эти границы довольно точны и превосходят границу

через η_TV в п. 7 предложения 5.

4.4. Тензоризация границ между коэффициентами сжатия. В отсутствии слабой

зависимости верхние границы следствия 1 и теорем 3 и 4 могут быть слабыми. На

самом деле, их можно считать сколь угодно слабыми, поскольку константы в этих

границах не тензоризуются в отличие от коэффициентов сжатия (последнее пока-

зано в п. 5 предложения 3). Например, если дана P_X,Y с X ∼ Bernoulli(1/2), то кон-

станта в верхней границе следствия 1 равна 1/ min P_X (x) = 2. Если вместо этого

x∈{0,1}

рассмотреть последовательность независимых и одинаково распределенных (н.о.р.)

согласно P_X,Y пар (X₁, Y₁), . . . , (X_n, Y_n), то константа в верхней границе следствия 1

равна 1/ min

P_Xn

(xn1) = 2ⁿ. Но поскольку η_KL(P_Xn

,P_Yn

|Xn1 ) = ηKL(PX^,PY |X⁾

xn1∈{0,1}ⁿ

и η_χ2 (P_Xn,PYn

|Xn1 ) = ηχ2(PX, PY |X) по свойству тензоризации из п. 5 предложе-

ния 3, то константа 2ⁿ

становится сколь угодно плохой с ростом n. Эту атаку на

следствие 1 с помощью н.о.р. пар частично позволяет отразить

Следствие 2 (тензоризованная КЛ-граница на коэффициенты сжатия). Если

пары (X₁, Y₁), . . . , (X_n, Y_n) н.о.р. с совместной вероятностной мерой P_X,Y , такой

что P_X ∈ P^◦X и P_Y ∈ P^◦Y, то

(

)

(

)

η_χ2

Xn1 , PYn1 |Xⁿ

η_KL

P_Xn

,P_Yn

|Xn1

≤

minPX(x)

x∈X

Доказательство. Это неравенство тривиальным образом вытекает из след-

ствия 1 и свойства тензоризации в п. 5 предложения 3. ▴

В контексте произведений распределений это следствие позволяет использовать

в верхней границе следствия

более точный множитель 1/minPX(x) вместо

(

)_n

x∈X

1/ min

P_Xn

(xn1) =

1/minPX(x)

. Аналогичные уточнения в этом контексте мож-

xn1∈Xⁿ

x∈X

но также сделать для констант в теоремах 3 и 4. Таким образом, тензоризация может

улучшить верхние границы в следствии 1 и теоремах 3, 4.

§ 5. Доказательство эквивалентности между гауссовскими коэффициентами сжатия

В этом параграфе мы докажем теорему 5. Напомним (см. п. 3.3), что мы рас-

сматриваем совместно гауссовские плотности распределения P_X,Y , заданные в (52),

с маргинальными плотностями распределения на входе P_X = N (0, σ2X ) и услов-

{

}

ными плотностями распределения P_Y|X =

PY|X=x = N(x, σ2W ) : x ∈ R

, где

σ2X, σ2W > 0. Пусть T - множество всех функций распределения на R с ограничен-

ным существенным носителем. Таким образом, R_X ∈ T тогда и только тогда, когда

существует C > 0, такая что R_X = R_X1[-C,C] почти всюду по мере Лебега, где через

1[-C,C] : R → {0, 1} обозначена индикаторная функция на [-C, C]:

^{1, x ∈ [-C, C],

1[-C,C](x) =

(87)

в противном случае.

Вначале докажем следующую полезную лемму.

Лемма

(характеризация η_KL через функции с ограниченным носителем).

Супремум в (55) можно ограничить на плотности распределения из множест-

ва T :

D(R_Y ∥ P_Y )

η_KL(P_X, P_Y|X) =

sup

RX∈T

D(R_X ∥ P_X )

D(RX ∥PX)<+∞

где R_Y

= R_X ∗ P_W для каждой плотности распределения R_X, P_W = N(0,σ2W),

а ограничение D(R_X ∥ P_X ) > 0 автоматически выполнено для любой R_X ∈ T , по-

скольку P_X = N (0, σ2X ).

Доказательство. Рассмотрим произвольную плотность распределения R_X,

такую что 0 < D(R_X ∥ P_X ) < +∞, и зададим соответствующую последовательность

функций плотности распределения

R(n)X = R_X1[-n,n]/C_n ∈ T ,

где C_n = ERX [1[-n,n](X)], индексы n ∈ N достаточно большие, так что C_n > 0, и

lim

C_n = 1. Заметим, что

n→∞

[

(

)

⁽R_X(X)^)]

R(n)X ∥P_X

ERX 1[-n,n](X)log

- log(C_n).

C_n

P_X(X)

Очевидно, что lim

1[-n,n] log(R_X/P_X) = log(R_X/P_X) поточечно R_X-п.н., а также



n→∞



1[-n,n] log(R_X/P_X)



≤ |log(R_X /P_X )| поточечно R_X -п.н., так что выполнено нера-

венство ERX[|log(R_X(X)/P_X(X))|] < +∞ (где конечность следует из того факта,

что D(R_X ∥ P_X ) < +∞). Отсюда по теореме о мажорируемой сходимости получаем

(

)

lim

R(n)X ∥P_X

= D(R_X ∥P_X).

(88)

n→∞

Далее, пусть R(n)Y = R(n)X ∗ P_W , так что для любого y ∈ R

R_Y (y) - C_nR(n)Y(y) = ERX[1R\[-n,n](X)P_W (y - X)].

Так как для всех x, y ∈ R имеем lim

1R\[-n,n](x)P_W (y - x) = 0, а также 0 ≤

n→∞

≤ 1R\[-n,n](x)P_W (y - x) ≤ P_W (y - x), так что ERX[P_W (y - X)] = R_Y (y) < +∞,

применяя теорему о мажорируемой сходимости, получаем поточечную сходимость

функций плотности распределения {R(n)Y}:

∀y ∈ R, lim

C_nR(n)Y(y) = lim

R(n)Y(y) = R_Y (y).

n→∞

Отсюда следует, что R(n)Y слабо сходится к R_Y при n → ∞ по лемме Шеффе. Сле-

довательно, согласно слабой полунепрерывности КЛ-дивергенции снизу [38, теоре-

ма 3.6, п. 3.5] имеем

(

)

lim inf

R(n)Y ∥P_Y

≥ D(R_Y ∥P_Y ).

(89)

n→∞

Объединяя (88) и (89), получаем

(

)

R(n)∥PY

D(R_Y ∥ P_Y )

lim inf

(

) ≥

(90)

D(R_X ∥ P_X )

^n→∞ D

R(n)X ∥P_X

Для завершения доказательства применим рассуждения, основанные на “диаго-

нальном методе”. Пусть {R_X,m : m ∈ N} - последовательность функций плотности

распределения, таких что 0 < D(R_X,m ∥ P_X ) < +∞ для всех m ∈ N, достигающая

супремума в (55):

D(R_Y,m ∥ P_Y )

lim

= η_KL(P_X, PY |X),

m→∞ D(R_X,m ∥ P_X )

где R_Y,m = R_X,m ∗ P_W . Тогда в силу (90) можно построить последовательность

{

}

R(n(m))X,m ∈ T : m ∈ N

, где каждое n(m) выбирается так, чтобы для любого m ∈ N

(

)

R(n(m))Y,m ∥P_Y

D(R_Y,m ∥ P_Y )

(

) ≥

D(R_X,m ∥ P_X )

2^m

R(n(m))X,m ∥P_X

где R(n(m))Y,m = R(n(m))X,m ∗ P_W . Устремляя m → ∞, получаем

(

)

R(n(m))∥PY

Y,m

lim inf

(

) ≥ η_KL(PX,PY |X).

^m→∞ D

R(n(m))∥PX

X,m

Поскольку супремум в (55) берется по всем плотностям распределения (которые

заведомо включают в себя все плотности распределения из T ), это неравенство на

самом деле является равенством, что и завершает доказательство. ▴

Теперь докажем теорему 5, пользуясь леммой 7, которая гарантирует, что все

дифференциальные энтропии, участвующие в нижеследующих рассуждениях, кор-

ректно определены и конечны.

Доказательство теоремы 5. Вначале заметим, что

Cov(X, Y )

σ2X

η_χ2 (P_X, P_Y|X) = ρ(X; Y )² =

Var(X) Var(Y )

σ2X + σ²

где первое равенство - это в точности соотношение (23) (справедливое для общих

случайных величин [11]), второе вытекает из седьмой аксиомы Реньи, гласящей, что

ρ(X; Y ) равно абсолютной величине коэффициента корреляции Пирсона совместно

гауссовских величин X и Y [12], а последнее получается непосредственными вычис-

лениями.

Теперь докажем, что для любого p ≥ σ2X

η_KL(P_X, P_Y|X) ≥ η(p)KL(P_X, P_Y|X) ≥ η_χ2 (P_X, P_Y|X).

Первое неравенство очевидно ввиду (55) и (57). Для второго неравенства положим

√

R_X = N(

δ, σ2X -δ) и R_Y = R_X ∗P_W = N(

δ, σ2X +σ2W -δ) для любого δ > 0. Тогда

получаем

(

)

σ²

+σ

log

D(R_Y ∥ P_Y )

σ2X + σ2W - δ

σ2X

lim

= lim

(

)

δ→0⁺ D(R_X ∥ P_X )

σ2X

σ2X + σ²

δ→0⁺ log

σ2X - δ

где первое равенство получается непосредственными вычислениями (см. [38, фор-

мула (1.17)]), а второе следует из правила Лопиталя. Так как ERX [X²] = σ2X для

любого δ > 0, то η(p)KL(P_X , P_Y|X ) ≥ σ2X /(σ2X + σ2W ) для любого p ≥ σ2X .

Поэтому достаточно доказать, что η_KL(P_X, P_Y|X) ≤ σ2X/(σ2X + σ2W ). С учетом

леммы 7 это равносильно тому, что для любой плотности распределения R_X ∈ T ,

такой что D(R_X ∥ P_X ) < +∞,

D(R_Y ∥ P_Y )

σ2X

≤

(91)

D(R_X ∥ P_X )

σ2X + σ²

Для любой плотности распределения R_X определим ее дифференциальную эн-

тропию h(R_X) ≜ - ERX[log(R_X(X))]. Чтобы проверить, что эти величины коррект-

но определены и конечны для R_X ∈ T , используем рассуждение из [101, лемма 8.3.1,

теорема 8.3.3]. Заметим, что для всех x ∈ ess supp(R_X)

)

⁽R_X(x)

x²

log(R_X (x)) = log

log(2πσ2X ) -

P_X(x)

2σ²

где через ess supp(·) обозначен существенный носитель измеримой по Борелю функ-

ции относительно меры Лебега. Поскольку величина D(R_X ∥ P_X ) должна быть ко-

нечна в формуле (55), а X² ≥ 0, можно перейти к математическим ожиданиям

относительно R_X:

ERX[X²]

-h(R_X) = D(R_X ∥P_X) -

log(2πσ2X ) -

(92)

2σ²

откуда следует, что h(R_X) существует всегда, она конечна, если ERX [X²] < +∞, и

h(R_X ) = +∞, когда ERX [X²] = +∞. Кроме того, если функция плотности распре-

деления R_X ∈ T имеет ограниченный существенный носитель, то ERX [X²] < +∞,

и h(R_X) определена и конечна.

Пусть R_X ∈ T и R_Y = R_X ∗ P_W имеют вторые моменты ERX [X²] = σ2X + q > 0

и ERY [Y ²] = σ2X + σ2W + q > 0 для некоторого q > -σ2X. Используя (92) и [38,

формула (1.20)], получаем

σ2X + q

D(R_X ∥ P_X ) =

log(2πσ2X ) +

- h(R_X) = h(P_X) - h(R_X) +

2σ2X

2σ²

D(R_Y ∥ P_Y ) = h(P_Y ) - h(R_Y ) +

2(σ2X + σ2W )

где h(R_Y ) существует и конечна, так как ERY [Y²] конечно (как показано выше с по-

мощью (92)). Значит, достаточно доказать, что

σ2X

h(P_Y ) - h(R_Y ) ≤

(h(P_X ) - h(R_X )),

(93)

σ2X + σ²

что равносильно (91). Перепишем (93) в виде

(

)_σ2

(

)_σ2

e2h(PY )-2h(RY )

+σ2W ≤

e2h(PX)-2h(RX)

^X ⇐⇒

⎛

⎞σ2X+σ2W

⎛

⎞σ2X

e2h(PY )

e2h(PX)

⎜

πe

⎟

⎜

πe

⎟

⇐⇒

⎝²

⎠

≤

⎝²

⎠

⇐⇒

e2h(RY⁾

e2h(RX⁾

2πe

)σ2X+σ2W

)σ2X

⁽N(PY )

⁽N(P_X)

⇐⇒

≤

N (R_Y )

N (R_X )

где для любой плотности распределения Q_X , такой что h(Q_X ) существует, мы опре-

деляем энтропийную мощность Q_X как N(Q_X ) ≜ e2h(QX)/(2πe) [102, п. III-A]. Для

P_X = N(0, σ2X), P_W = N(0, σ2W ) и P_Y = P_X ∗ P_W = N(0, σ2X + σ2W ) энтропийные

мощности равны N(P_X ) = σ2X , N(P_W ) = σ2W и N(P_Y ) = σ2X + σ2W соответствен-

но (см. [38, формула (1.20)]). Применяя неравенство для энтропийной мощности

к R_X, P_W и R_Y = R_X ∗ P_W [102, теорема 4], получаем

N (R_Y ) ≥ N(R_X ) + N(P_W ) = N(R_X ) + σ2W .

Следовательно, достаточно доказать, что

(

)σ2X+σ2W

(

)σ2X

σ2X + σ2W

σ2X

≤

N (R_X ) + σ2W

N (R_X )

Положим a = σ2X + σ2W , b = σ2X - N(R_X) и c = σ2X. Тогда имеем a > c > 0 и c > b

(что следует из конечности h(R_X)), и поэтому достаточно доказать, что

( a

)^a ≤(c

)^c,

a-b

c-b

что равносильно

(

)_a

a>c>0

и c>b

=⇒

≤ 1-

Это утверждением является вариантом неравенства Бернулли, доказанного в [103,

теорема 3.1, пп. (r′7) и (r′′7)], что и завершает доказательство. ▴

§6. Доказательства результатов о предпорядке меньшего искажения

Наконец, обратимся к выводу эквивалентных характеризаций отношения ≽_ln че-

рез операторную выпуклость. В п. 6.1 представлены предварительные сведения об

операторно выпуклых функциях, в п. 6.2 доказывается теорема 6, а в п. 6.3 - тео-

рема 7.

6.1. Операторно выпуклые функции. Для любого непустого (конечного или бес-

конечного, открытого или замкнутого) интервала I ⊆ R обозначим через Cn×nHerm(I)

множество всех (комплексных) эрмитовых матриц размера n × n, все собственные

значения которых принадлежат I, где Cn×nHerm(R) - пространство всех эрмитовых

матриц. Любую заданную функцию f : I → R можно продолжить до функции

f : Cn×nHerm(I) → Cn×nHerm(R) следующим образом [87, гл. V.1]:

∀A ∈ Cn×nHerm(I), f(A) ≜ U diag((f(λ₁), . . . , f(λ_n)))U^H ,

(94)

где A = U diag((λ₁, . . . , λ_n))U^H - спектральное разложение A с вещественными соб-

ственными значениями λ₁, . . . , λ_n ∈ I, U ∈ C^n×n - унитарная матрица, а U^H - ее

эрмитово сопряженная. Будем говорить, что f операторно выпукла, если для лю-

бого n ≥ 1, любой пары матриц A, B ∈ Cn×nHerm(I) и любого λ ∈ [0, 1] справедливо

соотношение

λf(A) + (1 - λ)f(B) ≽_PSD f(λA + (1 - λ)B),

(95)

где через ≽_PSD обозначен частичный порядок Лёвнера (т.е. для любых матриц

A, B ∈ Cn×nHerm(R) отношение A ≽_PSD B означает, что матрица A - B положительно

полуопределена), и непосредственной проверкой легко убедиться, что λA+(1-λ)B ∈

∈ Cn×nHerm(I) (см. [87, гл. V.1]). Заметим, что операторно выпуклая функция f : I → R

очевидным образом выпукла, и ее аффинные преобразования со сдвигами g: {c+x :

x ∈ I} → R, g(t) = af(t-c)+b, также операторно выпуклы для любых a ≥ 0, b ∈ R

и c ∈ R.

Удивительное свойство операторно выпуклых функций состоит в том, что они

характеризуются интегральными представлениями определенного типа - см. тео-

ремы Лёвнера в [87, гл. V.4, задача V.5.5]. В частности, для любой операторно вы-

пуклой функции f : (0, ∞) → R, такой что f(1) = 0, существуют константы a ∈ R

и b ≥ 0 и конечная положительная мера μ на (1,∞) (с соответствующей борелевской

σ-алгеброй), такие что

∫

(t - 1)(ωt - ω - 1)

f (t) = a(t - 1) + b(t - 1)² +

dμ(ω),

(96)

t+ω-1

(1,∞)

что следует из [18, формула (7)] и соответствующих ссылок (заметим, что наша f

и функция g в [18] связаны как f(t) = g(t - 1)). Как отмечено в [18], верно и об-

ратное, т.е. функции вида (96) операторно выпуклы. Следующая лемма является

прямым следствием формулы (96), которую мы выделили из [18] и представляем

здесь в более прозрачном виде, показывающем роль дивергенций Винце - Ле Кама.

Лемма 8 (интегральное представление [18, c. 33]). Рассмотрим произвольную

f-дивергенцию, где функция f : (0, ∞) → R операторно выпукла и f(1) = 0. Тогда

существует константа b ≥ 0 и конечная положительная мера τ на (0, 1) (с со-

ответствующей борелевской σ-алгеброй), такие что для любых R_X , P_X ∈ P_X

∫

1+λ²

D_f (R_X ∥P_X) = bχ²(R_X ∥P_X) +

LC_λ(R_X ∥P_X)dτ(λ).

λ(1 - λ)

(0,1)

Доказательство. Зафиксируем произвольные вероятностныемеры R_X,P_X ∈

∈ P_X, и пусть случайная величина X имеет распределение P_X. Тогда, поскольку

для f справедливо интегральное представление (96), подставим t = R_X (X)/P_X (X)

в (96) и перейдем к математическим ожиданиям:

]

[

)₂

⁽R_X(X)^)]

[(R_X(X)

E f

=bE

-1

P_X(X)

∫

)(

)⎤

^⎡(RX(X)

RX(X)

-1

-ω-1

⎢

(X)

⎥

+ E⎣

⎦ dμ(ω),

RX(X)

+ω-1

(X)

(1,∞)

где первое слагаемое в правой части (96) исчезает после перехода к математическому

ожиданию (см. свойство аффинной инвариантности в п. 2.1). Отсюда

∫

⎡

)₂

⎤

⁽ RX(X)

(1 + ω²)

-1

⎢

(X)

⎥

D_f (R_X ∥P_X) = bχ²(R_X ∥P_X) +

E⎣

)

⎦ dμ(ω),

⁽ RX(X)

+ω-1

(X)

(1,∞)

где левая часть вытекает из определения 1, χ²-дивергенция получается из (4), а по-

следнее слагаемое следует из свойства аффинной инвариантности в п. 2.1 и соотно-

шения

(t - 1)(ωt - ω - 1)

(1 + ω²)(t - 1)

t-1

∀t ≥ 0, ∀ω > 1,

t+ω-1

ω(t + ω - 1)

Теперь заметим, что замена переменных ω =

дает

∫

⎡

)₂

⎤

⁽ RX(X)

(1 + λ²)

-1

⎢

(X)

⎥

D_f (R_X ∥P_X) = bχ²(R_X ∥P_X) +

E⎣

(

)

⎦ dτ(λ)

RX(X)

+1-λ

(X)

(0,1)

для некоторой конечной положительной меры τ на (0, 1). Наконец, замечая, что

подынтегральное выражение в правой части пропорционально дивергенции Винце -

Ле Кама (см. п. 2.1), непосредственными преобразованиями получаем требуемое

интегральной представление. ▴

Лемма 8 использовалась в [18, c. 33] (в несколько другом виде) для доказатель-

ства предложения 6 (см. [18, теорема 1]). Кроме того, в [8, c. 3363] также использо-

валась ключевая идея из [18, c. 33] для получения альтернативного интегрального

представления (через дивергенцию Винце - Ле Кама и χ²-дивергенцию), аналогич-

ного лемме 8. Однако представление из [8, c. 3363] справедливо лишь для операторно

выпуклых функций f, таких что f(0) конечно, в то время как лемма 8 верна и для

бесконечных f(0).

6.2. Доказательство теоремы 6. Теперь с помощью леммы 8 докажем теорему 6.

Доказательство теоремы 6. Наше доказательство использует технику до-

казательств утверждений [18, теорема 1] и [83, теорема 1] (см. также [8, п. III-C]). За-

фиксируем произвольную нелинейную операторно выпуклую функцию f : (0, ∞) →

→ R, такую что f(1) = 0, где из нелинейности следует, что соответствующая f-ди-

вергенция не тождественно равна нулю (см. свойство аффинной инвариантности

в п. 2.1). Для любых стохастических матриц PY |X = W ∈ P_Y|X и P_Z|X = V ∈ P_Z|X

вначале установим, что неравенство

∀R_X , P_X ∈ P_X , χ²(R_X W ∥ P_X W ) ≥ χ²(R_X V ∥ P_X V )

(97)

имеет место тогда и только тогда, когда

∀R_X , P_X ∈ P_X , D_f (R_X W ∥ P_X W ) ≥ D_f (R_X V ∥ P_X V ).

(98)

Для доказательства необходимости условия 98, применяя лемму 8 и эквивалент-

ное представление дивергенции Винце - Ле Кама из (6), получаем следующее инте-

гральное представление нашей f-дивергенции через χ²-дивергенцию (см. [18, c. 33]):

∀R_X , P_X ∈ P_X , D_f (R_X ∥ P_X ) = bχ²(R_X ∥ P_X ) +

∫

1+λ²

(

)

χ²

R_X ∥λR_X + (1 - λ)P_X

dτ(λ),

(99)

(1 - λ)²

(0,1)

где b ≥ 0 - некоторая константа, а τ - конечная положительная мера на (0, 1).

В силу (97) также имеем

∀R_X , P_X ∈ P_X ,

(

)

(

)

χ²

R_XW ∥(λR_X + (1 - λ)P_X)W

≥χ²

R_XV ∥(λR_X + (1 - λ)P_X)V

(100)

для любого λ ∈ (0, 1). Поэтому, используя (97) и (100), а также интегральное пред-

ставление (99), получаем (98), что и требовалось.

Для доказательства достаточности заметим, что из интегрального представления

Лёвнера (96) следует, что f бесконечно дифференцируема и f^′′(1) > 0. В силу (98)

получаем также, что для любого λ ∈ (0, 1)

(

)

∀R_X , P_X ∈ P_X , D_f

((1 - λ)P_X + λR_X )W ∥ P_X W

≥

(

)

≥D_f

((1 - λ)P_X + λR_X )V ∥ P_X V

(101)

Поэтому, умножая обе части неравенства (101) на 2/(f^′′(1)λ²) > 0 и переходя к

пределу при λ → 0⁺, из локальной аппроксимации f-дивергенций (равенство (13))

получаем (97) для всех RX ∈ PX и всех PX ∈ P◦X. Хотя наш вариант равен-

ства (13) справедлив в предположении P_X ∈ P^◦X , утверждение (97) верно также

и для P_X ∈ P_X \ P^◦X в силу непрерывности χ²-дивергенции по второму аргументу

при фиксированном первом.

Теперь заметим, что эквивалентность между (97) и (98) показывает, что все

предпорядки на стохастических матрицах, определяемые через нелинейные опера-

торно выпуклые f-дивергенции согласно (98) (способом, аналогичным определе-

нию 6) эквивалентны. Действительно, все они характеризуются χ²-дивергенцией

(см. (97)). Поскольку КЛ-дивергенция является нелинейной операторно выпуклой

f-дивергенцией (см. замечание после теоремы 6 в п. 3.4 по поводу теоремы Лёвне-

ра - Хайнца), предпорядок меньшего искажения ≽_ln эквивалентен предпорядку, за-

даваемому χ²-дивергенцией в (97); это в точности является содержанием утвержде-

ний [83, теорема 1] и [85, теорема 1]. Следовательно, ≽_ln эквивалентен предпорядку,

задаваемому соотношением (98), для любой нелинейной операторно выпуклой f-ди-

вергенции, что и завершает доказательство. ▴

Теперь докажем предложение 6, чтобы показать, что оно является немедленным

следствием теоремы 6.

Доказательство предложения 6. Зафиксируем произвольную нелиней-

ную операторно выпуклую функцию f : (0, ∞) → R, такую что f(1) = 0, и лю-

бую стохастическую матрицу P_Y|X = W ∈ P_Y|X . Согласно теореме 6 для матрицы

|X |-ичного канала со стиранием E1-β ≽_ln P_Y|X тогда и только тогда, когда

∀R_X , P_X ∈ P_X , D_f (R_X W ∥ P_X W ) ≤ D_f (R_X E1-β ∥ P_X E1-β ) = βD_f (R_X ∥ P_X ),

где равенство разбирается в комментариях после формулы (30) в п. 2.2. Эта экви-

валентность приводит к следующему обобщению соотношения (58):

η_f (P_Y|X) = min{β ∈ [0, 1] : E1-β ≽_ln P_Y|X}.

(102)

Поэтому коэффициенты сжатия η_f (P_Y|X) для всех нелинейных операторно выпук-

лых f равны, и в частности, все они равны η_χ2 (P_Y|X ) и η_KL(P_Y|X ) (так как функции,

соответственно, f(t) = t² - 1 и f(t) = t log(t) операторно выпуклы по теореме Лёв-

нера - Хайнца). ▴

6.3. Доказательство теоремы 7. Чтобы доказать теорему 7, нам понадобится по-

лезная лемма о тензоризации. Пусть X_i ∈ X_i, Y_i ∈ Y_i и Z_i ∈ Z_i - дискретные

случайные величины с конечными множествами значений, и пусть PYi|Xi^∈PYi|Xi

и PZi|Xi ∈ PZi|Xi - стохастические матрицы, i = 1,2. В следующей лемме сформули-

ровано свойство тензоризации предпорядка меньшего искажения [7, предложение 16;

104, предложение 5].

Лемма

(тензоризация предпорядка меньшего искажения [7, 104]). Если

PZi |Xi^≽ln^PYi |Xiдляi=1,2,тоPZ1 |X1^⊗PZ2 |X2^≽ln^PY1 |X1^⊗PY2 |X2^.

Наконец, приведем доказательство теоремы 7 с помощью теоремы 6, леммы 9 и

соотношения (58).

Доказательство теоремы 7. Будем следовать схеме доказательства из [7].

Вначале заметим, что η_i = η_KL(P_Y

i|Xi)

для всех i ∈ {1, . . . , n} согласно предло-

жению 6 (см. [18, теорема 1]). Пусть Z_i ∈ Z_i = X_i ∪ {e} - дискретная случайная

величина, и пусть P_Z

i|Xi

= E1-ηi ∈ P_Z

i|Xi

- матрица |X_i|-ичного канала со стира-

нием с вероятностью стирания 1 - η_i, определенная в (30), для всех i ∈ {1, . . . , n}.

Тогда, используя (58) (см. [7, предложение 15]), получаем, что матрица P_Z

i|Xi ме-

нее искажающая, чем P_Y

i|Xi,длявсехi∈{1,...,n}.Теперьопределимпроизведение

стохастических матриц P_Zn

|Xn1 ∈ PZn|Xn:

P_Zn

|Xn1 = PZ1|X1^⊗PZ2|X2^⊗...⊗PZn|Xn^,

где Zn1 = (Z₁, . . . , Z_n) и Zⁿ = Z₁ × . . . × Z_n. Тогда по лемме 9 получаем, что P_Zn

|Xn1

менее искажающая, чем P_Y n

|Xⁿ.₁

Чтобы доказать вариант СНОД Самородницкого для f-дивергенции (64), зафик-

сируем произвольную пару вероятностных мер на входе R_Xn

,P_Xn

∈ P_Xn. Тогда по

теореме 6 имеем

D_f (R_Y n

∥P_Yn) ≤ Df(RZn

∥P_Zn),

(103)

где R_Zn

=R_Xn

P_Zn

|Xn1 ∈ PZⁿ и PZn1 = PXn1PZn1|Xn1 ∈ PZⁿ. Теперь заметим, что слу-

чайную величину Zn1 можно эквивалентным образом представить как (X_S , S), где

случайное подмножество S представляет собой позиции, которые не стираются под

действием P_Zn|Xn1, а XS - значения в этих позициях. (Заметим, что Z1 = (e, . . . , e)

соответствует множеству S = ∅.) Таким образом,

)

(

)

∑

⁽P_S(T)RXT (x_T)

D_f

R_Zn

∥P_Zn

P_S(T)

PXT (x_T )f

P_S(T)PXT (x_T )

T⊆{1,...,n}

∑

P_S(T)D_f(RXT ∥PXT ),

T⊆{1,...,n}

где использован тот факт, что S не зависит от Xn1, а также следующие соглашения:

D_f (RX∅ ∥PX∅) = 0, и P_S(T)D_f (RXT ∥PXT ) = 0, если P_S(T) = 0. С учетом (103)

отсюда получаем (64).

Чтобы доказать вариант СНОД Самородницкого для взаимной f-информа-

ции (65), зафиксируем произвольное совместное распределение P_U,Xn и рассмотрим

цепь Маркова U → Xn1 → (Yn1, Zn1), такую что Yn1 и Zn1 условно независимы при за-

данном Xn1. Это задает совместное распределение P_U,Xn

,Yn1,Zn1 через PU,Xn₁ , PYn1 |Xn1

и P_Zn

|Xⁿ. Для любой заданной U = u ∈ U из (103) получаем₁

(

)

(

)

D_f

P_Y n

|U=u ∥PY n1

≤D_f

P_Zn|U=u ∥PZn

ные вероятностные меры (на выходе), соответствующие условной вероятностной

мере (на входе) P_Xn|U=u ∈ PXn (благодаря марковскому свойству), а PYn1 ∈ PYn

и P_Zn

∈ P_Zn - маргинальные вероятностные меры для P_U,Xn,Yn1,Zn . С учетом (8),1

переходя к математическим ожиданиям по маргинальной вероятностной мере P_U ,

получаем

If (U;

) ≤ I_f(U;Zn1 ).

(104)

Далее, используя эквивалентность между Zn1 и (X_S, S), имеем (как и выше)

If (U; Z¹) = If (U; XS , S) =

)

∑

⁽P_X

T |U(^xT|u)PU(u)PS(T)

P_S(T)

P_U (u)

PXT (x_T )f

PXT (x_T )P_U (u)P_S(T)

T⊆{1,...,n}

u∈U

∑

(

)

∑

P_S(T)D_f

PU,XT ∥P_U PXT

P_S(T)I_f (U; X_T ),

T⊆{1,...,n}

где использовано соотношение (8) и тот факт, что S не зависит от (U, Xn1), а также

следующие соглашения: I_f (U; X_∅) = 0, и P_S (T )I_f (U; X_T ) = 0, если P_S (T ) = 0.

С учетом (104) отсюда получаем (65).

И наконец, случай η_i = η для всех i ∈ {1, . . . , n} в (66) получается подстанов-

кой выражения для P_S (T ) в (65) и дальнейшими стандартными выкладками, что и

завершает доказательство. ▴

Заметим, что в условиях теоремы 7, если к тому же η_i = η для всех i ∈ {1, . . ., n},

то наше обобщенное СНОД Самородницкого действительно точнее, чем тензоризо-

ванное СНОД (63):

∑

If (U;

)≤

η^|T|(1 - η)^n-|T|I_f (U; X_T ) ≤ (1 - (1 - η)ⁿ)I_f (U; Xn1).

(105)

T⊆{1,...,n}

Это так, поскольку I_f (U; Zn1) ≤ (1 - (1 - η)ⁿ)I_f (U; Xn1) с учетом соотношения (63)

для произведения стохастических матриц P_Zn

|Xⁿ.₁

§ 7. Заключение

Здесь мы вкратце перечислим наши основные достижения и предложим некото-

рые направления дальнейшего исследования. Вначале мы описали некоторые свой-

ства коэффициентов сжатия для совместных распределений. Точнее, в теореме 1

было показано, что такие коэффициенты сжатия достигают своей верхней грани-

цы, равной единице, когда совместное распределение разложимо, а в теореме 2 -

что наложение на оптимизационную задачу, определяющую величину η_f (P_X , P_Y|X )

дополнительного ограничения “локальной аппроксимации”, при котором f-дивер-

генции на входе становятся сколь угодно малыми, приводит к оптимальному зна-

чению η_χ2(P_X , P_Y|X ). Этот последний результат довольно прозрачно объясняет

интуитивные соображения по поводу нижней границы максимальной корреляции

в п. 7 предложения 3. Затем в теореме 3 мы вывели линейную верхнюю границу на

η_f (P_X, P_Y|X) через η_χ2 (P_X, P_Y|X) для некоторого класса f-дивергенций, а в теоре-

ме 4 улучшили эту границу для важного частного случая η_KL(P_X , P_Y|X ). Подобные

границы полезны для режимов со слабой зависимостью, таких как возникающие при

анализе эргодичности цепей Маркова (как показано в предложении 7). В духе срав-

нения коэффициентов сжатия для совместных распределений мы также дали аль-

тернативное доказательство эквивалентности η_KL(P_X, P_Y|X) = η_χ2(P_X, P_Y|X) для

совместно гауссовских распределений P_X,Y , описываемых моделями АБГШ в теоре-

ме 5 и § 5. Это доказательство продемонстрировало, что при наложении достаточно

сильного ограничения на мощность (или ограниченный второй момент) в экстре-

мальной задаче для величины η_KL(P_X , P_Y|X ) ее значение не изменяется. Наконец,

в области коэффициентов сжатия для стохастических матриц мы обобщили пред-

ложение 6 в теореме 6 и установили, что предпорядок меньшего искажения на сто-

хастических матрицах полностью характеризуется любой нелинейной операторно

выпуклой f-дивергенцией. Более того, в качестве приложения этой характеризации

мы также обобщили СНОД Самородницкого на все нелинейные операторно выпук-

лые f-дивергенции в теореме 7.

Как было указано в п. 4.4, константы в линейных границах из теорем 3 и 4

“неотчетливо” изменяются с изменением размерности распределения-произведения.

В то время как результаты, подобные следствию 2, частично позволяют справиться

с этой проблемой тензоризации, одним из обязательных направлений будущих иссле-

дований должно стать получение линейных границ, константы в которых должным

образом ведут себя при тензоризации. Еще одно, по-видимому, более конкретное на-

правление будущей работы - это вывод оптимального зависящего от распределений

улучшенного варианта леммы 4 (как предложено в [79, замечание, c. 5380]). Такой

улучшенный вариант можно было бы использовать для уточнения теоремы 3 так,

чтобы из нее вытекала теорема 4 вместо следствия 1. Однако и такой улучшенный

вариант не сможет охватить вопрос, связанный с тензоризацией, что гораздо важнее

для данных границ.

ПРИЛОЖЕНИЕ A: ДОКАЗАТЕЛЬСТВО ПРЕДЛОЖЕНИЯ 2

Схема доказательства описана в [4], а само доказательство приведено в диплом-

ной работе автора [48, теорема 3.2.4] для случая P_X ∈ P^◦X и P_Y ∈ P^◦Y . Мы приводим

его здесь для полноты изложения.

Пусть маргинальные вероятностные меры для X и Y таковы, что P_X ∈ P^◦X и

P_Y ∈ P^◦Y. Вначале покажем, что наибольшее сингулярное число МДП B равно еди-

нице. Рассмотрим матрицу

(√

)-1

(√

)

M = diag

P_Y

B^T B diag

P_Y

= diag(P_Y )-1W^T diag(P_X )W = V W,

где V = diag(P_Y )-1W^T diag(P_X ) ∈ P_X|Y - стохастическая по строкам обратная мат-

рица вероятностей перехода, соответствующая условному распределению P_X|Y . За-

метим, что M имеет тот же набор собственных значений, что и матрица Грама МДП

B^T B, поскольку она просто определяется через преобразование подобия. Так как

B^T B положительно полуопределена, собственные значения матриц M и B^T B - неот-

рицательные вещественные числа согласно спектральной теореме (см. [49, п. 2.5]).

Более того, так как и V , и W стохастические по строкам, их произведение M = V W

также стохастическое по строкам. Следовательно, наибольшее собственное значение

матриц M и B^T B равно единице по теореме Перрона - Фробениуса (см. [49, гл. 8]).

Отсюда следует, что наи√льше√сингулярное число матрицы B также равно едини-

це. Отметим также, что

P_X и

P_Y - соответственно левый и правый сингулярные

векторы матрицы B, соответствующие сингулярному числу, равному единице. Дей-

ствительно,

√

(√

)

(√

)-1

√

P_XB =

P_X diag

P_X

W diag

P_Y

P_Y ,

√

P_Y

^T = diag^(√P_X )W diag^(√P_Y )-1√PY T = ^√P_XT.

Далее, следуя определению 3, пусть f ∈ R^|X| и g ∈ R^|Y| - векторы-столбцы,

задающие множества значений функций f : X → R и g : Y → R соответственно.

Заметим, что математические ожидания в определении 3 можно выразить через B,

P_X, P_Y , f и g:

(

(√

)

E[f(X)g(Y )] =

diag

P_X

)^T B⁽diag^(√P_Y )g⁾,

√

(

(√

)

E[f(X)] =

P_X

diag

P_X

√

(

(√

)

E[g(Y )] =

P_Y

diag

P_Y



(√

)



²

E[f(X)²] =

^diag

P_X



(√

)



E[g(Y )²] =

^diag

P_Y

g2

Полагая a = diag

(√P_X )f и b = diag(√P_Y )g, из определения 3 получаем

ρ(X; Y ) =

max

a^T Bb,

a∈R^|X| , b∈R^|Y|

√PXa=√PY b=0

∥a∥²²=∥b∥²²=1

где оптимизация проводится по всем a ∈ R^|X| и b ∈ R^|Y|, поскольку P_X ∈ P^◦X и

P_Y ∈ P^◦Y. Так как a и b ортогональны, соответственно, левому и правому сингуляр-

ным векторам, соответствующим максимальному сингулярному числу матрицы B,

равному единице, эта максимизация дает второе по величине сингулярное число мат-

рицы B с помощью альтернативной версии (см., например, [105, лемма 2]) принципа

минимакса Куранта- Фишера-Вейля (см. [49, теоремы 4.2.6 и 7.3.8]). Это доказы-

вает, что ρ(X; Y ) - второе по величине сингулярное число МДП, когда P_X ∈ P^◦X

и P_Y ∈P^◦Y.

Наконец, покажем, что без ограничения общности можно считать, что P_X ∈ P^◦X

и P_Y ∈ P^◦Y. Когда P_X или P_Y имеют нулевые компоненты, X и Y принимают зна-

чения лишь на носителях supp(P_X ) = {x ∈ X : P_X (x) > 0} ⊆ X и supp(P_Y ) =

= {y ∈ Y : P_Y (y) > 0} ⊆ Y соответственно, что означает, что P_X ∈ P◦supp(P

иP_Y ∈

∈ P◦supp(P

. Пусть B обозначает “истинную” МДП размера |X| × |Y|, соответству-

Y )

ющую вероятностной мере P_X,Y на X × Y, а B_supp - “ограниченную на носитель”

МДП размера |supp(P_X )| × |supp(P_Y )|, соответствующую вероятностной мере P_X,Y

на supp(P_X ) × supp(P_Y ). Очевидно, B можно восстановить по B_supp, добавляя нуле-

вые строки и столбцы, соответствующие компонентам с нулевой вероятностью в X

и Y соответственно. Поэтому B и B_supp имеют одинаковые ненулевые сингулярные

значения (с учетом кратностей), откуда следует, что и второе по величине сингу-

лярное число у них одинаково, что завершает доказательство. ▴

ПРИЛОЖЕНИЕ B: ДОКАЗАТЕЛЬСТВО ПРЕДЛОЖЕНИЯ 3

Свойство 1: Нормировка коэффициентов сжатия очевидна в силу неотрицатель-

ности f-дивергенций и соответствующих им неравенств об обработке данных (7).

Отметим, что в случае η_χ2(P_X, P_Y|X) = ρ(X; Y )² (где использовалось (23)) условие

0 ≤ ρ(X;Y ) ≤ 1 - это третья аксиома Реньи в определении максимальной корреля-

ции [12].

Свойство 2: Дадим простое доказательство этого хорошо известного свойства.

Без ограничения общности предположим, что P_X ∈ P^◦X , отбрасывая все компонен-

ты X, имеющие нулевую вероятность. Если в результате |X| = 1, то X - константа

п.н., и результат тривиален. Итак, можно считать, что |X | ≥ 2. Так как W - мат-

рица единичного ранга (все ее строки равны P_Y , т.е. PY|X=x = P_Y для всех x ∈ X )

тогда и только тогда, когда X и Y независимы, достаточно показать, что W имеет

единичный ранг тогда и только тогда, когда η_f (P_X , P_Y|X ) = 0.

Для доказательства в одну сторону заметим, что если ранг W равен единице,

то все ее строки равны P_Y , и R_XW = PY для всех RX ∈ PX. Следовательно,

η_f (P_X, P_Y|X) = 0 в силу определения 2, поскольку D_f(R_XW ∥P_XW) = 0 для всех

вероятностных мер на входе R_X ∈ P_X .

Для доказательства обратного утверждения применим слегка измененный ва-

риант рассуждения из [48, лемма 3.1.5], которое использовалось для доказатель-

ства случая η_KL(P_X, P_Y|X). Для любых x ∈ X и λ ∈ (0, 1) рассмотрим RX =

= (1 - λ)δ_x + λu ∈ P^◦X , где δ_x - вероятностная дельта-мера Кронекера, такая что

δ_x(x) = 1 и δ_x(x^′) = 0 для x^′ ∈ X \ {x}, u - равномерная вероятностная мера, а λ

выбрано так, что R_X = P_X . Тогда 0 < D_f (R_X ∥ P_X ) < +∞, поскольку f строго

выпукла в единице, и D_f (R_X W ∥ P_X W ) = 0, так как η_f (P_X , P_Y|X ) = 0. Отсюда

следует, что

(1 - λ)PY|X=x + λuW = R_X W = P_X W = P_Y ,

так как f строго выпукла в единице. Переходя к пределу при λ → 0, получаем, что

каждая строка W равна P_Y . (Заметим, что невозможно применить этот аргумент

просто при λ = 0, или R_X = δ_x, поскольку f(0) может равняться бесконечности.)

Значит, W имеет единичный ранг.

Заметим также, что в случае η_χ2 (P_X , P_Y|X ) это свойство максимальной корре-

ляции является четвертой аксиомой Реньи из [12].

Свойство 3: См. теорему 1 и Приложение C. Заметим, что случай η_χ2 (P_X , P_Y|X )

этого результата был доказан в [13, 15] (см. лемму 10), а случай η_KL(P_X, P_Y|X) -

в [15].

Свойство 4: Это доказано в [8, предложение III.3].

Свойство 5: Это доказано в [8, теорема III.9]. Заметим также, что два доказатель-

ства свойства тензоризации для η_KL(P_X, P_Y|X) можно найти в [4], а доказательство

свойства тензоризации для η_χ2 (P_X , P_Y|X ) - в [13].

Свойство 6: Для доказательства первой части этого утверждения обозначим че-

рез P_U,X,Y совместную вероятностную меру для (U, X, Y ), состоящую из маргиналь-

ной вероятностной меры P_U ∈ P_U и условных распределений P_X|U = S ∈ P_X|U и

P_Y|X = W ∈ P_Y|X (т.е. стохастических по строкам матриц вероятностей перехода).

Тогда P_Y|U = SW ∈ P_Y|U согласно марковскому свойству. Заметим, что для любой

вероятностной меры R_U ∈ P_U \ {P_U }

D_f (R_U SW ∥P_U SW) ≤ η_f (P_X, P_Y|X)η_f (P_U , P_X|U )D_f (R_U ∥P_U ),

где P_X = P_U S и дважды использовалось СНОД (15). Отсюда

η_f (P_U , P_Y|U ) ≤ η_f (P_U , P_X|U )η_f (P_X, P_Y|X)

согласно определению 2.

Частный случай этого результата для η_χ2 соответствует свойству субмультипли-

кативности второго по величине сингулярного числа МДП. Это свойство субмуль-

типликативности также верно и для i-го по величине сингулярного числа МДП

(см. [106, теорема 2]), что полезно в приложениях, связанных с кодированием рас-

пределенных источников и каналов. При этом результат из [106, теорема 2] также

доказан в [40, теорема 3], где показана связь с главными компонентами инерции

и максимальной корреляцией.

Для доказательства второй части утверждения заметим, что для фиксированно-

го P_X,Y и любого P_U|X, такого что U → X → Y образуют цепь Маркова (с совмест-

ной вероятностной мерой P_U,X,Y ) и η_f (P_U , P_X|U ) > 0 (для чего требуется, чтобы X

не была постоянной п.н.), справедливо

η_f (P_U , P_Y|U )

≤ η_f(P_X,PY |X),

(106)

η_f (P_U , P_X|U )

где использовалось установленное выше свойство субмультипликативности. Пусть

U = X п.н., так что P_U|X ∈ P_X|X - единичная матрица. Тогда η_f(P_U,P_X|U) = 1

и η_f(P_U,P_Y|U) = η_f(P_X,P_Y|X) в силу определения 2. Поэтому равенство в (106)

достигается, что завершает доказательство.

Отметим, что случай η_χ2 этого результата представлен в [68, лемма 6], где также

доказано, что в качестве оптимальной стохастической матрицы P_U|X можно взять

P_Y|X (так что U является копией Y ) вместо единичной матрицы (где U = X п.н.).

Свойство 7: Будем следовать нашей технике доказательства из [1, теорема 5],

навеянной подходом из [17, теорема 5.4].

Напомним, что совместная вероятностная мера P_X,Y состоит из PX ∈ P◦X и

P_Y|X = W ∈ P_Y|X , и обозначим через B соответствующую МДП (см. (24)). За-

дадим траекторию сферически возмущенных вероятностных мер вида (11):

(√

)

R(ε)X = P_X + εK_X diag

P_X

где

{

}

(

√

K_X ∈ S ≜ x ∈

R^|X|)∗ :

P_Xx^T = 0, ∥x∥₂ = 1

– вектор сферического возмущения. Когда эти вероятностные меры проходят че-

рез W , получаем траекторию на выходе

(√

)

R(ε)XW = P_Y + εK_XB diag

P_Y

(107)

где B отображает сферические возмущения на входе в сферические возмущения на

выходе [43]. Теперь согласно определению 2 имеем

D_f (R_XW ∥P_XW)

η_f (P_X, P_Y|X) =

sup

≥

RX∈PX

D_f (R_X ∥P_X)

0<D_f (RX ∥PX )<+∞

∥K_X B∥

+ o(1)

∥K_XB∥²² + o(1)

≥ lim inf sup

≥ sup

lim inf

ε→0

1 + o(1)

KX∈S

∥K_X∥²² + o(1) KX∈S

= η_χ2 (P_X , PY |X ) = ρ(X; Y )²,

где второе неравенство вытекает из (14) при сужении супремума на все вероят-

ностные меры вида (11) (где ε = 0 - некоторая достаточно малая фиксированная

величина) и перехода к пределу при ε → 0, третье неравенство следует из неравен-

ства о минимаксе, а заключительные равенства - из (25) и (23) соответственно, что

и завершает доказательство.

Заметим, что предположения P_X ∈ P^◦X и P_Y ∈ P^◦Y , будучи важными для зада-

ния вышеупомянутых траекторий вероятностных мер, не существенны для самого

результата. Для специального случая η_KL(P_X , P_Y|X ) этот результат был впервые до-

казан в [15], а затем повторно в [3] и [1] - последние два доказательства используют

различного типа аргументы, основанные на возмущениях. ▴

ПРИЛОЖЕНИЕ C: ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 1

Для доказательства теоремы 1 нам потребуются следующие две леммы; первая

из них известна, а вторая является новой.

Лемма 10 (разложимость и максимальная корреляция [13,15]). Совместная

вероятностная мера P_X,Y является разложимой тогда и только тогда, когда

η_χ2 (P_X, P_Y|X) = ρ(X; Y )² = 1.

Доказательство. Хотя этот результат и был доказан в [13,15], для полноты

изложения мы приведем здесь доказательство. Пусть P_X,Y разложима и существуют

функции h: X → R и g: Y → R, такие что h(X) = g(Y ) п.н. и Var(h(X)) > 0. Тогда

без ограничения общности можно считать, что E[h(X)] = 0 и E[h(X)²] = 1, откуда

ρ(X; Y ) = 1 согласно определению 3. Таким образом, η_χ2 (P_X , P_Y|X ) = 1 в силу (23).

В обратную сторону, пусть η_χ2(P_X, PY |X) = 1, или, что равносильно, ρ(X; Y ) = 1

(в силу (23)). Пусть h: X → R и g: Y → R - функции, на которых достигается

ρ(X; Y ); такие функции существуют, когда X и Y конечны, так как в определении 3

берется экстремум непрерывной целевой функции по компактным множествам. Оче-

видно, что h(X) и g(Y ) имеют нулевое среднее, единичную дисперсию и коэффи-

циент корреляции Пирсона, равный 1. Отсюда следует, что h(X) = g(Y ) п.н., с по-

мощью прямого (и хорошо известного) рассуждения, использующего неравенство

Коши- Буняковского. Следовательно, P_X,Y разложима. ▴

Лемма 11 (одновременная экстремальность). Пусть задана выпуклая функ-

ция f : (0, ∞) → R, дважды дифференцируемая в единице и такая, что f(1) = 0

и f^′′(1) > 0. Тогда справедливо следующее:

1. Если η_χ2 (P_X, P_Y|X) = 1, то η_f (P_X, P_Y|X) = 1;

2. Если f строго выпукла и удовлетворяет условию f(0) < ∞, то из равенства

η_f (P_X, P_Y|X) = 1 следует η_χ2 (P_X, P_Y|X) = 1.

Доказательство. Утверждение 1 тривиальным образом следует из пп. 1 и 7

предложения 3.

Утверждение 2: Пусть η_f (P_X , P_Y|X ) = 1. Рассмотрим последовательность веро-

{

(

)

}

ятностных мер на входе

R(n)X ∈ P_X : 0 < D_f

R(n)X ∥P_X

< +∞, n ∈ N

, на которой

в пределе достигается η_f (P_X , PY |X ):

(

)

D_f

R(n)W∥PY

lim

(

)

= 1.

^n→∞ D_f

R(n)

∥P_X

С учетом секвенциональной компактности P_X можно считать, что R(n)X → R_X для

некоторого R_X ∈ P_X при n → ∞ (в смысле ℓ²-нормы), при необходимости переходя

к подпоследовательности. Отсюда получаем следующие две возможности.

Случай 1: Пусть R_X = P_X . В этом случае доказательство теоремы 2 в Прило-

жении D показывает, что η_f (P_X , P_Y|X ) = η_χ2 (P_X , P_Y|X ). Таким образом, получаем

η_χ2 (P_X, P_Y|X) = 1.

Случай 2: Пусть R_X = P_X . Так как f(0) < ∞, f строго выпукла и P_X ∈ P^◦X , то

0 < D_f(R_X ∥P_X) < +∞. Следовательно, получаем

(

)

(n)

D_f

R_X

W∥P_Y

D_f (R_XW ∥P_Y )

lim

(

)

= 1,

^n→∞ D_f

R(n)X ∥P_X

D_f (R_X ∥P_X)

используя непрерывность f (вытекающую из ее выпуклости). Теперь заметим, что

так как f строго выпукла и 0 < D_f (R_X W ∥ P_X W ) = D_f (R_X ∥ P_X ) < +∞, то Y явля-

ется достаточной статистикой для X, позволяющей делать выводы о паре (R_X , P_X )

(см. [28, теорема 14] или п. 2.1), откуда, в свою очередь, следует (см. [28, теорема 14]

или п. 2.1), что

0 < χ²(R_XW ∥P_XW) = χ²(R_X ∥P_X) < +∞.

Следовательно, η_χ2 (P_X , P_Y|X ) = 1 в силу (22). ▴

Доказательство теоремы 1 немедленно следует из лемм 10 и 11. ▴

ПРИЛОЖЕНИЕ D: ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 2

Доказательство. Начнем с определения функции τ : (0,∞) → [0,1]:

D_f(R_XW ∥P_XW)

τ (δ) ≜

sup

D_f (R_X ∥P_X)

RX∈PX

0<D_f (RX ∥PX )≤δ

так что все, что требуется доказать, это

lim

τ (δ_n) = η_χ2 (P_X , P_Y|X )

n→∞

для любой убывающей последовательности {δ_n > 0 : n ∈ N}, такой что lim

δ_n = 0.

n→∞

Заметим, что предел в левой части существует, поскольку при δ_n → 0 супремум

по τ(δ_n) является невозрастающим и ограничен снизу нулем.

Вначале докажем, что lim

τ (δ_n) ≥ η_χ2 (P_X , P_Y|X ), следуя, по существу, доказа-

n→∞

тельству п. 7 предложения 3 в Приложении B. Для этого рассмотрим траекторию

сферически возмущенных вероятностных мер вида (11):

(√

)

R(n)X = P_X + ε_nK_X diag

P_X

где

{

√

}

(

K_X ∈ S = x ∈

R^|X|)∗ :

P_Xx^T = 0, ∥x∥₂ = 1

– вектор сферического возмущения. Соответствующая траектория вероятностных

мер на выходе после прохождения через W имеет вид (107):

(√

)

R(n)XW = P_Y + ε_nK_XB diag

P_Y

где B - МДП, соответствующая P_X,Y в (24). Потребуем, чтобы все скалярные ве-

личины {ε_n = 0 : n ∈ N}, определяющие нашу траекторию, удовлетворяли условию

lim

ε_n = 0 и были достаточно малыми, так чтобы

n→∞

(

)

f^′′(1)

D_f

R(n)X ∥P_X

ε2n ∥K_X∥²² + o(ε2n) ≤ δ_n,

где использовалось (14) (а также тот факт, что f^′′(1) существует и строго положи-

тельна) и стандартная o-символика Бахмана - Ландау. По определению τ имеем

(

)

D_f

R(n)W∥PXW

sup

(

)

≤ τ(δ_n),

KX∈S D_f

R(n)X ∥P_X

f^′′(1)

ε2n ∥K_XB∥²² + o(ε2n)

lim sup

≤ lim

τ (δ_n),

n→∞K

n→∞

X∈S f^′′(1)

ε2n ∥K_X∥²² + o(ε2n)

∥K_XB∥

+ o(1)

lim sup

≤ lim

τ (δ_n),

n→∞K

1 + o(1)

n→∞

X∈S

η_χ2 (P_X, P_Y|X) ≤ lim

τ (δ_n),

n→∞

где во втором неравенстве использовалось (14) как в числителе, так и в знаменате-

ле, а в последнем неравенстве - характеризация η_χ2 (P_X , P_Y|X ) через сингулярное

число в (25).

Теперь докажем, что lim

τ (δ_n) ≤ η_χ2 (P_X , P_Y|X ). Заметим, что для любого n ∈ N

n→∞

существует вероятностная мера R(n)X ∈ P_X , обладающая следующими свойствами:

(

)

0<D_f

R(n)X ∥P_X

≤δ_n;

(

(n)

)

D_f

R_X

W ∥PXW

0 ≤ τ(δ_n) -

(

)

≤

D_f

R(n)X ∥ PX

2ⁿ

первое из которых справедливо, поскольку R_X → D_f (R_X ∥P_X) - непрерывное отоб-

ражение при фиксированной P_X ∈ P^◦X (что следует из выпуклости f), а второе -

поскольку τ(δ_n) определяется как супремум. Так как τ(δ_n) сходится при n → ∞,

получаем

(

)

D_f

R(n)W∥PXW

lim

(

)

= lim

τ (δ_n).

(108)

n→∞

^n→∞ D_f

R(n)X ∥P_X

С учетом секвенциальной компактности P_X можно считать, что R(n)X сходится при

n → ∞ (в смысле ℓ²-нормы), переходя при необходимости к подпоследовательности.

Так как lim

D_f (R(n)X ∥P_X) = 0, то lim

R(n)X = P_X в силу непрерывности отображе-

n→∞

ния R_X → D_f (R_X ∥ P_X ) при фиксированной P_X ∈ P^◦X и того факта, что f-дивер-

генция (где f строго выпукла в единице) равна нулю тогда и только тогда, когда ее

{

}

аргументы равны. Зададим векторы сферического возмущения

K(n)X ∈ S : n ∈ N

в виде

(√

)

R(n)X = P_X + ε_nK(n)X diag

P_X

где {ε_n = 0 : n ∈ N} задают необходимые масштабирования, а lim

ε_n = 0 (так как

n→∞

lim

R(n)X = P_X). Соответствующие вероятностные меры на выходе имеют вид (107)

n→∞

с необходимыми поправками, и отношение между выходной и входной f-диверген-

циями можно, как и выше, аппроксимировать с помощью (14):



f^′′(1)



²

ε2n

^K(n)XB

+ o(ε2n)

K(n)

²

D_f (R(n)XW ∥P_XW)

+ o(1)



f^′′(1)

1 + o(1)

D_f (R(n)X ∥P_X)

²

ε2n

^K(n)X

+ o(ε2n)

С учетом секвенциальной компактности S можно считать, что lim

K(n)X = K^⋆X ∈ S,

n→∞

переходя при необходимости к подпоследовательности. Отсюда, переходя к пределу

при n → ∞, получаем

lim

τ (δ_n) = ∥K^⋆X B∥²² ≤ η_χ2 (P_X , P_Y|X ),

n→∞

(

где равенство следует из (108) и непрерывности отображения

R^|X|)∗ ∋ x → ∥xB∥22,

а неравенство - из (25), что и завершает доказательство. ▴

ПРИЛОЖЕНИЕ E: ДОКАЗАТЕЛЬСТВО СЛЕДСТВИЯ 1

Доказательство. Выпуклая функция f : (0,∞) → R, f(t) = tlog(t), оче-

видно, строго выпукла и трижды дифференцируема в единице, причем f(1) = 0,

f^′(1) = 1, f′′(1) = 1 > 0 и f′′′(1) = -1. Кроме того, функция g: (0, ∞) → R,

f(t) - f(0)

g(t) =

= log(t), где f(0) = lim f(t) = 0, очевидно, выпукла вверх. Таким

t→0⁺

образом, для доказательства следствия 1 с помощью теоремы 3 достаточно показать,

что f удовлетворяет условию (75) для любого t ∈ (0, ∞) (см. [79])

(

)

(

)

f^′′′(1)

f^′′(1)

f (t) - f^′(1)(t - 1)

(t - 1)

≥

(t - 1)²,

3f^′′(1)

что после упрощения приводится к виду

2t(t + 2) log(t) - (5t + 1)(t - 1) ≥ 0.

Зададим h: (0, ∞) → R, h(t) = 2t(t + 2) log(t) - (5t + 1)(t - 1), и заметим, что

h^′(t) = 4(t + 1)log(t) - 8(t - 1),

h^′′(t) = 4 log(t) +

- 4 ≥ 0,

где неотрицательность второй производной следует из хорошо известного неравен-

ства

∀x > 0, x log(x) ≥ x - 1.

Так как h выпукла (поскольку ее вторая производная неотрицательна) и h(1) =

= h^′(1) = 0, то t = 1 является глобальной точкой минимума h, и h(t) ≥ 0 для

любого t ∈ (0, ∞), что и требовалось.

Наконец, нетрудно проверить, что константа в следствии 1 равна

f^′(1) + f(0)

f^′′(1)minPX(x)

minPX(x)

x∈X

что и завершает доказательство. ▴

ПРИЛОЖЕНИЕ F: ДОКАЗАТЕЛЬСТВО ГРАНИЦЫ (78)

Доказательство. В [1, лемма 6] приведены два доказательства границы (78).

Здесь мы изложим одно из них, использующее идеи выпуклого анализа. В нем при-

меняется тот факт, что КЛ-дивергенция является так называемой дивергенцией

Брегмана, соответствующей отрицательной функции энтропии Шеннона, а затем

сильная выпуклость отрицательной функции энтропии Шеннона используется для

вывода границы на КЛ-дивергенцию. Пусть H_neg : P_X → R - отрицательная функ-

ция энтропии Шеннона, определяемая как

∑

∀Q_X ∈ P_X , H_neg(Q_X ) ≜

Q_X(x)log(Q_X(x)).

x∈X

Так как дивергенция Брегмана, соответствующая функции H_neg, является КЛ-ди-

вергенцией (см. [107]), то для всех S_X ∈ P_X и Q_X ∈ P^◦X справедливо

D(S_X ∥ Q_X ) = H_neg(S_X ) - H_neg(Q_X ) - (S_X - Q_X )∇H_neg(Q_X ),

где ∇H_neg : P^◦X → R^|X| - градиент функции H_neg. При этом, так как H_neg дважды

непрерывно дифференцируема, справедливо

∀Q_X ∈ P^◦X ,

∇²H_neg(Q_X) = diag(Q_X)-1 ≽_PSD I,

где через ∇²H_neg : P^◦X → R^|X|×|X| обозначен гессиан функции H_neg. (Заметим, что

матрица diag(Q_X )-1 - I положительно полуопределена как диагональная матрица

с неотрицательными элементами на диагонали.) Напомним [100, гл. 9], что дважды

непрерывно дифференцируемая выпуклая функция f : S → R на открытой области

S ⊆ Rⁿ называется сильно выпуклой, если существует m > 0, такое что для всех

x ∈ S выполнено ∇²f(x) ≽ mI. Значит, H_neg сильно выпукла на P^◦X. Следствием

этой сильной выпуклости является такая квадратичная нижняя граница [100, гл. 9]:

H_neg(S_X) ≥ H_neg(Q_X) + (S_X - Q_X)∇H_neg(Q_X) +

∥S_X - Q_X∥²² ⇐⇒

⇐⇒ D(S_X ∥ Q_X) ≥

∥S_X - Q_X∥²²

для любых S_X ∈ P_X и Q_X ∈ P^◦X , где разрешается S_X ∈ P_X \ P^◦X в силу непрерывно-

сти H_neg. Это в точности то же самое, что получалось при ослаблении границы (71)

в доказательстве леммы 2 с помощью соотношений ∥S_X - Q_X ∥₁ ≥ ∥S_X - Q_X ∥₂

и (70). Наконец, для любых S_X ∈ P_X и Q_X ∈ P^◦X имеем

minQX(x)

x∈X

D(S_X ∥ Q_X ) ≥

∥S_X - Q_X∥²² ≥

χ²(S_X ∥Q_X),

где второе неравенство вытекает из (4). Это тривиальным образом справедливо так-

же и для всех Q_X ∈ P_X \ P^◦X . ▴

Первый автор выражает благодарность проф. Юрию Полянскому за весьма по-

лезные обсуждения по поводу теорем 6 и 7, а также в целом за обсуждение вопросов,

связанных с коэффициентами сжатия.

СПИСОК ЛИТЕРАТУРЫ

Makur A., Zheng L. Bounds between Contraction Coefficients // Proc. 53rd Annual Aller-

ton Conf. on Communication, Control, and Computing. Monticello, IL, USA. Sept. 29 -

October 2, 2015. P. 1422-1429.

Erkip E., Cover T.M. The Efficiency of Investment Information // IEEE Trans. Inform.

Theory. 1998. V. 44. № 3. P. 1026-1040.

Kamath S., Anantharam V. Non-interactive Simulation of Joint Distributions: The Hirsch-

feld-Gebelein-Rényi Maximal Correlation and the Hypercontractivity Ribbon // Proc.

50th Annual Allerton Conf. on Communication, Control, and Computing. Monticello, IL,

USA. Oct. 1-5, 2012. P. 1057-1064.

Anantharam V., Gohari A., Kamath S., Nair C. On Maximal Correlation, Hypercontrac-

tivity, and the Data Processing Inequality Studied by Erkip and Cover, arXiv:1304.6133

[cs.IT], 2013.

Anantharam V., Gohari A., Kamath S., Nair C. On Hypercontractivity and the Mutual

Information between Boolean Functions // Proc. 51st Annual Allerton Conf. on Commu-

nication, Control, and Computing. Monticello, IL, USA. Oct. 2-4, 2013. P. 13-19.

Polyanskiy Y., Wu Y. Dissipation of Information in Channels with Input Constraints //

IEEE Trans. Inform. Theory. 2016. V. 62. № 1. P. 35-55.

Polyanskiy Y., Wu Y. Strong Data-Processing Inequalities for Channels and Bayesian

Networks // Convexity and Concentration. New York: Springer, 2017. P. 211-249.

Raginsky M. Strong Data Processing Inequalities and Φ-Sobolev Inequalities for Discrete

Channels // IEEE Trans. Inform. Theory. 2016. V. 62. № 6. P. 3355-3389.

Hirschfeld H.O. A Connection between Correlation and Contingency // Math. Proc. Cam-

bridge Philos. Soc. 1935. V. 31. № 4. P. 520-524.

10.

Gebelein H. Das statistische Problem der Korrelation als Variations- und Eigenwertproblem

und sein Zusammenhang mit der Ausgleichsrechnung // Z. Angew. Math. Mech. 1941.

V. 21. № 6. P. 364-379.

11.

Сарманов О.В. Максимальный коэффициент корреляции (несимметричный слу-

чай) // Докл. АН СССР. 1958. Т. 121. № 1. С. 52-55.

12.

Rényi A. On Measures of Dependence // Acta Math. Acad. Sci. Hungar. 1959. V. 10.

№ 3-4. P. 441-451.

13.

Witsenhausen H.S. On Sequences of Pairs of Dependent Random Variables // SIAM J.

Appl. Math. 1975. V. 28. № 1. P. 100-113.

14.

Добрушин Р.Л. Центральная предельная теорема для неоднородных цепей Марко-

ва. I // Теория вероятн. и ее примен. 1956. Т. 1. № 1. С. 72-89.

15.

Ahlswede R., Gács P. Spreading of Sets in Product Spaces and Hypercontraction of the

Markov Operator // Ann. Probab. 1976. V. 4. № 6. P. 925-939.

16.

Seneta E. Non-negative Matrices and Markov Chains. New York: Springer, 1981.

17.

Cohen J.E., Iwasa Y., Răutu G., Ruskai M.B., Seneta E., Zbăganu G. Relative Entropy

under Mappings by Stochastic Matrices // Linear Algebra Appl. 1993. V. 179. P. 211-235.

18.

Choi M.-D., Ruskai M.B., Seneta E. Equivalence of Certain Entropy Contraction Coeffi-

cients // Linear Algebra Appl. 1994. V. 208/209. P. 29-36.

19.

Cohen J.E., Kemperman J.H.B., Zbăganu G. Comparisons of Stochastic Matrices with

Applications in Information Theory, Statistics, Economics and Population Sciences. Ann

Arbor, MI, USA: Birkhäuser, 1998.

20.

Körner J., Marton K. Comparison of Two Noisy Channels // Topics in Information Theory

(2nd Colloq., Keszthely, Hungary, 1975). Colloq. Math. Soc. János Bolyai. V. 16. Amster-

dam: North-Holland, 1977. P. 411-423.

21.

Csiszár I. Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis

der Ergodizität von Markoffschen Ketten // Magyar Tud. Akad. Mat. Kutató Int. Közl.

Ser. A. 1963. V. 8. P. 85-108.

22.

Csiszár I. Information-type Measures of Difference of Probability Distributions and Indirect

Observations // Studia Sci. Math. Hungar. 1967. V. 2. P. 299-318.

23.

Ali S.M., Silvey S.D. A General Class of Coefficients of Divergence of One Distribution

from Another // J. Roy. Statist. Soc. Ser. B. 1966. V. 28. № 1. P. 131-142.

24.

Morimoto T. Markov Processes and the H-Theorem // J. Phys. Soc. Japan. 1963. V. 18.

№ 3. P. 328-331.

25.

Akaike H. Information Theory and an Extension of the Maximum Likelihood Principle //

Proc. 2nd Int. Symp. on Information Theory. Tsaghkadzor, Armenia, USSR. Sept. 2-8,

1971. Budapest, Hungary: Akad. Kiadó, 1973. P. 267-281.

26.

Ziv J., Zakai M. On Functionals Satisfying a Data-Processing Theorem // IEEE Trans.

Inform. Theory. 1973. V. 19. № 3. P. 275-283.

27.

Zakai M., Ziv J. A Generalization of the Rate-Distortion Theory and Applications //

Information Theory: New Trends and Open Problems. New York: Springer, 1975. P. 87-123.

28.

Liese F., Vajda I. On Divergences and Informations in Statistics and Information Theory //

IEEE Trans. Inform. Theory. 2006. V. 52. № 10. P. 4394-4412.

29.

Levin D.A., Peres Y., Wilmer E.L. Markov Chains and Mixing Times. Providence, RI,

USA: Amer. Math. Soc., 2009.

30.

Kullback S., Leibler R.A. On Information and Sufficiency // Ann. Math. Statist. 1951.

V. 22. № 1. P. 79-86.

31.

Neyman J. Contribution to the Theory of the χ² Test // Proc. 1st Berkeley Symp. on

Mathematical Statistics and Probability. Berkeley, CA, USA. Aug. 13-18, 1945; Jan. 27-

29, 1946. Berkeley, CA, USA: Univ. of California Press, 1949. P. 239-273.

32.

Nielsen F., Nock R. On the Chi Square and Higher-Order Chi Distances for Approximating

f-Divergences // IEEE Signal Process. Lett. 2014. V. 21. № 1. P. 10-13.

33.

Liese F., Vajda I. Convex Statistical Distances. Leipzig: Teubner, 1987.

34.

Sason I., Verdú S. f-Divergence Inequalities // IEEE Trans. Inform. Theory. 2016. V. 62.

№ 11. P. 5973-6006.

35.

Le Cam L. Asymptotic Methods in Statistical Decision Theory. New York: Springer, 1986.

36.

Vincze I. On the Concept and Measure of Information Contained in an Observation //

Contributions to Probability: A Collection of Papers Dedicated to Eugène Lukacs. New

York: Academic Press, 1981. P. 207-214.

37.

Györfi L., Vajda I. A Class of Modified Pearson and Neyman Statistics // Statist. Deci-

sions. 2001. V. 19. № 3. P. 239-251.

38.

Polyanskiy Y., Wu Y. Lecture Notes on Information Theory. Dept. of Electrical Engineering

and Computer Science, MIT, Cambridge, USA, 2017. Lect. Notes 6.441.

39.

Csiszár I. A Class of Measures of Informativity of Observation Channels // Period. Math.

Hungar. 1972. V. 2. № 1-4. P. 191-213.

40.

du Pin Calmon F., Makhdoumi A., Médard M., Varia M., Christiansen M., Duffy K.R.

Principal Inertia Components and Applications // IEEE Trans. Inform. Theory. 2017.

V. 63. № 8. P. 5011-5038.

41.

Cover T.M., Thomas J.A. Elements of Information Theory. Hoboken, NJ, USA: John

Wiley & Sons, 2006.

42.

Borade S., Zheng L. Euclidean Information Theory // Proc. IEEE Int. Zurich Seminar on

Communications. Zurich, Switzerland. Mar. 12-14, 2008. P. 14-17.

43.

Huang S.-L., Zheng L. Linear Information Coupling Problems // Proc. 2012 IEEE Int.

Symp. on Information Theory (ISIT’2012). Cambridge, MA, USA. July 1-6, 2012. P. 1029-

1033.

44.

Amari S., Nagaoka H. Methods of Information Geometry. Providence, RI, USA: Amer.

Math. Soc.; Oxford Univ. Press, 2000.

45.

Csiszár I., Shields P.C. Information Theory and Statistics: A Tutorial. Hanover, MA, USA:

Now Publ., 2005.

46.

Gohari A.A., Anantharam V. Evaluation of Marton’s Inner Bound for the General Broad-

cast Channel // IEEE Trans. Inform. Theory. 2012. V. 58. № 2. P. 608-619.

47.

Abbe E., Zheng L. A Coordinate System for Gaussian Networks // IEEE Trans. Inform.

Theory. 2012. V. 58. № 2. P. 721-733.

48.

Makur A. A Study of Local Approximations in Information Theory: Master’s Thesis. Dept.

of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA, 2015.

49.

Horn R.A., Johnson C.R. Matrix Analysis. New York: Cambridge Univ. Press, 2013.

50.

Greenacre M.J. Theory and Applications of Correspondence Analysis. San Diego, CA,

USA: Academic Press, 1984.

51.

Greenacre M., Hastie T. The Geometric Interpretation of Correspondence Analysis //

J. Amer. Statist. Assoc. 1987. V. 82. № 398. P. 437-447.

52.

Hsu H., Salamatian S., Calmon F.P. Correspondence Analysis Using Neural Networks //

Proc. 22nd Int. Conf. on Artificial Intelligence and Statistics (AISTATS’2019). Naha,

Japan. April 16-18, 2019. P. 2671-2680.

53.

Lancaster H.O. The Structure of Bivariate Distributions // Ann. Math. Statist. 1958. V. 29.

№ 3. P. 719-736.

54.

Lancaster H.O. The Chi-Squared Distribution. New York: John Wiley & Sons, 1969.

55.

Makur A., Zheng L. Polynomial Spectral Decomposition of Conditional Expectation Op-

erators // Proc. 54th Annual Allerton Conf. on Communication, Control, and Computing.

Monticello, IL, USA. Sept. 27-30, 2016. P. 633-640.

56.

Makur A., Zheng L. Polynomial Singular Value Decompositions of a Family of Source-

Channel Models // IEEE Trans. Inform. Theory. 2017. V. 63. № 12. P. 7716-7728.

57.

Breiman L., Friedman J.H. Estimating Optimal Transformations for Multiple Regression

and Correlation // J. Amer. Statist. Assoc. 1985. V. 80. № 391. P. 580-598.

58.

Makur A., Kozynski F., Huang S.-L., Zheng L. An Efficient Algorithm for Information

Decomposition and Extraction // Proc. 53rd Annual Allerton Conf. on Communication,

Control, and Computing. Monticello, IL, USA. Sept. 29 - Oct. 2, 2015. P. 972-979.

59.

Golub G.H., van Loan C.F. Matrix Computations Baltimore, MD, USA: The Johns Hop-

kins Univ. Press, 1996.

60.

Demmel J.W. Applied Numerical Linear Algebra. Philadelphia, PA, USA: SIAM, 1997.

61.

Makur A. Information Contraction and Decomposition: Sc.D. Thesis. Dept. of Electrical

Engineering and Computer Science, MIT, Cambridge, MA, USA, 2019.

62.

Huang S.-L., Makur A., Kozynski F., Zheng L. Efficient Statistics: Extracting Information

from IID Observations // Proc. 52nd Annual Allerton Conf. on Communication, Control,

and Computing. Monticello, IL, USA. Oct. 1-3, 2014. P. 699-706.

63.

Huang S.-L., Makur A., Wornell G.W., Zheng L. On Universal Features for High-

Dimensional Learning and Inference, arXiv:1911.09105 [cs.LG], 2019.

64.

Pearson K. On Lines and Planes of Closest Fit to Systems of Points in Space // Philos.

Mag. 1901. V. 2. № 11. P. 559-572.

65.

Hotelling H. Analysis of a Complex of Statistical Variables into Principal Components //

J. Educ. Psychol. 1933. V. 24. № 6. P. 417-441; 498-520.

66.

Hotelling H. Relations between Two Sets of Variates // Biometrika. 1936. V. 28. № 3/4.

P. 321-377.

67.

Coifman R.R., Lafon S. Diffusion Maps // Appl. Comput. Harmon. Anal. 2006. V. 21.

№ 1. P. 5-30.

68.

Asoodeh S., Diaz M., Alajaji F., Linder T. Information Extraction under Privacy Con-

straints // Information. 2016. V. 7. № 1. Article no. 15 (37 pp.).

69.

Seneta E. Coefficients of Ergodicity: Structure and Applications // Adv. in Appl. Probab.

1979. V. 11. № 3. P. 576-590.

70.

Ipsen I.C.F., Selee T.M. Ergodicity Coefficients Defined by Vector Norms // SIAM J.

Matrix Anal. Appl. 2011. V. 32. № 1. P. 153-200.

71.

Selee T.M. Stochastic Matrices: Ergodicity Coefficients, and Applications to Ranking:

Ph.D. Thesis. Dept. of Applied Mathematics, North Carolina State Univ., Raleigh, NC,

USA, 2009.

72.

Kontorovich A. Obtaining Measure Concentration from Markov Contraction // Markov

Process. Related Fields. 2012. V. 18. № 4. P. 613-638.

73.

Yu B. Assouad, Fano, and Le Cam // Festschrift for Lucien Le Cam: Research Papers in

Probability and Statistics. New York: Springer, 1997. P. 423-435.

74.

Shannon C.E. The Zero Error Capacity of a Noisy Channel // IRE Trans. Inform. Theory.

1956. V. 2. № 3. P. 8-19.

75.

Csiszár I., Körner J. Information Theory: Coding Theorems for Discrete Memoryless Sys-

tems. New York: Cambridge Univ. Press, 2011.

76.

Evans W.S., Schulman L.J. Signal Propagation and Noisy Circuits // IEEE Trans. Inform.

Theory. 1999. V. 45. № 7. P. 2367-2373.

77.

Goldstein S. Maximal Coupling // Z. Wahrsch. Verw. Gebiete. 1979. V. 46. № 2. P. 193-204.

78.

Kim H., Gao W., Kannan S., Oh S., Viswanath P. Discovering Potential Correlations via

Hypercontractivity // Entropy. 2017. V. 19. № 11. Article no. 586 (32 pp.).

79.

Gilardoni G.L. On Pinsker’s and Vajda’s Type Inequalities for Csiszár’s f-Divergences //

IEEE Trans. Inform. Theory. 2010. V. 56. № 11. P. 5377-5386.

80.

Verdú S. Total Variation Distance and the Distribution of Relative Information // Proc.

2014 Information Theory and Applications Workshop (ITA’2014). San Diego, CA, USA.

Feb. 9-14, 2014. P. 1-3.

81.

Nair C. An Extremal Inequality Related to Hypercontractivity of Gaussian Random Vari-

ables // Proc. 2014 Information Theory and Applications Workshop (ITA’2014). San Diego,

CA, USA. Feb. 9-14, 2014. P. 1-7.

82.

Calmon F.P., Polyanskiy Y., Wu Y. Strong Data Processing Inequalities for Input Con-

strained Additive Noise Channels // IEEE Trans. Inform. Theory. 2018. V. 64. № 3.

P. 1879-1892.

83.

Makur A., Polyanskiy Y. Comparison of Channels: Criteria for Domination by a Symmetric

Channel // IEEE Trans. Inform. Theory. 2018. V. 64. № 8. P. 5704-5725.

84.

van Dijk M. On a Special Class of Broadcast Channels with Confidential Messages // IEEE

Trans. Inform. Theory. 1997. V. 43. № 2. P. 712-714.

85.

Makur A., Polyanskiy Y. Less Noisy Domination by Symmetric Channels // Proc. 2017

IEEE Int. Symp. on Information Theory (ISIT’2017). Aachen, Germany. June 25-30, 2017.

P. 2463-2467.

86.

Carlen E. Trace Inequalities and Quantum Entropy: An Introductory Course // Entropy

and the Quantum. Providence, RI, USA: Amer. Math. Soc., 2010. P. 73-140.

87.

Bhatia R. Matrix Analysis. New York: Springer, 1997.

88.

Samorodnitsky A. On the Entropy of a Noisy Function // IEEE Trans. Inform. Theory.

2016. V. 62. № 10. P. 5446-5464.

89.

Kumar G.R., Courtade T.A. Which Boolean Functions Are Most Informative? // Proc.

2013 IEEE Int. Symp. on Information Theory (ISIT’2013). Istanbul, Turkey. July 7-12,

2013. P. 226-230.

90.

El Gamal A., Kim Y.-H. Network Information Theory. New York: Cambridge Univ. Press,

2011.

91.

Ordentlich E., Weinberger M.J. A Distribution Dependent Refinement of Pinsker’s Inequal-

ity // IEEE Trans. Inform. Theory. 2005. V. 51. № 5. P. 1836-1840.

92.

Sason I. Bounds on f-Divergences and Related Distances // CCIT Report № 859. Haifa,

Israel: Dept. of Electrical Engineering, Technion - Israel Inst. of Technology, 2014.

93.

Harremoës P., Vajda I. On Pairs of f-Divergences and Their Joint Range // IEEE Trans.

Inform. Theory. June 2011. V. 57. № 6. P. 3230-3235.

94.

Fedotov A.A., Harremoës P., Topsøe F. Refinements of Pinsker’s Inequality // IEEE Trans.

Inform. Theory. 2003. V. 49. № 6. P. 1491-1498.

95.

Su F.E. Methods for Quantifying Rates of Convergence for Random Walks on Groups:

Ph.D. Thesis. Dept. of Mathematics, Harvard Univ., Cambridge, MA, USA, 1995.

96.

Dragomir S.S., Gluščević V. Some Inequalities for the Kullback-Leibler and χ²-Distances

in Information Theory and Applications // Tamsui Oxf. J. Math. Sci. 2001. V. 17. № 2.

P. 97-111.

97.

Sason I. Tight Bounds for Symmetric Divergence Measures and a New Inequality Relating

f-Divergences // Proc. 2015 IEEE Information Theory Workshop (ITW’2015). Jerusalem,

Israel. April 26 - May 1, 2015. P. 1-5.

98.

Gibbs A.L., Su F.E. On Choosing and Bounding Probability Metrics // Int. Stat. Rev.

2002. V. 70. № 3. P. 419-435.

99.

Csiszár I., Talata Z. Context Tree Estimation for Not Necessarily Finite Memory Processes,

via BIC and MDL // IEEE Trans. Inform. Theory. 2006. V. 52. № 3. P. 1007-1016.

100.

Boyd S., Vandenberghe L. Convex Optimization. New York: Cambridge Univ. Press, 2004.

101.

Ash R.B. Information Theory. New York: John Wiley & Sons, 1965.

102.

Dembo A., Cover T.M., Thomas J.A. Information Theoretic Inequalities // IEEE Trans.

Inform. Theory. 1991. V. 37. № 6. P. 1501-1518.

103.

Li Y.-C., Yeh C.-C. Some Equivalent Forms of Bernoulli’s Inequality: A Survey // Appl.

Math. 2013. V. 4. № 7. P. 1070-1093.

104.

Sutter D., Renes J.M. Universal Polar Codes for More Capable and Less Noisy Channels

and Sources // Proc. 2014 IEEE Int. Symp. on Information Theory (ISIT’2014). Honolulu,

HI, USA. June 29 - July 4, 2014. P. 1461-1465.

105.

Rakočević V., Wimmer H.K. A Variational Characterization of Canonical Angles between

Subspaces // J. Geom. 2003. V. 78. № 1. P. 122-124.

106.

Kang W., Ulukus S. A New Data Processing Inequality and Its Applications in Distributed

Source and Channel Coding // IEEE Trans. Inform. Theory. 2011. V. 57. № 1. P. 56-69.

107.

Banerjee A., Merugu S., Dhillon I.S., Ghosh J. Clustering with Bregman Divergences //

J. Mach. Learn. Res. 2005. V. 6. P. 1705-1749.

Макур Ануран

Поступила в редакцию

Чжэн Личжун

17.10.2019

Отделение информационных технологий,

После доработки

Массачусетский технологический институт, Кэмбридж, США

17.10.2019

a_makur@mit.edu

Принята к публикации

lizhong@mit.edu

09.03.2020