Свойство пустого пространства

При сжатом зондировании свойство нулевого пространства дает необходимые и достаточные условия для восстановления разреженных сигналов с использованием методов $\ell _{1}$-релаксация . Термин «свойство нулевого пространства» принадлежит Коэну, Дамену и ДеВору. Свойство нулевого пространства часто трудно проверить на практике, а свойство ограниченной изометрии является более современным условием в области измерения сжатых данных.

Техника $\ell _{1}$-релаксация

Невыпуклый ​ $\ell _{0}$- задача минимизации,

$\min \limits _{x}\|x\|_{0}$ при условии $Ax=b$,

это стандартная проблема в сжатом измерении. Однако, $\ell _{0}$-минимизация, как известно, NP-трудна . вообще Таким образом, техника $\ell _{1}$-релаксация иногда используется, чтобы обойти трудности реконструкции сигнала с использованием $\ell _{0}$-норм. В $\ell _{1}$-расслабление, $\ell _{1}$ проблема,

$\min \limits _{x}\|x\|_{1}$ при условии $Ax=b$,

решается вместо $\ell _{0}$ проблема. Обратите внимание, что это расслабление является выпуклым и, следовательно, поддается стандартным методам линейного программирования - желательная функция с вычислительной точки зрения. Естественно, мы хотим знать, когда $\ell _{1}$-расслабление даст тот же ответ, что и $\ell _{0}$ проблема. Свойство nullspace — это один из способов гарантировать соглашение.

Определение

Ан $m\times n$ комплексная матрица $A$ имеет свойство порядка nullspace $s$, если для всех наборов индексов $S$ с $s=|S|\leq n$ у нас есть это: $\|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}$ для всех $\eta \in \ker {A}\setminus \left\{0\right\}$.

Условия восстановления

Следующая теорема дает необходимое и достаточное условие восстановимости заданного $s$-разреженный вектор в $\mathbb {C} ^{n}$. Доказательство теоремы является стандартным, и представленное здесь доказательство обобщено у Хольгера Раухута.

${\textbf {Theorem:}}$ Позволять $A$ быть $m\times n$ сложная матрица. Затем каждый $s$-разреженный сигнал $x\in \mathbb {C} ^{n}$ это уникальное решение проблемы $\ell _{1}$-проблемы с расслаблением $b=Ax$ тогда и только тогда, когда $A$ удовлетворяет свойству нулевого пространства с порядком $s$.

${\textit {Proof:}}$ Для прямого направления обратите внимание, что $\eta _{S}$ и $-\eta _{S^{C}}$ являются различными векторами с $A(-\eta _{S^{C}})=A(\eta _{S})$ по линейности $A$, и, следовательно, в силу единственности мы должны иметь $\|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}$ по желанию. Для обратного направления пусть $x$ быть $s$-редкий и $z$ другой (не обязательно $s$-разреженный) вектор такой, что $z\neq x$ и $Az=Ax$. Определите (ненулевой) вектор $\eta =x-z$ и заметьте, что оно лежит в нулевом пространстве $A$. Вызов $S$ поддержка $x$, и тогда результат следует из элементарного применения неравенства треугольника : $\|x\|_{1}\leq \|x-z_{S}\|_{1}+\|z_{S}\|_{1}=\|\eta _{S}\|_{1}+\|z_{S}\|_{1}<\|\eta _{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|-z_{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|z\|_{1}$, устанавливая минимальность $x$. $\square$