Nullspace property

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of

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.

-minimization problem,

, is a standard problem in compressed sensing.

ℓ

-minimization is known to be NP-hard in general.

-relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the

, is solved in place of the

Note that this relaxation is convex and hence amenable to the standard techniques of linear programming - a computationally desirable feature.

ℓ

-relaxation will give the same answer as the

ℓ

The nullspace property is one way to guarantee agreement.

complex matrix

has the nullspace property of order

, if for all index sets

η ∈ ker ⁡

The following theorem gives necessary and sufficient condition on the recoverability of a given

The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.

complex matrix.

is the unique solution to the

satisfies the nullspace property with order

For the forwards direction notice that

are distinct vectors with

For the backwards direction, let

Define the (non-zero) vector

and notice that it lies in the nullspace of

, and then the result follows from an elementary application of the triangle inequality:

, establishing the minimality of