Ограниченное свойство изометрии - Restricted isometry property

В линейная алгебра, то свойство ограниченной изометрии (РВАТЬ) характеризует матрицы которые почти ортонормированы, по крайней мере, при работе с разреженными векторами. Концепция была представлена Эммануэль Кандес и Теренс Тао^[1] и используется для доказательства многих теорем в области сжатое зондирование.^[2] Нет известных больших матриц с ограниченными ограниченными константами изометрии (вычисление этих постоянных сильно NP-жесткий,^[3] и трудно приблизиться^[4]), но было показано, что многие случайные матрицы остаются ограниченными. В частности, было показано, что с экспоненциально высокой вероятностью случайные гауссовы матрицы, матрицы Бернулли и частичные матрицы Фурье удовлетворяют RIP с числом измерений, почти линейным по уровню разреженности.^[5] Текущие наименьшие верхние границы для любых больших прямоугольных матриц относятся к таковым для гауссовых матриц.^[6] Веб-формы для оценки границ ансамбля Гаусса доступны на странице Edinburgh Compressed Sensing RIC.^[7]

Определение

Позволять А быть м × п матрица и пусть 1 ≤ s ≤ п быть целым числом. Предположим, что существует постоянная ${displaystyle delta _{s}in (0,1)}$ так что для каждого м × s подматрица А_s из А и для каждого s-мерный вектору,

${displaystyle (1-delta _{s})|y|_{2}^{2}leq |A_{s}y|_{2}^{2}leq (1+delta _{s})|y|_{2}^{2}.,}$

Тогда матрица А считается, что удовлетворяет s-ограниченная изометрия с ограниченной константой изометрии ${displaystyle delta _{s}}$.

Это эквивалентно

${displaystyle |A_{s}^{*}A_{s}-I|_{2 o 2}leq delta _{s}}$

куда ${displaystyle I}$ - единичная матрица и ${displaystyle |X|_{2 o 2}}$ это норма оператора. См. Например ^[8] для доказательства.

Наконец, это эквивалентно утверждению, что все собственные значения из ${displaystyle A_{s}^{*}A_{s}}$ находятся в интервале ${displaystyle [1-delta _{s},1+delta _{s}]}$.

Ограниченная изометрическая константа (RIC)

Константа RIC определяется как инфимум из всех возможных ${displaystyle delta }$ для данного ${displaystyle Ain mathbb {R} ^{n imes m}}$.

${displaystyle delta _{K}=inf left[delta :(1-delta )|y|_{2}^{2}leq |A_{s}y|_{2}^{2}leq (1+delta )|y|_{2}^{2}ight], forall |s|leq K,forall yin R^{|s|}}$

Обозначается как ${displaystyle delta _{K}}$.

Собственные значения

Для любой матрицы, которая удовлетворяет свойству RIP с RIC, равным ${displaystyle delta _{K}}$, выполняется следующее условие:^[1]

${displaystyle 1-delta _{K}leq lambda _{min}(A_{ au }^{*}A_{ au })leq lambda _{max}(A_{ au }^{*}A_{ au })leq 1+delta _{K}}$.

Самая точная верхняя граница RIC может быть вычислена для гауссовых матриц. Это может быть достигнуто путем вычисления точной вероятности того, что все собственные значения матриц Уишарта лежат в пределах интервала.

Смотрите также

• Сжатое зондирование
• Взаимная когерентность (линейная алгебра)
• На веб-сайте Теренса Тао по сжатому зондированию перечислено несколько связанных условий, таких как «Принцип точной реконструкции» (ERP) и «Принцип единой неопределенности» (UUP).^[9]
• Nullspace свойство, еще одно достаточное условие для разреженного восстановления
• Обобщенное свойство ограниченной изометрии,^[10] обобщенное достаточное условие разреженного восстановления, где взаимная согласованность и свойство ограниченной изометрии обе его особые формы.

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

1. Э. Дж. Кандес и Т. Тао, «Декодирование с помощью линейного программирования», IEEE Trans. Инф. Th., 51 (12): 4203–4215 (2005).
2. Э. Дж. Кандес, Дж. К. Ромберг и Т. Тао, "Устойчивое восстановление сигнала при неполных и неточных измерениях", Сообщения по чистой и прикладной математике, Vol. LIX, 1207–1223 (2006).
3. А. М. Тилльманн и М. Э. Пфетч "Вычислительная сложность свойства ограниченной изометрии, свойства нулевого пространства и связанных понятий в сжатых измерениях, "IEEE Trans. Inf. Th., 60 (2): 1248–1259 (2014)"
4. Абхирам Натараджан и Йи Ву "Вычислительная сложность подтверждения свойства ограниченной изометрии, «Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы (APPROX / RANDOM 2014) (2014)
5. Ф. Ян, С. Ван и Ч. Дэн "Компрессионное распознавание реконструкции изображения с использованием многовейвлетного преобразования", IEEE 2010
6. Б. Ба и Дж. Таннер "Улучшенные оценки констант ограниченной изометрии для гауссовских матриц"
7. «Архивная копия». Архивировано из оригинал на 2010-04-27. Получено 2010-03-31.
8. «Математическое введение в зондирование сжатия» (PDF). Cis.pku.edu.cn. Получено 15 мая 2018.
9. "Сжатое зондирование". Math.ucla.edu. Получено 15 мая 2018.
10. Ю Ван, Цзиньшань Цзэн, Чжимин Пэн, Сянью Чанг и Цзунбэнь Сюй (2015). «О линейной сходимости адаптивно итерационных алгоритмов пороговой обработки для сжатого зондирования». Транзакции IEEE при обработке сигналов. 63 (11): 2957–2971. arXiv:1408.6890. Дои:10.1109 / TSP.2015.2412915.