Nullspace property

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 technique of ℓ1-relaxation

The non-convex ℓ0-minimization problem,

minx‖x‖0 subject to Ax=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,

minx‖x‖1 subject to Ax=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.

Definition

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<‖ηSC‖1 for all η∈ker⁡A∖{0}.

Recovery Condition

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

𝐓𝐡𝐞𝐨𝐫𝐞𝐦: Let A be a m×n complex matrix. Then every s-sparse signal x∈ℂn is the unique solution to the ℓ1-relaxation problem with b=Ax if and only if A satisfies the nullspace property with order s.

𝑃𝑟𝑜𝑜𝑓: For the forwards direction notice that ηS and −ηSC are distinct vectors with A(−ηSC)=A(ηS) by the linearity of A, and hence by uniqueness we must have ‖ηS‖1<‖ηSC‖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 Az=Ax. 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−zS‖1+‖zS‖1=‖ηS‖1+‖zS‖1<‖ηSC‖1+‖zS‖1=‖−zSC‖1+‖zS‖1=‖z‖1, establishing the minimality of x. ◻