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 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.
An complex matrix has the nullspace property of order , if for all index sets with we have that: for all .
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 .
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 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.
An complex matrix has the nullspace property of order , if for all index sets with we have that: for all .
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 .