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,

$\underset{x}{min}\Vert x{\Vert }_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,

$\underset{x}{min}\Vert x{\Vert }_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|\le n$ we have that: $\Vert {\eta }_S{\Vert }_1<\Vert {\eta }_{S^C}{\Vert }_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 ${ℂ}^n$. The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.

$\mathbf{\text{𝐓𝐡𝐞𝐨𝐫𝐞𝐦:}}$ Let $A$ be a $m\times n$ complex matrix. Then every $s$-sparse signal $x\in {ℂ}^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$.

$\mathit{\text{𝑃𝑟𝑜𝑜𝑓:}}$ 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 $\Vert {\eta }_S{\Vert }_1<\Vert {\eta }_{S^C}{\Vert }_1$ as desired. For the backwards direction, let $x$ be $s$-sparse and $z$ another (not necessary $s$-sparse) vector such that $z\ne 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: $\Vert x{\Vert }_1\le \Vert x-z_S{\Vert }_1+\Vert z_S{\Vert }_1=\Vert {\eta }_S{\Vert }_1+\Vert z_S{\Vert }_1<\Vert {\eta }_{S^C}{\Vert }_1+\Vert z_S{\Vert }_1=\Vert -z_{S^C}{\Vert }_1+\Vert z_S{\Vert }_1=\Vert z{\Vert }_1$, establishing the minimality of $x$. $◻$