Nullspace property

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of $\ell _{1}$-relaxation. The term "nullspace property" originates from Cohen, Dahmen, and DeVore. The nullspace property is often difficult to check in practice, and the restricted isometry property is a more modern condition in the field of compressed sensing.

The technique of $\ell _{1}$-relaxation

The non-convex $\ell _{0}$-minimization problem,

$\min \limits _{x}\|x\|_{0}$ subject to $Ax=b$,

is a standard problem in compressed sensing. However, $\ell _{0}$-minimization is known to be NP-hard in general. As such, the technique of $\ell _{1}$-relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the $\ell _{0}$-norm. In $\ell _{1}$-relaxation, the $\ell _{1}$ problem,

$\min \limits _{x}\|x\|_{1}$ subject to $Ax=b$,

is solved in place of the $\ell _{0}$ problem. Note that this relaxation is convex and hence amenable to the standard techniques of linear programming - a computationally desirable feature. Naturally we wish to know when $\ell _{1}$-relaxation will give the same answer as the $\ell _{0}$ problem. The nullspace property is one way to guarantee agreement.

Definition

An $m\times n$ complex matrix $A$ has the nullspace property of order $s$, if for all index sets $S$ with $s=|S|\leq n$ we have that: $\|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}$ for all $\eta \in \ker {A}\setminus \left\{0\right\}$.

Recovery Condition

The following theorem gives necessary and sufficient condition on the recoverability of a given $s$-sparse vector in $\mathbb {C} ^{n}$. The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.

${\textbf {Theorem:}}$ Let $A$ be a $m\times n$ complex matrix. Then every $s$-sparse signal $x\in \mathbb {C} ^{n}$ is the unique solution to the $\ell _{1}$-relaxation problem with $b=Ax$ if and only if $A$ satisfies the nullspace property with order $s$.

${\textit {Proof:}}$ For the forwards direction notice that $\eta _{S}$ and $-\eta _{S^{C}}$ are distinct vectors with $A(-\eta _{S^{C}})=A(\eta _{S})$ by the linearity of $A$, and hence by uniqueness we must have $\|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}$ as desired. For the backwards direction, let $x$ be $s$-sparse and $z$ another (not necessary $s$-sparse) vector such that $z\neq x$ and $Az=Ax$. Define the (non-zero) vector $\eta =x-z$ and notice that it lies in the nullspace of $A$. Call $S$ the support of $x$, and then the result follows from an elementary application of the triangle inequality: $\|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}$, establishing the minimality of $x$. $\square$