In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of ℓ 1 {\displaystyle \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 ℓ 1 {\displaystyle \ell _{1}} -relaxation The non-convex ℓ 0 {\displaystyle \ell _{0}} -minimization problem,
min x ‖ x ‖ 0 {\displaystyle \min \limits _{x}\|x\|_{0}} subject to A x = b {\displaystyle Ax=b} , is a standard problem in compressed sensing. However, ℓ 0 {\displaystyle \ell _{0}} -minimization is known to be NP-hard in general. As such, the technique of ℓ 1 {\displaystyle \ell _{1}} -relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the ℓ 0 {\displaystyle \ell _{0}} -norm. In ℓ 1 {\displaystyle \ell _{1}} -relaxation, the ℓ 1 {\displaystyle \ell _{1}} problem,
min x ‖ x ‖ 1 {\displaystyle \min \limits _{x}\|x\|_{1}} subject to A x = b {\displaystyle Ax=b} , is solved in place of the ℓ 0 {\displaystyle \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 ℓ 1 {\displaystyle \ell _{1}} -relaxation will give the same answer as the ℓ 0 {\displaystyle \ell _{0}} problem. The nullspace property is one way to guarantee agreement.
Definition An m × n {\displaystyle m\times n} complex matrix A {\displaystyle A} has the nullspace property of order s {\displaystyle s} , if for all index sets S {\displaystyle S} with s = | S | ≤ n {\displaystyle s=|S|\leq n} we have that: ‖ η S ‖ 1 < ‖ η S C ‖ 1 {\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}} for all η ∈ ker A ∖ { 0 } {\displaystyle \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 {\displaystyle s} -sparse vector in C n {\displaystyle \mathbb {C} ^{n}} . The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.
Theorem: {\displaystyle {\textbf {Theorem:}}} Let A {\displaystyle A} be a m × n {\displaystyle m\times n} complex matrix. Then every s {\displaystyle s} -sparse signal x ∈ C n {\displaystyle x\in \mathbb {C} ^{n}} is the unique solution to the ℓ 1 {\displaystyle \ell _{1}} -relaxation problem with b = A x {\displaystyle b=Ax} if and only if A {\displaystyle A} satisfies the nullspace property with order s {\displaystyle s} .
… excerpt ends here. Continue reading the full article.
