Nullspace property

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of formula_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 formula_1-relaxation.
The non-convex formula_3-minimization problem,
formula_4 subject to formula_5,
is a standard problem in compressed sensing. However, formula_3-minimization is known to be NP-hard in general. As such, the technique of formula_1-relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the formula_3-norm. In formula_1-relaxation, the formula_1 problem,
formula_11 subject to formula_5,
is solved in place of the formula_3 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 formula_1-relaxation will give the same answer as the formula_3 problem. The nullspace property is one way to guarantee agreement.
Definition.
An formula_16 complex matrix formula_17 has the nullspace property of order formula_18, if for all index sets formula_19 with formula_20 we have that: formula_21 for all formula_22.
Recovery Condition.
The following theorem gives necessary and sufficient condition on the recoverability of a given formula_18-sparse vector in formula_24. The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.
formula_25 Let formula_17 be a formula_16 complex matrix. Then every formula_18-sparse signal formula_29 is the unique solution to the formula_1-relaxation problem with formula_31 if and only if formula_17 satisfies the nullspace property with order formula_18.
formula_34 For the forwards direction notice that formula_35 and formula_36 are distinct vectors with formula_37 by the linearity of formula_17, and hence by uniqueness we must have formula_21 as desired. For the backwards direction, let formula_40 be formula_18-sparse and formula_42 another (not necessary formula_18-sparse) vector such that formula_44 and formula_45. Define the (non-zero) vector formula_46 and notice that it lies in the nullspace of formula_17. Call formula_19 the support of formula_40, and then the result follows from an elementary application of the triangle inequality: formula_50, establishing the minimality of formula_40. formula_52