Матрица Граница Чернова - Matrix Chernoff bound

Для некоторых приложений в линейная алгебра, полезно знать свойства распределение вероятностей из крупнейших собственное значение из конечная сумма из случайные матрицы. Предполагать ${\displaystyle \{\mathbf {X} _{k}\}}$ конечная последовательность случайных матриц. По аналогии с известным Граница Чернова для сумм скаляров ищется оценка для заданного параметрат:

${\displaystyle \Pr \left\{\lambda _{\max }\left(\sum _{k}\mathbf {X} _{k}\right)\geq t\right\}}$

Следующие теоремы дают ответ на этот общий вопрос при различных предположениях; эти предположения называются ниже по аналогии с их классическими скалярными аналогами. Все эти теоремы можно найти в (Тропп 2010 ), как частное применение общего результата, который выводится ниже. Дается краткое содержание родственных работ.

Матрица Гаусса и рядов Радемахера

Случай самосопряженных матриц

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {A} _{k}\}}$ фиксированных самосопряженных матриц размерности ${\displaystyle d}$, и разреши ${\displaystyle \{\xi _{k}\}}$ конечная последовательность независимый стандарт нормальный или независимый Радемахер случайные переменные.

Тогда для всех ${\displaystyle t\geq 0}$,

${\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}}}$

куда

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Прямоугольный корпус

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {B} _{k}\}}$ фиксированных самосопряженных матриц размерности ${\displaystyle d_{1}\times d_{2}}$, и разреши ${\displaystyle \{\xi _{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\}.}$

Тогда для всех ${\displaystyle t\geq 0}$,

${\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}}.}$

Матричные неравенства Чернова

Классический Границы Чернова относятся к сумме независимых, неотрицательных и равномерно ограниченных случайных величин. В матричной установке аналогичная теорема касается суммы положительно-полуопределенный случайные матрицы, подвергнутые равномерной оценке собственных значений.

Матрица Чернова I

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {X} _{k}\}}$ независимых, случайных, самосопряженных матриц размерности ${\displaystyle d}$Предположим, что каждая случайная матрица удовлетворяет

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}$

почти наверняка.

Определять

${\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).}$

потом

${\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}}}$

${\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.}$

Матрица Чернова II

Рассмотрим последовательность ${\displaystyle \{\mathbf {X} _{k}:k=1,2,\ldots ,n\}}$ независимых, случайных, самосопряженных матриц, удовлетворяющих

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq 1}$

почти наверняка.

Вычислить минимальное и максимальное собственные значения среднего ожидания,

${\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).}$

потом

${\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}}}$

${\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.}$

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

${\displaystyle D(a\Vert u)=a\left(\log a-\log u\right)+(1-a)\left(\log(1-a)-\log(1-u)\right)}$

за ${\displaystyle a,u\in [0,1]}$.

Матричные неравенства Беннета и Бернштейна

В скалярной настройке Неравенства Беннета и Бернштейна описывают верхний хвост суммы независимых случайных величин с нулевым средним, которые либо ограничены, либо субэкспоненциальный. В матричном случае аналогичные результаты относятся к сумме случайных матриц с нулевым средним.

Ограниченный случай

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {X} _{k}\}}$ независимых, случайных, самосопряженных матриц размерности ${\displaystyle d}$Предположим, что каждая случайная матрица удовлетворяет

${\displaystyle \mathbf {X} _{k}\succeq \mathbf {0} \quad {\text{and}}\quad \lambda _{\text{max}}(\mathbf {X} _{k})\leq R}$

почти наверняка.

Вычислите норму общей дисперсии,

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbb {E} \,(\mathbf {X} _{k}^{2}){\bigg \Vert }.}$

Тогда для всех справедлива следующая цепочка неравенств. ${\displaystyle t\geq 0}$:

${\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}}}$

Функция ${\displaystyle h(u)}$ определяется как ${\displaystyle h(u)=(1+u)\log(1+u)-u}$ за ${\displaystyle u\geq 0}$.

Субэкспоненциальный случай

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {X} _{k}\}}$ независимых, случайных, самосопряженных матриц размерности ${\displaystyle d}$.Предположить, что

${\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}}$

за ${\displaystyle p=2,3,4,\ldots }$.

Вычислить параметр дисперсии,

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Тогда для всех справедлива следующая цепочка неравенств. ${\displaystyle t\geq 0}$:

${\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}}}$

Прямоугольный корпус

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {Z} _{k}\}}$ независимых случайных матриц размерности ${\displaystyle d_{1}\times d_{2}}$Предположим, что каждая случайная матрица удовлетворяет

${\displaystyle \mathbb {E} \,\mathbf {Z} _{k}=\mathbf {0} \quad {\text{and}}\quad \Vert \mathbf {Z} _{k}\Vert \leq R}$

почти наверняка. Определите параметр дисперсии

${\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\}.}$

Тогда для всех ${\displaystyle t\geq 0}$

${\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]

Матричные неравенства Адзумы, Хёффдинга и МакДиармида

Матрица Адзума

Скалярная версия Неравенство Адзумы утверждает, что скаляр мартингейл показывает нормальную концентрацию относительно своего среднего значения, а шкала отклонений контролируется общим максимальным квадратом диапазона разностной последовательности. Ниже показано расширение в настройке матрицы.

Рассмотрим конечную адаптированную последовательность ${\displaystyle \{\mathbf {X} _{k}\}}$ самосопряженных матриц размерности ${\displaystyle d}$, и фиксированная последовательность ${\displaystyle \{\mathbf {A} _{k}\}}$ самосопряженных матриц, удовлетворяющих

${\displaystyle \mathbb {E} _{k-1}\,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}$

почти наверняка.

Вычислить параметр дисперсии

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Тогда для всех ${\displaystyle t\geq 0}$

${\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 при наличии дополнительной информации. Один случай возникает, когда каждое слагаемое ${\displaystyle \mathbf {X} _{k}}$ условно симметрична. Другой пример требует предположения, что ${\displaystyle \mathbf {X} _{k}}$ почти наверняка ездит с ${\displaystyle \mathbf {A} _{k}}$.

Матрица Хёффдинг

Добавление предположения о том, что слагаемые в Matrix Azuma независимы, дает матричное расширение Неравенства Хёффдинга.

Рассмотрим конечную последовательность ${\displaystyle \{\mathbf {X} _{k}\}}$ независимых, случайных, самосопряженных матриц размерности ${\displaystyle d}$, и разреши ${\displaystyle \{\mathbf {A} _{k}\}}$ - последовательность фиксированных самосопряженных матриц. Предположим, что каждая случайная матрица удовлетворяет

${\displaystyle \mathbb {E} \,\mathbf {X} _{k}=\mathbf {0} \quad {\text{and}}\quad \mathbf {X} _{k}^{2}\preceq \mathbf {A} _{k}^{2}}$

почти наверняка.

Тогда для всех ${\displaystyle t\geq 0}$

${\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}}}$

куда

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Улучшение этого результата было установлено в (Mackey et al. 2012 г. ):для всех ${\displaystyle t\geq 0}$

${\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}}}$

куда

${\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 }.}$

Матричная ограниченная разность (МакДиармид)

В скалярной настройке Неравенство МакДиармида предоставляет один общий способ ограничения различий путем применения Неравенство Адзумы к Дуб мартингейл. В матричной установке выполняется вариант неравенства ограниченных разностей.

Позволять ${\displaystyle \{Z_{k}:k=1,2,\ldots ,n\}}$ - независимое семейство случайных величин, и пусть ${\displaystyle \mathbf {H} }$ быть функцией, отображающей ${\displaystyle n}$ переменных в самосопряженную матрицу размерности ${\displaystyle d}$.Рассмотрим последовательность ${\displaystyle \{\mathbf {A} _{k}\}}$ фиксированных самосопряженных матриц, удовлетворяющих

${\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},}$

куда ${\displaystyle z_{i}}$ и ${\displaystyle z'_{i}}$ диапазон всех возможных значений ${\displaystyle Z_{i}}$ для каждого индекса ${\displaystyle i}$. Вычислить параметр дисперсии

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Тогда для всех ${\displaystyle t\geq 0}$

${\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}},}$

куда ${\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}$.

Улучшение этого результата было установлено в (Полин, Макки и Тропп, 2013 г. ) (смотрите также (Полин, Макки и Тропп, 2016 г. )):для всех ${\displaystyle t\geq 0}$

${\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}},}$

куда ${\displaystyle \mathbf {z} =(Z_{1},\ldots ,Z_{n})}$ и${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Обзор родственных теорем

Первые оценки этого типа были получены с помощью (Альсведе и зима 2003 ). Напомним Теорема выше для самосопряженных матричных оценок Гаусса и Радемахера: Для конечной последовательности ${\displaystyle \{\mathbf {A} _{k}\}}$ фиксированных самосопряженных матриц размерности ${\displaystyle d}$ и для ${\displaystyle \{\xi _{k}\}}$ конечная последовательность независимый стандарт нормальный или независимый Радемахер случайные величины, тогда

${\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}}}$

куда

${\displaystyle \sigma ^{2}={\bigg \Vert }\sum _{k}\mathbf {A} _{k}^{2}{\bigg \Vert }.}$

Альсведе и Винтер дадут тот же результат, за исключением

${\displaystyle \sigma _{AW}^{2}=\sum _{k}\lambda _{\max }\left(\mathbf {A} _{k}^{2}\right)}$.

Для сравнения: ${\displaystyle \sigma ^{2}}$ в теореме выше коммутирует ${\displaystyle \Sigma }$ и ${\displaystyle \lambda _{\max }}$; то есть это наибольшее собственное значение суммы, а не сумма наибольших собственных значений. Оно никогда не превышает значения Альсведе – Винтера ( норма неравенство треугольника ), но может быть намного меньше. Следовательно, приведенная выше теорема дает более жесткую оценку, чем результат Альсведе – Винтера.

Главный вклад (Альсведе и зима 2003 ) был расширением метода преобразования Лапласа, использованного для доказательства скалярной границы Чернова (см. Граница Чернова # Теорема для аддитивной формы (абсолютная ошибка) ) на случай самосопряженных матриц. Процедура, приведенная в происхождение ниже. Все недавние работы по этой теме следуют той же процедуре, и основные отличия вытекают из последующих шагов. Ahlswede & Winter используют Неравенство Голдена – Томпсона для продолжения, тогда как Tropp (Тропп 2010 ) использует Теорема Либа.

Предположим, что кто-то хочет изменить длину ряда (п) и размерности матриц (d), при этом правая часть остается примерно постоянной. Thenn должна варьироваться примерно в зависимости от журналаd. В нескольких работах предпринимались попытки установить границу без зависимости от размеров. Рудельсон и Вершинин (Рудельсон и Вершинин 2007 ) дают результат для матриц, которые являются внешним произведением двух векторов. (Magen & Zouzias 2010 ) дают результат без размерной зависимости для матриц низкого ранга. Первоначальный результат был получен независимо от подхода Альсведе – Винтера, но (Оливейра 2010b ) Ошибка harv: цель отсутствует: CITEREFOliveira2010b (помощь) доказывает аналогичный результат с использованием подхода Альсведе – Винтера.

Наконец, Оливейра (Оливьера 2010a ) Ошибка harv: цель отсутствует: CITEREFOliviera2010a (помощь) доказывает результат для матричных мартингалов независимо от модели Альсведе – Винтера. Тропп (Тропп 2011 ) немного улучшает результат при использовании схемы Алсведе – Винтера. Ни один из результатов не представлен в этой статье.

Вывод и доказательство

Альсведе и зима

Аргумент преобразования Лапласа, найденный в (Альсведе и зима 2003 ) является самостоятельным значительным результатом: Пусть ${\displaystyle \mathbf {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\}.}$

Чтобы доказать это, исправим ${\displaystyle \theta >0}$. потом

${\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}}}$

Предпоследнее неравенство Неравенство Маркова. Последнее неравенство выполнено, поскольку ${\displaystyle e^{\lambda _{\max }\theta \mathbf {Y} }=\lambda _{\max }e^{\theta \mathbf {Y} }\leq \operatorname {tr} e^{\theta \mathbf {Y} }}$. Поскольку самая левая величина не зависит от ${\displaystyle \theta }$, инфимум закончился ${\displaystyle \theta >0}$ остается его верхней границей.

Итак, наша задача понять ${\displaystyle \operatorname {E} \operatorname {tr} e^{\theta \mathbf {Y} }}$ Тем не менее, поскольку след и математическое ожидание линейны, мы можем их коммутировать, поэтому достаточно рассмотреть ${\displaystyle \operatorname {E} e^{\theta \mathbf {Y} }:=\mathbf {M} _{\mathbf {Y} }(\theta )}$, которую мы называем производящей функцией матрицы. Вот где методы (Альсведе и зима 2003 ) и (Тропп 2010 ) расходятся. Сразу после этого следует представление (Альсведе и зима 2003 ).

В Неравенство Голдена – Томпсона подразумевает, что

${\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 )}$, где мы несколько раз использовали линейность математического ожидания.

Предполагать ${\displaystyle \mathbf {Y} =\sum _{k}\mathbf {X} _{k}}$. Мы можем найти верхнюю оценку для ${\displaystyle \operatorname {tr} \mathbf {M} _{\mathbf {Y} }(\theta )}$ повторяя этот результат. Отмечая, что ${\displaystyle \operatorname {tr} (\mathbf {AB} )\leq \operatorname {tr} (\mathbf {A} )\lambda _{\max }(\mathbf {B} )}$, тогда

${\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}}).}$

Повторяя это, мы получаем

${\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 ) применил Неравенство Голдена – Томпсона. Следствие Троппа следующее: если ${\displaystyle H}$ - фиксированная самосопряженная матрица и ${\displaystyle X}$ - случайная самосопряженная матрица, то

${\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\mathbf {X} }\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} e^{\mathbf {X} })}}$

Доказательство: Пусть ${\displaystyle \mathbf {Y} =e^{\mathbf {X} }}$. Тогда теорема Либа говорит нам, что

${\displaystyle f(\mathbf {Y} )=\operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}}$

вогнутая. Последний шаг - использовать Неравенство Дженсена чтобы переместить ожидание внутри функции:

${\displaystyle \operatorname {E} \operatorname {tr} e^{\mathbf {H} +\log(\mathbf {Y} )}\leq \operatorname {tr} e^{\mathbf {H} +\log(\operatorname {E} \mathbf {Y} )}.}$

Это дает нам главный результат статьи: субаддитивность журнала производящей функции матрицы.

Субаддитивность log mgf

Позволять ${\displaystyle \mathbf {X} _{k}}$ - конечная последовательность независимых случайных самосопряженных матриц. Тогда для всех ${\displaystyle \theta \in \mathbb {R} }$,

${\displaystyle \operatorname {tr} \mathbf {M} _{\sum _{k}\mathbf {X} _{k}}(\theta )\leq \operatorname {tr} e^{\sum _{k}\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}}$

Доказательство: достаточно позволить ${\displaystyle \theta =1}$. Расширяя определения, нам нужно показать, что

${\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}}}.}$

Для завершения доказательства воспользуемся закон полного ожидания. Позволять ${\displaystyle \operatorname {E} _{k}}$ ожидание обусловлено ${\displaystyle \mathbf {X} _{1},\ldots ,\mathbf {X} _{k}}$. Поскольку мы предполагаем, что все ${\displaystyle \mathbf {X} _{i}}$ независимы,

${\displaystyle \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\operatorname {E} e^{\mathbf {X} _{k}}.}$

Определять ${\displaystyle \mathbf {\Xi } _{k}=\log \operatorname {E} _{k-1}e^{\mathbf {X} _{k}}=\log \mathbf {M} _{\mathbf {X} _{k}}(\theta )}$.

Наконец, у нас есть

${\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 мы используем следствие Троппа с

${\displaystyle \mathbf {H} _{m}=\sum _{k=1}^{m-1}\mathbf {X} _{k}+\sum _{k=m+1}^{n}\mathbf {\Xi } _{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\}}$

Все приведенные выше теоремы выводятся из этой оценки; теоремы состоят в различных способах ограничения нижней грани. Эти шаги значительно проще, чем приведенные доказательства.

Рекомендации

1. Удобные хвостовые границы для сумм случайных матриц

• Ahlswede, R .; Уинтер А. (2003). «Сильный разговор для идентификации через квантовые каналы». IEEE Transactions по теории информации. 48 (3): 569–579. arXiv:Quant-ph / 0012127. Дои:10.1109/18.985947. S2CID  523176.
• Mackey, L .; Jordan, M. I .; Chen, R. Y .; Farrell, B .; Тропп, Дж. А. (2012). «Неравенства концентраций матриц методом обменных пар». Анналы вероятности. 42 (3): 906–945. arXiv:1201.6002. Дои:10.1214 / 13-AOP892. S2CID  9635314.
• Маген, А.; Зузиас, А. (2010). "Матричнозначные границы Чернова низкого ранга и приближенное матричное умножение". arXiv:1005.2724 [cs.DS ].
• Оливейра, Р.И. (2010). «Концентрация матрицы смежности и лапласиана в случайных графах с независимыми ребрами». arXiv:0911.0600 [math.CO ].
• Оливейра, Р.И. (2010). «Суммы случайных эрмитовых матриц и неравенство Рудельсона». arXiv:1004.3821 [math.PR ].
• Паулин, Д .; Mackey, L .; Тропп, Дж. А. (2013). «Получение матричных концентрационных неравенств из связей ядра». arXiv:1305.0612 [math.PR ].
• Паулин, Д .; Mackey, L .; Тропп, Дж. А. (2016). «Неравенства Эфрона – Стейна для случайных матриц». Анналы вероятности. 44 (5): 3431–3473. arXiv:1408.3470. Дои:10.1214 / 15-AOP1054. S2CID  16263460.
• Рудельсон, М .; Вершинин, Р. (2007). «Выборка из больших матриц: подход через геометрический функциональный анализ». J. Assoc. Comput. Мах. (4-е изд.). 54. arXiv:математика / 9608208. Bibcode:1996математика ...... 8208R. Дои:10.1145/1255443.1255449. S2CID  6054789.
• Тропп, Дж. (2011). «Неравенство Фридмана для матричных мартингалов». arXiv:1101.3039 [math.PR ].
• Тропп, Дж. (2010). «Удобные хвостовые границы для сумм случайных матриц». Основы вычислительной математики. 12 (4): 389–434. arXiv:1004.4389. Дои:10.1007 / s10208-011-9099-z. S2CID  17735965.