Свойство ограниченной изометрии

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

Определение

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

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

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

условие эквивалентно утверждению, что для каждой m × s подматрицы A _A матрицы имеем Это

\|A_{s}^{*}A_{s}-I_{s\times s}\|_{2\to 2}\leq \delta _{s},

где $I_{s\times s}$ это $s\times s$ идентификационная матрица и $\|X\|_{2\to 2}$ является операторной нормой . См. например ^[8] для доказательства.

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

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

Константа RIC определяется как нижняя грань всех возможных $\delta$ для данного $A\in \mathbb {R} ^{n\times m}$ .

\delta _{K}=\inf \left[\delta :(1-\delta )\|y\|_{2}^{2}\leq \|A_{s}y\|_{2}^{2}\leq (1+\delta )\|y\|_{2}^{2}\right],\ \forall |s|\leq K,\forall y\in R^{|s|}

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

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

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

1-\delta _{K}\leq \lambda _{min}(A_{\tau }^{*}A_{\tau })\leq \lambda _{max}(A_{\tau }^{*}A_{\tau })\leq 1+\delta _{K}

.

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

См. также

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

Ссылки

^ Jump up to: ^а ^б Э. Дж. Кандес и Т. Тао, «Декодирование с помощью линейного программирования», IEEE Trans. Инф. Т., 51(12): 4203–4215 (2005).
^ Э. Дж. Кандес, Дж. К. Ромберг и Т. Тао, «Стабильное восстановление сигнала при неполных и неточных измерениях», «Сообщения по чистой и прикладной математике», Vol. ЛИКС, 1207–1223 (2006).
^ А. М. Тиллманн и М. Е. Пфетч, « Вычислительная сложность свойства ограниченной изометрии, свойства нулевого пространства и связанных с ним концепций в сжатом измерении », IEEE Trans. Инф. Т., 60(2): 1248–1259 (2014)
^ Абхирам Натараджан и И Ву, « Вычислительная сложность сертификации свойства ограниченной изометрии» , «Аппроксимация, рандомизация и комбинаторная оптимизация». Алгоритмы и методы (ПРИБЛИЗИТЕЛЬНО/СЛУЧАЙНО, 2014 г.) (2014 г.)
^ Ф. Ян, С. Ван и К. Денг, « Сжимающее измерение реконструкции изображения с использованием многовейвлетного преобразования », IEEE 2010
^ Б. Бах и Дж. Таннер «Улучшенные границы ограниченных констант изометрии для гауссовских матриц»
^ «Эдинбургский университет — Школа математики — Группа сжатых измерений — Константы ограниченной изометрии» . Архивировано из оригинала 27 апреля 2010 г. Проверено 31 марта 2010 г.
^ «Математическое введение в измерение сжатия» (PDF) . Cis.pku.edu.cn. Проверено 15 мая 2018 г.
^ «Сжатое зондирование» . Math.ucla.edu . Проверено 15 мая 2018 г.
^ Ю Ван, Цзиньшань Цзэн, Чжиминь Пэн, Сяньюй Чанг и Цзунбэнь Сюй (2015). «О линейной сходимости адаптивно итеративных алгоритмов порогового определения для сжатого зондирования». Транзакции IEEE по обработке сигналов . 63 (11): 2957–2971. arXiv : 1408.6890 . Бибкод : 2015ITSP...63.2957W . дои : 10.1109/TSP.2015.2412915 . S2CID 10734058 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[auto-1] Jump up to: ^а ^б Э. Дж. Кандес и Т. Тао, «Декодирование с помощью линейного программирования», IEEE Trans. Инф. Т., 51(12): 4203–4215 (2005).

[2] Э. Дж. Кандес, Дж. К. Ромберг и Т. Тао, «Стабильное восстановление сигнала при неполных и неточных измерениях», «Сообщения по чистой и прикладной математике», Vol. ЛИКС, 1207–1223 (2006).

[3] А. М. Тиллманн и М. Е. Пфетч, « Вычислительная сложность свойства ограниченной изометрии, свойства нулевого пространства и связанных с ним концепций в сжатом измерении », IEEE Trans. Инф. Т., 60(2): 1248–1259 (2014)

[4] Абхирам Натараджан и И Ву, « Вычислительная сложность сертификации свойства ограниченной изометрии» , «Аппроксимация, рандомизация и комбинаторная оптимизация». Алгоритмы и методы (ПРИБЛИЗИТЕЛЬНО/СЛУЧАЙНО, 2014 г.) (2014 г.)

[5] Ф. Ян, С. Ван и К. Денг, « Сжимающее измерение реконструкции изображения с использованием многовейвлетного преобразования », IEEE 2010

[6] Б. Бах и Дж. Таннер «Улучшенные границы ограниченных констант изометрии для гауссовских матриц»

[7] «Эдинбургский университет — Школа математики — Группа сжатых измерений — Константы ограниченной изометрии» . Архивировано из оригинала 27 апреля 2010 г. Проверено 31 марта 2010 г.

[8] «Математическое введение в измерение сжатия» (PDF) . Cis.pku.edu.cn. Проверено 15 мая 2018 г.

[9] «Сжатое зондирование» . Math.ucla.edu . Проверено 15 мая 2018 г.

[10] Ю Ван, Цзиньшань Цзэн, Чжиминь Пэн, Сяньюй Чанг и Цзунбэнь Сюй (2015). «О линейной сходимости адаптивно итеративных алгоритмов порогового определения для сжатого зондирования». Транзакции IEEE по обработке сигналов . 63 (11): 2957–2971. arXiv : 1408.6890 . Бибкод : 2015ITSP...63.2957W . дои : 10.1109/TSP.2015.2412915 . S2CID 10734058 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]