Следующие теоремы дают ответ на этот общий вопрос при различных предположениях; эти предположения названы ниже по аналогии с их классическими скалярными аналогами. Все эти теоремы можно найти в ( Tropp 2010 ) как конкретное приложение общего результата, который выводится ниже. Дается краткое содержание родственных работ.
Классические оценки Чернова относятся к сумме независимых, неотрицательных и равномерно ограниченных случайных величин. В матричной установке аналогичная теорема касается суммы положительно-полуопределенных случайных матриц, подвергнутых равномерной оценке собственных значений.
Матрица Чернова I
Рассмотрим конечную последовательность независимых, случайных, самосопряженных матриц размерности . Предположим, что каждая случайная матрица удовлетворяет
Вычислить минимальное и максимальное собственные значения среднего ожидания,
потом
Расхождение двоичной информации определяется как
для .
Матричные неравенства Беннета и Бернштейна
В скалярной ситуации неравенства Беннета и Бернштейна описывают верхний хвост суммы независимых случайных величин с нулевым средним, которые являются либо ограниченными, либо субэкспоненциальными . В матричном случае аналогичные результаты относятся к сумме случайных матриц с нулевым средним.
Ограниченный случай
Рассмотрим конечную последовательность независимых, случайных, самосопряженных матриц размерности . Предположим, что каждая случайная матрица удовлетворяет
почти наверняка.
Вычислить норму общей дисперсии,
Тогда для всех справедлива следующая цепочка неравенств. :
Матричные неравенства Адзумы, Хёффдинга и МакДиармида
Матрица Адзума
Скалярная версия неравенства Адзумы утверждает, что скалярный мартингал демонстрирует нормальную концентрацию относительно своего среднего значения, а масштаб отклонений контролируется общим максимальным квадратом диапазона разностной последовательности. Ниже приводится расширение в настройке матрицы.
Константа 1/8 может быть увеличена до 1/2 при наличии дополнительной информации. Один случай возникает, когда каждое слагаемоеусловно симметрична. Другой пример требует предположения, что почти наверняка добирается до .
Матрица Хёффдинг
Добавление предположения о том, что слагаемые в Matrix Azuma независимы, дает матричное расширение неравенств Хёффдинга .
Рассмотрим конечную последовательность независимых, случайных, самосопряженных матриц размерности , и разреши - последовательность фиксированных самосопряженных матриц. Предположим, что каждая случайная матрица удовлетворяет
почти наверняка.
Тогда для всех
где
Улучшение этого результата было установлено в ( Mackey et al. 2012 ): для всех
где
Матричная ограниченная разность (МакДиармид)
В скалярной постановке неравенство МакДиармида предоставляет один общий способ ограничения различий, применяя неравенство Адзумы к мартингейлу Дуба . В матричной постановке выполняется вариант неравенства ограниченных разностей.
Позволять - независимое семейство случайных величин, и пусть быть функцией, отображающей переменных в самосопряженную матрицу размерности . Рассмотрим последовательность фиксированных самосопряженных матриц, удовлетворяющих
где а также диапазон всех возможных значений для каждого индекса . Вычислить параметр дисперсии
Альсведе и Винтер дадут тот же результат, за исключением
.
Для сравнения: в теореме выше коммутирует а также ; то есть это наибольшее собственное значение суммы, а не сумма наибольших собственных значений. Оно никогда не бывает больше значения Алсведе – Винтера (по неравенству треугольника нормы ), но может быть намного меньше. Следовательно, приведенная выше теорема дает более жесткую оценку, чем результат Альсведе – Винтера.
Предположим, кто-то желает изменить длину ряда ( n ) и размеры матриц ( d ), сохраняя при этом правую часть приблизительно постоянной. Тогда n должно изменяться примерно как логарифм d . В нескольких работах предпринята попытка установить границу без зависимости от размеров. Рудельсон и Вершинин ( Рудельсон и Вершинин, 2007 ) дают результат для матриц, которые являются внешним произведением двух векторов. ( Magen & Zouzias 2010 ) дают результат без размерной зависимости для матриц низкого ранга . Первоначальный результат был получен независимо от подхода Альсведе – Винтера, но ( Oliveira 2010b )ошибка harv: цель отсутствует: CITEREFOliveira2010b ( справка ) доказывает аналогичный результат с использованием подхода Альсведе – Винтера.
Наконец, Оливейра ( Oliviera 2010a )ошибка harv: цель отсутствует: CITEREFOliviera2010a ( справка )доказывает результат для матричных мартингалов независимо от модели Альсведе – Винтера. Tropp ( Tropp 2011 ) немного улучшает результат при использовании структуры Алсведе – Винтера. Ни один из результатов не представлен в этой статье.
Вывод и доказательство
Альсведе и зима
Аргумент преобразования Лапласа, найденный в ( Ahlswede & Winter 2003 ), сам по себе является значительным результатом: пусть- случайная самосопряженная матрица. потом
Чтобы доказать это, исправим . потом
Предпоследнее неравенство - это неравенство Маркова . Последнее неравенство выполняется, поскольку. Поскольку самая левая величина не зависит от, инфимум закончился остается его верхней границей.
Таким образом, наша задача понять Тем не менее, поскольку след и математическое ожидание линейны, мы можем коммутировать их, поэтому достаточно рассмотреть , которую мы называем производящей функцией матрицы. Вот где расходятся методы ( Ahlswede & Winter 2003 ) и ( Tropp 2010 ). Сразу после этого следует презентация ( Ahlswede & Winter 2003 ).
, где мы несколько раз использовали линейность математического ожидания.
Предполагать . Мы можем найти верхнюю оценку дляповторяя этот результат. Отмечая, что, тогда
Повторяя это, мы получаем
До сих пор мы нашли границу с точной нижней гранью по . В свою очередь, это может быть ограничено. Во всяком случае, можно увидеть, как возникает оценка Альсведе – Винтера как сумма наибольших собственных значений.
Тропп
Главный вклад ( Tropp 2010 ) - это применение теоремы Либа, где ( Ahlswede & Winter 2003 ) применили неравенство Голдена – Томпсона . Следствие Троппа следующее: если фиксированная самосопряженная матрица и - случайная самосопряженная матрица, то
Доказательство: Пусть . Тогда теорема Либа говорит нам, что
вогнутая. Последний шаг - использовать неравенство Дженсена для перемещения математического ожидания внутри функции:
Это дает нам главный результат статьи: субаддитивность журнала производящей функции матрицы.
Субаддитивность log mgf
Позволять - конечная последовательность независимых случайных самосопряженных матриц. Тогда для всех,
Доказательство: достаточно позволить . Расширяя определения, нам нужно показать, что
Для завершения доказательства воспользуемся законом полного ожидания . Позволять быть ожиданием, обусловленным . Поскольку мы предполагаем, что все независимы,
Определять .
Наконец, у нас есть
где на каждом шаге m мы используем следствие Троппа с
Мастер хвост связан
Следующее сразу следует из предыдущего результата:
Все приведенные выше теоремы выводятся из этой оценки; теоремы состоят в различных способах ограничения нижней грани. Эти шаги значительно проще, чем приведенные доказательства.
Рекомендации
^ Удобные хвостовые границы для сумм случайных матриц
Ahlswede, R .; Уинтер, А. (2003). «Сильный разговор для идентификации через квантовые каналы». IEEE Transactions по теории информации . 48 (3): 569–579. arXiv : квант-ph / 0012127 . DOI : 10.1109 / 18.985947 . S2CID 523176 .
Mackey, L .; Иордания, Мичиган; Chen, RY; Farrell, B .; Тропп, Дж. А. (2012). «Неравенства концентраций матриц методом обменных пар». Летопись вероятности . 42 (3): 906–945. arXiv : 1201.6002 . DOI : 10.1214 / 13-AOP892 . S2CID 9635314 .
Маген, А .; Зузиас, А. (2010). "Матричнозначные границы Чернова низкого ранга и приближенное матричное умножение". arXiv : 1005.2724 [ cs.DS ].
Оливейра, Р.И. (2010). «Концентрация матрицы смежности и лапласиана в случайных графах с независимыми ребрами». arXiv : 0911.0600 [ math.CO ].
Паулин, Д .; Mackey, L .; Тропп, Дж. А. (2013). «Получение матричных концентрационных неравенств из связей ядра». arXiv : 1305.0612 [ math.PR ].
Паулин, Д .; Mackey, L .; Тропп, Дж. А. (2016). «Неравенства Эфрона – Стейна для случайных матриц». Летопись вероятности . 44 (5): 3431–3473. arXiv : 1408.3470 . DOI : 10.1214 / 15-AOP1054 . S2CID 16263460 .
Рудельсон, М .; Вершинин, Р. (2007). «Выборка из больших матриц: подход через геометрический функциональный анализ». J. Assoc. Comput. Мах. (4-е изд.). 54 . arXiv : math / 9608208 . Bibcode : 1996math ...... 8208R . DOI : 10.1145 / 1255443.1255449 . S2CID 6054789 .
Тропп, Дж. (2011). «Неравенство Фридмана для матричных мартингалов». arXiv : 1101.3039 [ math.PR ].
Тропп, Дж. (2010). «Удобные хвостовые границы для сумм случайных матриц». Основы вычислительной математики . 12 (4): 389–434. arXiv : 1004,4389 . DOI : 10.1007 / s10208-011-9099-Z . S2CID 17735965 .