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