Nullspace property explained

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.^[1] 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

\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.^[2] 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 x 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: \| η _{S\|} _{1} < \| η _{S ^{C}} \| _{1} for all η \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 C ^{n} . The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.^[3] bf{Theorem:} Let A be a m x n complex matrix. Then every s -sparse signal x \in 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 .it{Proof:} For the forwards direction notice that η _{S} and -η _{S ^{C}} are distinct vectors with A( -η _{S ^{C}} ) = A( η _{S)} by the linearity of A , and hence by uniqueness we must have \| η _{S\|} _{1} < \| η _{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 ≠ x and Az = Ax . Define the (non-zero) vector η = 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} = \| η _{S\|} _{1+\|z} _{S\|} _{1} < \| η _{S ^{C}} \| _{1+\|z} _{S\|} _{1} = \| - z _{S ^{C}} \| _{1+\|z} _{S\|} _{1} = \|z\| _{1} , establishing the minimality of x . \square

Notes and References

1. Cohen. Albert. Dahmen. Wolfgang. DeVore. Ronald. 2009-01-01. Compressed sensing and best -term approximation. Journal of the American Mathematical Society. 22. 1. 211–231. 10.1090/S0894-0347-08-00610-3. 0894-0347. free.
2. Natarajan. B. K.. 1995-04-01. Sparse Approximate Solutions to Linear Systems. SIAM J. Comput.. 24. 2. 227–234. 10.1137/S0097539792240406. 2072045 . 0097-5397.
3. Book: Rauhut, Holger. Compressive Sensing and Structured Random Matrices. 10.1.1.185.3754. 2011.