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 ℓ 1 {\displaystyle \ell _{1}}
-relaxation
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
An
complex matrix
has the nullspace property of order
, if for all index sets
with
we have that:
for all
.
Recovery Condition
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
. ![{\displaystyle \square }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
References
- ^ 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.
- ^ 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.
- ^ Rauhut, Holger (2011). Compressive Sensing and Structured Random Matrices. CiteSeerX 10.1.1.185.3754.