Nullspace property

The non-convex $\backslash ell\_0$-minimization problem,

$\backslash min\backslash limits\_\{x\}\; \backslash |x\backslash |\_0$ subject to $Ax\; =\; b$,

is a standard problem in compressed sensing. However, $\backslash ell\_0$-minimization is known to be NP-hard in general.{{Cite journal|last=Natarajan|first=B. K.|date=1995-04-01|title=Sparse Approximate Solutions to Linear Systems|journal=SIAM J. Comput.|volume=24|issue=2|pages=227–234|doi=10.1137/S0097539792240406|s2cid=2072045 |issn=0097-5397}} As such, the technique of $\backslash ell\_1$-relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the $\backslash ell\_0$-norm. In $\backslash ell\_1$-relaxation, the $\backslash ell\_1$ problem,

$\backslash min\backslash limits\_\{x\}\; \backslash |x\backslash |\_1$ subject to $Ax\; =\; b$,

is solved in place of the $\backslash 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 $\backslash ell\_1$-relaxation will give the same answer as the $\backslash ell\_0$ problem. The nullspace property is one way to guarantee agreement.

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

The following theorem gives necessary and sufficient condition on the recoverability of a given $s$-sparse vector in $\backslash mathbb\{C\}^n$. The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.{{Cite book|title=Compressive Sensing and Structured Random Matrices|last=Rauhut|first=Holger|citeseerx = 10.1.1.185.3754|year = 2011}}

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

$\backslash textit\{Proof:\}$ For the forwards direction notice that $\backslash eta\_S$ and $-\backslash eta\_\{S^C\}$ are distinct vectors with $A(-\backslash eta\_\{S^C\})\; =\; A(\backslash eta\_S)$ by the linearity of $A$, and hence by uniqueness we must have as desired. For the backwards direction, let $x$ be $s$-sparse and $z$ another (not necessary $s$-sparse) vector such that $z\; \backslash neq\; x$ and $Az\; =\; Ax$. Define the (non-zero) vector $\backslash 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: , establishing the minimality of $x$. $\backslash square$

{{Reflist}}

Category:Linear algebra