Граница Матрицы Чернова - Википедия - 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 { хи _ {к} }}$ конечная последовательность независимый стандарт нормальный или независимый Радемахер случайные переменные.

Тогда для всех ${ Displaystyle т 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 { хи _ {к} }}$ - конечная последовательность независимых стандартных нормальных или независимых случайных величин Радемахера. Определить параметр дисперсии

${ 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 т 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} successq 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} справа) 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} successq 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 {, и}}}$

${ 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 (а Vert и) = а влево ( журнал а- журнал и право) + (1-а) влево ( журнал (1-а) - журнал (1-и) верно)}$

за ${ Displaystyle а, и в [0,1]}$.

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

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

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

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

${ displaystyle mathbf {X} _ {k} successq 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 т geq 0}$:

${ Displaystyle { begin {align} 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 {case} 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 {выровнено}}}$

Функция ${ Displaystyle ч (и)}$ определяется как ${ Displaystyle ч (и) = (1 + и) журнал (1 + и) -у}$ за ${ 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}) prevq { 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 т geq 0}$:

${ Displaystyle { begin {align} 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 { case} 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 {case}} end {align}}}$

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

Рассмотрим конечную последовательность ${ 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 т 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} prevq mathbf {A} _ {k} ^ {2}}$

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

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

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

Тогда для всех ${ Displaystyle т 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} prevq mathbf {A} _ {k} ^ {2}}$

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

Тогда для всех ${ Displaystyle т 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 т 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} prevq mathbf {A} _ {k} ^ {2},}$

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

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

Тогда для всех ${ Displaystyle т 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 т 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 { хи _ {к} }}$ конечная последовательность независимый стандарт нормальный или независимый Радемахер случайные величины, тогда

${ 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 {align} 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 {выровнено}}}$

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

Предполагать ${ Displaystyle mathbf {Y} = сумма _ {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} = е ^ { mathbf {X}}}$. Тогда теорема Либа говорит нам, что

${ Displaystyle е ( 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} _ {я}}$ независимы,

${ 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 {align} 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}} конец {выровнено}}}$

где на каждом шаге 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 }}$

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

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

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