Для некоторых приложений в линейной алгебре полезно знать свойства распределения вероятностей наибольшего собственного значения конечной суммы матриц случайных . Предполагать { X k } {\displaystyle \{\mathbf {X} _{k}\}} оценке Чернова ищется оценка следующего для сумм скаляров, для данного параметра t :
Pr { λ max ( ∑ k X k ) ≥ t } {\displaystyle \Pr \left\{\lambda _{\max }\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}} Следующие теоремы отвечают на этот общий вопрос при различных предположениях; эти предположения названы ниже по аналогии с их классическими скалярными аналогами. Все эти теоремы можно найти в ( Tropp 2010 ) как конкретное применение общего результата, полученного ниже. Приведен краткий обзор смежных работ.
Рассмотрим конечную последовательность { A k } {\displaystyle \{\mathbf {A} _{k}\}} d {\displaystyle d} { ξ k } {\displaystyle \{\xi _{k}\}} независимых стандартных нормальных или независимых Радемахера случайных величин .
Тогда для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( ∑ k ξ k A k ) ≥ t } ≤ d ⋅ e − t 2 / 2 σ 2 {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\xi _{k}\mathbf {A} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}} где
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} Рассмотрим конечную последовательность { B k } {\displaystyle \{\mathbf {B} _{k}\}} d 1 × d 2 {\displaystyle d_{1}\times d_{2}} { ξ k } {\displaystyle \{\xi _{k}\}}
σ 2 = max { ‖ ∑ k B k B k ∗ ‖ , ‖ ∑ k B k ∗ B k ‖ } . {\displaystyle \sigma ^{2}=\max \left\{{\bigg \Vert }\sum _{k}\mathbf {B} _{k}\mathbf {B} _{k}^{*}{\bigg \Vert },{\bigg \Vert }\sum _{k}\mathbf {B} _{k}^{*}\mathbf {B} _{k}{\bigg \Vert }\right\}.} Тогда для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { ‖ ∑ k ξ k B k ‖ ≥ t } ≤ ( d 1 + d 2 ) ⋅ e − t 2 / 2 σ 2 . {\displaystyle \Pr \left\{{\bigg \Vert }\sum _{k}\xi _{k}\mathbf {B} _{k}{\bigg \Vert }\geq t\right\}\leq (d_{1}+d_{2})\cdot e^{-t^{2}/2\sigma ^{2}}.} Классические границы Чернова касаются суммы независимых, неотрицательных и равномерно ограниченных случайных величин.В матричной ситуации аналогичная теорема касается суммы положительно-полуопределенных случайных матриц, подчиненных равномерной границе собственных значений.
Рассмотрим конечную последовательность { X k } {\displaystyle \{\mathbf {X} _{k}\}} d {\displaystyle d}
X k ⪰ 0 and λ max ( X k ) ≤ R {\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R} почти наверняка.
Определять
μ min = λ min ( ∑ k E X k ) and μ max = λ max ( ∑ k E X k ) . {\displaystyle \mu _{\text{min}}=\lambda _{\text{min}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{and}}\quad \mu _{\text{max}}=\lambda _{\text{max}}\left(\sum _{k}\mathbb {E} \,\mathbf {X} _{k}\right).} Затем
Pr { λ min ( ∑ k X k ) ≤ ( 1 − δ ) μ min } ≤ d ⋅ [ e − δ ( 1 − δ ) 1 − δ ] μ min / R for δ ∈ [ 0 , 1 ) , and {\displaystyle \Pr \left\{\lambda _{\text{min}}\left(\sum _{k}\mathbf {X} _{k}\right)\leq (1-\delta )\mu _{\text{min}}\right\}\leq d\cdot \left[{\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right]^{\mu _{\text{min}}/R}\quad {\text{for }}\delta \in [0,1){\text{, and}}} Pr { λ max ( ∑ k X k ) ≥ ( 1 + δ ) μ max } ≤ d ⋅ [ e δ ( 1 + δ ) 1 + δ ] μ max / R for δ ≥ 0. {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq (1+\delta )\mu _{\text{max}}\right\}\leq d\cdot \left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right]^{\mu _{\text{max}}/R}\quad {\text{for }}\delta \geq 0.} Рассмотрим последовательность { X k : k = 1 , 2 , … , n } {\displaystyle \{\mathbf {X} _{k}:k=1,2,\ldots ,n\}}
X k ⪰ 0 and λ max ( X k ) ≤ 1 {\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq 1} почти наверняка.
Вычислите минимальные и максимальные собственные значения среднего ожидания,
μ ¯ min = λ min ( 1 n ∑ k = 1 n E X k ) and μ ¯ max = λ max ( 1 n ∑ k = 1 n E X k ) . {\displaystyle {\bar {\mu }}_{\text{min}}=\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right)\quad {\text{and}}\quad {\bar {\mu }}_{\text{max}}=\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbb {E} \,\mathbf {X} _{k}\right).} Затем
Pr { λ min ( 1 n ∑ k = 1 n X k ) ≤ α } ≤ d ⋅ e − n D ( α ‖ μ ¯ min ) for 0 ≤ α ≤ μ ¯ min , and {\displaystyle \Pr \left\{\lambda _{\text{min}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\right)\leq \alpha \right\}\leq d\cdot e^{-nD(\alpha \Vert {\bar {\mu }}_{\text{min}})}\quad {\text{for }}0\leq \alpha \leq {\bar {\mu }}_{\text{min}}{\text{, and}}} Pr { λ max ( 1 n ∑ k = 1 n X k ) ≥ α } ≤ d ⋅ e − n D ( α ‖ μ ¯ max ) for μ ¯ max ≤ α ≤ 1. {\displaystyle \Pr \left\{\lambda _{\text{max}}\left({\frac {1}{n}}\sum _{k=1}^{n}\mathbf {X} _{k}\right)\geq \alpha \right\}\leq d\cdot e^{-nD(\alpha \Vert {\bar {\mu }}_{\text{max}})}\quad {\text{for }}{\bar {\mu }}_{\text{max}}\leq \alpha \leq 1.} Бинарная информационная дивергенция определяется как
D ( a ‖ u ) = a ( log a − log u ) + ( 1 − a ) ( log ( 1 − a ) − log ( 1 − u ) ) {\displaystyle D(a\Vert u)=a\left(\log a-\log u\right)+(1-a)\left(\log(1-a)-\log(1-u)\right)} для a , u ∈ [ 0 , 1 ] {\displaystyle a,u\in [0,1]}
В скалярной настройке неравенства Беннета и Бернштейна описывают верхний хвост суммы независимых случайных величин с нулевым средним, которые являются либо ограниченными, либо субэкспоненциальными . В матрицеВ этом случае аналогичные результаты относятся к сумме случайных матриц с нулевым средним.
Рассмотрим конечную последовательность { X k } {\displaystyle \{\mathbf {X} _{k}\}} d {\displaystyle d}
E X k = 0 and λ max ( X k ) ≤ R {\displaystyle \mathbb {E} \mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R} почти наверняка.
Вычислите норму полной дисперсии,
σ 2 = ‖ ∑ k E ( X k 2 ) ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {X} _{k}^{2}){\bigg \Vert }.} Тогда для всех справедлива следующая цепочка неравенств t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( ∑ k X k ) ≥ t } ≤ d ⋅ exp ( − σ 2 R 2 ⋅ h ( R t σ 2 ) ) ≤ d ⋅ exp ( − t 2 σ 2 + R t / 3 ) ≤ { d ⋅ exp ( − 3 t 2 / 8 σ 2 ) for t ≤ σ 2 / R ; d ⋅ exp ( − 3 t / 8 R ) for t ≥ σ 2 / R . {\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}&\leq d\cdot \exp \left(-{\frac {\sigma ^{2}}{R^{2}}}\cdot h\left({\frac {Rt}{\sigma ^{2}}}\right)\right)\\&\leq d\cdot \exp \left({\frac {-t^{2}}{\sigma ^{2}+Rt/3}}\right)\\&\leq {\begin{cases}d\cdot \exp(-3t^{2}/8\sigma ^{2})\quad &{\text{for }}t\leq \sigma ^{2}/R;\\d\cdot \exp(-3t/8R)\quad &{\text{for }}t\geq \sigma ^{2}/R.\\\end{cases}}\end{aligned}}} Функция h ( u ) {\displaystyle h(u)} h ( u ) = ( 1 + u ) log ( 1 + u ) − u {\displaystyle h(u)=(1+u)\log(1+u)-u} u ≥ 0 {\displaystyle u\geq 0}
Рассмотрим конечную последовательность { X k } {\displaystyle \{\mathbf {X} _{k}\}} d {\displaystyle d}
E X k = 0 and E ( X k p ) ⪯ p ! 2 ⋅ R p − 2 A k 2 {\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbb {E} \,(\mathbf {X} _{k}^{p})\preceq {\frac {p!}{2}}\cdot R^{p-2}\mathbf {A} _{k}^{2}} для p = 2 , 3 , 4 , … {\displaystyle p=2,3,4,\ldots }
Вычислите параметр дисперсии,
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} Тогда для всех справедлива следующая цепочка неравенств t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( ∑ k X k ) ≥ t } ≤ d ⋅ exp ( − t 2 / 2 σ 2 + R t ) ≤ { d ⋅ exp ( − t 2 / 4 σ 2 ) for t ≤ σ 2 / R ; d ⋅ exp ( − t / 4 R ) for t ≥ σ 2 / R . {\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}&\leq d\cdot \exp \left({\frac {-t^{2}/2}{\sigma ^{2}+Rt}}\right)\\&\leq {\begin{cases}d\cdot \exp(-t^{2}/4\sigma ^{2})\quad &{\text{for }}t\leq \sigma ^{2}/R;\\d\cdot \exp(-t/4R)\quad &{\text{for }}t\geq \sigma ^{2}/R.\\\end{cases}}\end{aligned}}} Рассмотрим конечную последовательность { Z k } {\displaystyle \{\mathbf {Z} _{k}\}} d 1 × d 2 {\displaystyle d_{1}\times d_{2}}
E Z k = 0 and ‖ Z k ‖ ≤ R {\displaystyle \mathbb {E} \,\mathbf {Z} _{k}=\mathbf {0} \quad {\text{and}}\quad \Vert \mathbf {Z} _{k}\Vert \leq R} почти наверняка.Определите параметр отклонения
σ 2 = max { ‖ ∑ k E ( Z k Z k ∗ ) ‖ , ‖ ∑ k E ( Z k ∗ Z k ) ‖ } . {\displaystyle \sigma ^{2}=\max \left\{{\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {Z} _{k}\mathbf {Z} _{k}^{*}){\bigg \Vert },{\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {Z} _{k}^{*}\mathbf {Z} _{k}){\bigg \Vert }\right\}.} Тогда для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { ‖ ∑ k Z k ‖ ≥ t } ≤ ( d 1 + d 2 ) ⋅ exp ( − t 2 / 2 σ 2 + R t / 3 ) {\displaystyle \Pr \left\{{\bigg \Vert }\sum _{k}\mathbf {Z} _{k}{\bigg \Vert }\geq t\right\}\leq (d_{1}+d_{2})\cdot \exp \left({\frac {-t^{2}/2}{\sigma ^{2}+Rt/3}}\right)} держит. [1]
[ редактировать ] Скалярная версия неравенства Азумы утверждает, что скалярный мартингал демонстрирует нормальную концентрацию вокруг своего среднего значения, а масштаб отклонений контролируется общим максимальным квадратом диапазона разностной последовательности.Ниже приводится расширение настроек матрицы.
Рассмотрим конечную адаптированную последовательность { X k } {\displaystyle \{\mathbf {X} _{k}\}} d {\displaystyle d} { A k } {\displaystyle \{\mathbf {A} _{k}\}}
E k − 1 X k = 0 and X k 2 ⪯ A k 2 {\displaystyle \mathbb {E} _{k-1}\,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}} почти наверняка.
Вычислите параметр дисперсии
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} Тогда для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( ∑ k X k ) ≥ t } ≤ d ⋅ e − t 2 / 8 σ 2 {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}}} Константу 1/8 можно улучшить до 1/2 при наличии дополнительной информации. Один случай имеет место, когда каждое слагаемое X k {\displaystyle \mathbf {X} _{k}} X k {\displaystyle \mathbf {X} _{k}} A k {\displaystyle \mathbf {A} _{k}}
Допущение сложения о том, что слагаемые в матрице Азумы независимы, дает матричное расширение неравенств Хёффдинга .
Рассмотрим конечную последовательность { X k } {\displaystyle \{\mathbf {X} _{k}\}} d {\displaystyle d} { A k } {\displaystyle \{\mathbf {A} _{k}\}}
E X k = 0 and X k 2 ⪯ A k 2 {\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}} почти наверняка.
Тогда для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( ∑ k X k ) ≥ t } ≤ d ⋅ e − t 2 / 8 σ 2 {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}}} где
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} Улучшение этого результата было установлено в ( Mackey et al. 2012 ):для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( ∑ k X k ) ≥ t } ≤ d ⋅ e − t 2 / 2 σ 2 {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}} где
σ 2 = 1 2 ‖ ∑ k A k 2 + E X k 2 ‖ ≤ ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\frac {1}{2}}{\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}+\mathbb {E} \,\mathbf {X} _{k}^{2}{\bigg \Vert }\leq {\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} В скалярной настройке неравенство МакДиармида обеспечивает один общий способ ограничения различий путем применения неравенства Азумы к мартингейлу Дуба . Версия неравенства ограниченных разностей справедлива и в матричной ситуации.
Позволять { Z k : k = 1 , 2 , … , n } {\displaystyle \{Z_{k}:k=1,2,\ldots ,n\}} H {\displaystyle \mathbf {H} } n {\displaystyle n} d {\displaystyle d} { A k } {\displaystyle \{\mathbf {A} _{k}\}}
( H ( z 1 , … , z k , … , z n ) − H ( z 1 , … , z k ′ , … , z n ) ) 2 ⪯ A k 2 , {\displaystyle \left(\mathbf {H} (z_{1},\ldots ,z_{k},\ldots ,z_{n})-\mathbf {H} (z_{1},\ldots ,z'_{k},\ldots ,z_{n})\right)^{2}\preceq \mathbf {A} _{k}^{2},} где z i {\displaystyle z_{i}} z i ′ {\displaystyle z'_{i}} Z i {\displaystyle Z_{i}} i {\displaystyle i}
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} Тогда для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( H ( z ) − E H ( z ) ) ≥ t } ≤ d ⋅ e − t 2 / 8 σ 2 , {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\mathbf {H} (\mathbf {z} )-\mathbb {E} \,\mathbf {H} (\mathbf {z} )\right)\geq t\right\}\leq d\cdot e^{-t^{2}/8\sigma ^{2}},} где z = ( Z 1 , … , Z n ) {\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}
Улучшение этого результата было установлено в ( Полин, Макки и Тропп 2013 ) (см. также ( Полин, Макки и Тропп 2016 )):для всех t ≥ 0 {\displaystyle t\geq 0}
Pr { λ max ( H ( z ) − E H ( z ) ) ≥ t } ≤ d ⋅ e − t 2 / σ 2 , {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\mathbf {H} (\mathbf {z} )-\mathbb {E} \,\mathbf {H} (\mathbf {z} )\right)\geq t\right\}\leq d\cdot e^{-t^{2}/\sigma ^{2}},} где z = ( Z 1 , … , Z n ) {\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})} σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}
Первые оценки этого типа были получены ( Alswede & Winter 2003 ). Напомним приведенную выше теорему для самосопряженной матрицы Гаусса и границ Радемахера :Для конечной последовательности { A k } {\displaystyle \{\mathbf {A} _{k}\}} d {\displaystyle d} { ξ k } {\displaystyle \{\xi _{k}\}} независимых стандартных нормальных или независимых Радемахера случайных величин , тогда
Pr { λ max ( ∑ k ξ k A k ) ≥ t } ≤ d ⋅ e − t 2 / 2 σ 2 {\displaystyle \Pr \left\{\lambda _{\text{max}}\left(\sum _{k}\xi _{k}\mathbf {A} _{k}\right)\geq t\right\}\leq d\cdot e^{-t^{2}/2\sigma ^{2}}} где
σ 2 = ‖ ∑ k A k 2 ‖ . {\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.} Альсведе и Винтер дали бы тот же результат, за исключением
σ A W 2 = ∑ k λ max ( A k 2 ) {\displaystyle \sigma _{AW}^{2}=\sum _{k}\lambda _{\max }\left(\mathbf {A} _{k}^{2}\right)} Для сравнения, σ 2 {\displaystyle \sigma ^{2}} Σ {\displaystyle \Sigma } λ max {\displaystyle \lambda _{\max }} неравенству нормального треугольника ), но может быть намного меньше. Следовательно, приведенная выше теорема дает более точную оценку, чем результат Альсведе–Винтера.
Главный вклад ( Альсведе и Винтер 2003 ) заключался в расширении метода преобразования Лапласа, используемого для доказательства скалярной границы Чернова (см. Ограничение Чернова#Аддитивная форма (абсолютная ошибка) ) на случай самосопряженных матриц. Процедура приведена в выводе ниже. Все последние работы по этой теме следуют одной и той же процедуре, а основные отличия вытекают из последующих шагов. Альсведе и Винтер используют неравенство Голдена-Томпсона для дальнейших действий, тогда как Тропп ( Тропп 2010 ) использует теорему Либа .
Предположим, кто-то захотел изменить длину ряда ( n ) и размерыматрицы ( d ), сохраняя при этом правую часть примерно постоянной. Затемn должно меняться примерно как логарифм d . В нескольких статьях были предприняты попытки установить границу без зависимости от размеров. Рудельсон и Вершинин ( Рудельсон и Вершинин, 2007 ) дают результат для матриц, которые являются внешним произведением двух векторов. ( Маген и Зузиас 2010 ) предоставляют результат без размерной зависимости для матриц низкого ранга . Первоначальный результат был получен независимо от подхода Альсведе-Винтера, но ( Оливейра 2010b ) доказывает аналогичный результат с использованием подхода Альсведе-Винтера.
Наконец, Оливейра ( Оливейра 2010a ) доказывает результат для матричных мартингалов независимо от модели Альсведе-Винтера. Тропп ( Tropp 2011 ) немного улучшает результат, используя структуру Альсведе-Винтера. Ни один результат не представлен в этой статье.
Аргумент преобразования Лапласа, найденный в ( Ahlswede & Winter 2003 ), сам по себе является важным результатом:Позволять Y {\displaystyle \mathbf {Y} }
Pr { λ max ( Y ) ≥ t } ≤ inf θ > 0 { e − θ t ⋅ E [ tr e θ Y ] } . {\displaystyle \Pr \left\{\lambda _{\max }(Y)\geq t\right\}\leq \inf _{\theta >0}\left\{e^{-\theta t}\cdot \operatorname {E} \left[\operatorname {tr} e^{\theta \mathbf {Y} }\right]\right\}.} Чтобы доказать это, исправьте θ > 0 {\displaystyle \theta >0}
Pr { λ max ( Y ) ≥ t } = Pr { λ max ( θ Y ) ≥ θ t } = Pr { e λ max ( θ Y ) ≥ e θ t } ≤ e − θ t E e λ max ( θ Y ) ≤ e − θ t E tr e ( θ Y ) {\displaystyle {\begin{aligned}\Pr \left\{\lambda _{\max }(\mathbf {Y} )\geq t\right\}&=\Pr \left\{\lambda _{\max }(\mathbf {\theta Y} )\geq \theta t\right\}\\&=\Pr \left\{e^{\lambda _{\max }(\theta \mathbf {Y} )}\geq e^{\theta t}\right\}\\&\leq e^{-\theta t}\operatorname {E} e^{\lambda _{\max }(\theta \mathbf {Y} )}\\&\leq e^{-\theta t}\operatorname {E} \operatorname {tr} e^{(\theta \mathbf {Y} )}\end{aligned}}} Предпоследнее неравенство — это неравенство Маркова . Последнее неравенство имеет место, поскольку e λ max ( θ Y ) = λ max ( e θ Y ) ≤ tr ( e θ Y ) {\displaystyle e^{\lambda _{\max }(\theta \mathbf {Y} )}=\lambda _{\max }(e^{\theta \mathbf {Y} })\leq \operatorname {tr} (e^{\theta \mathbf {Y} })} θ {\displaystyle \theta } θ > 0 {\displaystyle \theta >0}
Таким образом, наша задача – понять E [ tr ( e θ Y ) ] {\displaystyle \operatorname {E} [\operatorname {tr} (e^{\theta \mathbf {Y} })]} E e θ Y := M Y ( θ ) {\displaystyle \operatorname {E} e^{\theta \mathbf {Y} }:=\mathbf {M} _{\mathbf {Y} }(\theta )} Альсведе и Винтер 2003 ) и ( Тропп 2010 ) расходятся. Далее следует презентация ( Alswede & Winter 2003 ).
означает Неравенство Голдена – Томпсона , что
tr M X 1 + X 2 ( θ ) ≤ tr [ ( E e θ X 1 ) ( E e θ X 2 ) ] = tr M X 1 ( θ ) M X 2 ( θ ) {\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}+\mathbf {X} _{2}}(\theta )\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\theta \mathbf {X} _{1}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{2}}\right)\right]=\operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}}(\theta )\mathbf {M} _{\mathbf {X} _{2}}(\theta )} Предполагать Y = ∑ k X k {\displaystyle \mathbf {Y} =\sum _{k}\mathbf {X} _{k}} tr M Y ( θ ) {\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )} tr ( A B ) ≤ tr ( A ) λ max ( B ) {\displaystyle \operatorname {tr} (\mathbf {AB} )\leq \operatorname {tr} (\mathbf {A} )\lambda _{\max }(\mathbf {B} )}
tr M Y ( θ ) ≤ tr [ ( E e ∑ k = 1 n − 1 θ X k ) ( E e θ X n ) ] ≤ tr ( E e ∑ k = 1 n − 1 θ X k ) λ max ( E e θ X n ) . {\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{n}}\right)\right]\leq \operatorname {tr} \left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{n}}).} Повторяя это, мы получаем
tr M Y ( θ ) ≤ ( tr I ) [ Π k λ max ( E e θ X k ) ] = d e ∑ k λ max ( log E e θ X k ) {\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )\leq (\operatorname {tr} \mathbf {I} )\left[\Pi _{k}\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{k}})\right]=de^{\sum _{k}\lambda _{\max }\left(\log \operatorname {E} e^{\theta \mathbf {X} _{k}}\right)}} До сих пор мы нашли границу с нижней границей над θ {\displaystyle \theta }
Основным вкладом ( Тропп 2010 ) является применение теоремы Либа , где ( Альсведе и Винтер 2003 ) применили неравенство Голдена-Томпсона . Следствие Троппа следующее: если H {\displaystyle H} X {\displaystyle X}
E tr e H + X ≤ tr e H + log ( E e X ) {\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\mathbf {X} }\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} e^{\mathbf {X} })}} Доказательство: Пусть Y = e X {\displaystyle \mathbf {Y} =e^{\mathbf {X} }}
f ( Y ) = tr e H + log ( Y ) {\displaystyle f(\mathbf {Y} )=\operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}} является вогнутым.Последний шаг — использовать неравенство Дженсена для перемещения математического ожидания внутри функции:
E tr e H + log ( Y ) ≤ tr e H + log ( E Y ) . {\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} \mathbf {Y} )}.} Это дает нам основной результат статьи: субаддитивность логарифма матричной производящей функции.
Позволять X k {\displaystyle \mathbf {X} _{k}} θ ∈ R {\displaystyle \theta \in \mathbb {R} }
tr M ∑ k X k ( θ ) ≤ tr e ∑ k log M X k ( θ ) {\displaystyle \operatorname {tr} \mathbf {M} _{\sum _{k}\mathbf {X} _{k}}(\theta )\leq \operatorname {tr} e^{\sum _{k}\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}} Доказательство: достаточно положить θ = 1 {\displaystyle \theta =1}
E tr e ∑ k θ X k ≤ tr e ∑ k log E e θ X k . {\displaystyle \operatorname {E} \operatorname {tr} e^{\sum _{k}\theta \mathbf {X} _{k}}\leq \operatorname {tr} e^{\sum _{k}\log \operatorname {E} e^{\theta \mathbf {X} _{k}}}.} Для завершения доказательства воспользуемся законом полного ожидания . Позволять E k {\displaystyle \operatorname {E} _{k}} X 1 , … , X k {\displaystyle \mathbf {X} _{1},\ldots ,\mathbf {X} _{k}} X i {\displaystyle \mathbf {X} _{i}}
E k − 1 e X k = E e X k . {\displaystyle \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\operatorname {E} e^{\mathbf {X} _{k}}.} Определять Ξ k = log E k − 1 e X k = log M X k ( θ ) {\displaystyle \mathbf {\Xi } _{k}=\log \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}
Наконец, у нас есть
E tr e ∑ k = 1 n X k = E 0 ⋯ E n − 1 tr e ∑ k = 1 n − 1 X k + X n ≤ E 0 ⋯ E n − 2 tr e ∑ k = 1 n − 1 X k + log ( E n − 1 e X n ) = E 0 ⋯ E n − 2 tr e ∑ k = 1 n − 2 X k + X n − 1 + Ξ n ⋮ = tr e ∑ k = 1 n Ξ k {\displaystyle {\begin{aligned}\operatorname {E} \operatorname {tr} e^{\sum _{k=1}^{n}\mathbf {X} _{k}}&=\operatorname {E} _{0}\cdots \operatorname {E} _{n-1}\operatorname {tr} e^{\sum _{k=1}^{n-1}\mathbf {X} _{k}+\mathbf {X} _{n}}\\&\leq \operatorname {E} _{0}\cdots \operatorname {E} _{n-2}\operatorname {tr} e^{\sum _{k=1}^{n-1}\mathbf {X} _{k}+\log(\operatorname {E} _{n-1}e^{\mathbf {X} _{n}})}\\&=\operatorname {E} _{0}\cdots \operatorname {E} _{n-2}\operatorname {tr} e^{\sum _{k=1}^{n-2}\mathbf {X} _{k}+\mathbf {X} _{n-1}+\mathbf {\Xi } _{n}}\\&\vdots \\&=\operatorname {tr} e^{\sum _{k=1}^{n}\mathbf {\Xi } _{k}}\end{aligned}}} где на каждом шаге m мы используем следствие Троппа с
H m = ∑ k = 1 m − 1 X k + ∑ k = m + 1 n Ξ k {\displaystyle \mathbf {H} _{m}=\sum _{k=1}^{m-1}\mathbf {X} _{k}+\sum _{k=m+1}^{n}\mathbf {\Xi } _{k}} Следующее следует непосредственно из предыдущего результата:
Pr { λ max ( ∑ k X k ) ≥ t } ≤ inf θ > 0 { e − θ t tr e ∑ k log M X k ( θ ) } {\displaystyle \Pr \left\{\lambda _{\max }\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}\leq \inf _{\theta >0}\left\{e^{-\theta t}\operatorname {tr} e^{\sum _{k}\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}\right\}} Все приведенные выше теоремы вытекают из этой оценки; теоремы заключаются в различных способах ограничения нижней границы. Эти шаги существенно проще приведенных доказательств.
Альсведе, Р.; Зима, А. (2003). «Сильный конверс для идентификации по квантовым каналам». Транзакции IEEE по теории информации 48 (3): 569–579. arXiv : Quant-ph/0012127 дои : 10.1109/18.985947 . S2CID 523176 . Макки, Л.; Джордан, Мичиган; Чен, Р.Ю.; Фаррелл, Б.; Тропп, Дж. А. (2012). «Матричные неравенства концентрации методом сменных пар». Анналы вероятности . 42 (3): 906–945. arXiv : 1201.6002 дои : 10.1214/13-AOP892 . S2CID 9635314 . Маген, А. ; Зузиас, А. (2010). «Матричные границы низкого ранга Чернова и приближенное умножение матриц». arXiv : 1005.2724 cs.DS ]. Оливейра, Род-Айленд (2010a). «Концентрация матрицы смежности и лапласиана в случайных графах с независимыми ребрами». arXiv : 0911.0600 math.CO ]. Оливейра, Род-Айленд (2010b). «Суммы случайных эрмитовых матриц и неравенство Рудельсона». arXiv : 1004.3821 мат.PR ]. Полин, Д.; Макки, Л.; Тропп, Дж. А. (2013). «Вывод матричных неравенств концентрации из связей ядра». arXiv : 1305.0612 мат.PR ]. Полин, Д.; Макки, Л.; Тропп, Дж. А. (2016). «Неравенства Эфрона – Штейна для случайных матриц». Анналы вероятности . 44 (5): 3431–3473. arXiv : 1408.3470 дои : 10.1214/15-AOP1054 . S2CID 16263460 . Рудельсон, М.; Вершинин Р. (2007). «Выборка из больших матриц: подход посредством геометрического функционального анализа». Журнал Ассоциации вычислительной техники . 54 (4-е изд.). arXiv : математика/9608208 Бибкод : 1996math......8208R . дои : 10.1145/1255443.1255449 . S2CID 6054789 . Тропп, Дж. (2011). «Неравенство Фридмана для матричных мартингалов». arXiv : 1101.3039 мат.PR ]. Тропп, Дж. (2010). «Удобные хвостовые оценки сумм случайных матриц». Основы вычислительной математики . 12 (4): 389–434. arXiv : 1004.4389 дои : 10.1007/s10208-011-9099-z . S2CID 17735965 . 
![{\displaystyle \Pr \left\{\lambda _{\text{min}} \left(\sum _{k}\mathbf {X} _{k}\right)\leq (1-\delta)\mu _{\text{min}}\right\}\leq d\cdot \left[{\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right ]^{\mu _{\text{min}}/R}\quad {\text{for }}\delta \in [0,1){\text{, и}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46592521df777091d4e7f72648c36b2ece4156c9)
![{\displaystyle \Pr \left\{\lambda _ {\text{max}} \left(\sum _{k}\mathbf {X} _{k}\right)\geq (1+\delta)\mu _{\text{max}}\right\}\leq d\cdot \left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right] ^{\mu _{\text{max}}/R}\quad {\text{for }}\delta \geq 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/454bbdcdfde7b3d63d754368c060ca700adea928)
![{\displaystyle a,u\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1fdb0ebb73b92634be0702a271dd4ee6edc785f6)
![{\displaystyle \Pr \left\{\lambda _{\max }(Y)\geq t\right\}\leq \inf _{\theta >0}\left\{e^{-\theta t}\ cdot \operatorname {E} \left[\operatorname {tr} e^{\theta \mathbf {Y} }\right]\right\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4f51d7959a8d6fa7014048f8e66eed89510ec47)
![{\displaystyle \operatorname {E} [\operatorname {tr} (e^{\theta \mathbf {Y}})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4e9bd7685ee021d247f26c1a2d7bd711a4491a4)
![{\displaystyle \operatorname {tr} \mathbf {M} _ {\mathbf {X} _{1}+\mathbf {X} _{2}}(\theta)\leq \operatorname {tr} \left[\ left(\operatorname {E} e^{\theta \mathbf {X} _{1}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{2}}\right )\right]=\operatorname {tr} \mathbf {M} _{\mathbf {X} _{1}}(\theta )\mathbf {M} _{\mathbf {X} _{2}}(\ тэта )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3693e804125725156cfa88849136e58fe55471c8)
![{\displaystyle \operatorname {tr} \mathbf {M} _ {\mathbf {Y} }(\theta)\leq \operatorname {tr} \left[\left(\operatorname {E} e^{\sum _{ k=1}^{n-1}\theta \mathbf {X} _{k}}\right)\left(\operatorname {E} e^{\theta \mathbf {X} _{n}}\right )\right]\leq \operatorname {tr} \left(\operatorname {E} e^{\sum _{k=1}^{n-1}\theta \mathbf {X} _{k}}\right )\lambda _{\max }(\operatorname {E} e^{\theta \mathbf {X} _{n}}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c30f06d2e5152a1b1e46e154ec20c7bcf80f9f9)
![{\displaystyle \operatorname {tr} \mathbf {M} _ {\mathbf {Y} }(\theta)\leq (\operatorname {tr} \mathbf {I})\left[\Pi _{k}\lambda _ {\max }(\operatorname {E} e^{\theta \mathbf {X} _{k}})\right]=de^{\sum _{k}\lambda _{\max }\left( \log \operatorname {E} e^{\theta \mathbf {X} _{k}}\right)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dddbf61e0f6c90bf2239928f9284603f8ff5e4cb)
