Jump to content

Nullspace property

From Wikipedia, the free encyclopedia

In compressed sensing, the nullspace property gives necessary and sufficient conditions on the reconstruction of sparse signals using the techniques of -relaxation. 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.

The technique of -relaxation

[edit]

The non-convex -minimization problem,

subject to ,

is a standard problem in compressed sensing. However, -minimization is known to be NP-hard in general.[2] As such, the technique of -relaxation is sometimes employed to circumvent the difficulties of signal reconstruction using the -norm. In -relaxation, the problem,

subject to ,

is solved in place of the 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 -relaxation will give the same answer as the problem. The nullspace property is one way to guarantee agreement.

Definition

[edit]

An complex matrix has the nullspace property of order , if for all index sets with we have that: for all .

Recovery Condition

[edit]

The following theorem gives necessary and sufficient condition on the recoverability of a given -sparse vector in . The proof of the theorem is a standard one, and the proof supplied here is summarized from Holger Rauhut.[3]

Let be a complex matrix. Then every -sparse signal is the unique solution to the -relaxation problem with if and only if satisfies the nullspace property with order .

For the forwards direction notice that and are distinct vectors with by the linearity of , and hence by uniqueness we must have as desired. For the backwards direction, let be -sparse and another (not necessary -sparse) vector such that and . Define the (non-zero) vector and notice that it lies in the nullspace of . Call the support of , and then the result follows from an elementary application of the triangle inequality: , establishing the minimality of .

References

[edit]
  1. ^ Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald (2009-01-01). "Compressed sensing and best 𝑘-term approximation". Journal of the American Mathematical Society. 22 (1): 211–231. doi:10.1090/S0894-0347-08-00610-3. ISSN 0894-0347.
  2. ^ Natarajan, B. K. (1995-04-01). "Sparse Approximate Solutions to Linear Systems". SIAM J. Comput. 24 (2): 227–234. doi:10.1137/S0097539792240406. ISSN 0097-5397. S2CID 2072045.
  3. ^ Rauhut, Holger (2011). Compressive Sensing and Structured Random Matrices. CiteSeerX 10.1.1.185.3754.