In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of ℓ 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 non-convex ℓ 0 -minimization problem,
min x ∥ x ∥ 0 subject to A x = b ,
is a standard problem in compressed sensing. However, ℓ 0 -minimization is known to be NP-hard in general. As such, the technique of ℓ 1 -relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the ℓ 0 -norm. In ℓ 1 -relaxation, the ℓ 1 problem,
min x ∥ x ∥ 1 subject to A x = b ,
is solved in place of the ℓ 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 -relaxation will give the same answer as the ℓ 0 problem. The nullspace property is one way to guarantee agreement.
An m × n complex matrix A has the nullspace property of order s if for all index sets S with s = | S | ≤ n we have that: ∥ η S ∥ 1 < ∥ η S C ∥ 1 for all η ∈ ker A ∖ { 0 } .
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.
Theorem: Let A be a m × n complex matrix. Then every s -sparse signal x ∈ C n is the unique solution to the ℓ 1 -relaxation problem with b = A x if and only if A satisfies the nullspace property with order s .
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 A z = A x . 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 ≤ ∥ 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 . ◻
