Source-linked AI summary
A Short Note on Compressed Sensing with Partially Known Signal Support
Laurent Jacques
TL;DR
When part of a sparse signal’s support is known, compressed sensing can use that information in reconstruction. This note introduces iBPDN, an ℓ1-based method focused on the unknown support, and extends stability results to compressible signals and noisy measurements. Its recovery requirements are connected to those of cancel-then-recover approaches.
Problem
Method
iBPDN extends Modified-CS by minimizing the candidate’s ℓ1 norm outside the known support under an ℓ2 fidelity constraint.
Source: §4 · p. 3Results
Takeaways & Limitations
iBPDN’s stability requirements are related to cancel-then-recover, while that strategy may use a weaker δ-stable embedding condition than RIP of order s + 2k.
Source: §7 · p. 7, §9 · p. 8The known support may be corrupted, and the size of the true support outside it is unconstrained; compressibility there is characterized by coefficient values.
Source: §2 · p. 3
Abstract
from arXiv · showhide
This short note studies a variation of the Compressed Sensing paradigm introduced recently by Vaswani et al., i.e. the recovery of sparse signals from a certain number of linear measurements when the signal support is partially known. The reconstruction method is based on a convex minimization program coined "innovative Basis Pursuit DeNoise" (or iBPDN). Under the common $\ell_2$-fidelity constraint made on the available measurements, this optimization promotes the ($\ell_1$) sparsity of the candidate signal over the complement of this known part. In particular, this paper extends the results of Vaswani et al. to the cases of compressible signals and noisy measurements. Our proof relies on a small adaption of the results of Candes in 2008 for characterizing the stability of the Basis Pursuit DeNoise (BPDN) program. We emphasize also an interesting link between our method and the recent work of Davenport et al. on the $\delta$-stable embeddings and the "cancel-then-recover" strategy applied to our problem. For both approaches, reconstructions are indeed stabilized when the sensing matrix respects the Restricted Isometry Property for the same sparsity order. We conclude by sketching an easy numerical method relying on monotone operator splitting and proximal methods that iteratively solves iBPDN.
1 Introduction
The paper studies compressed sensing when part of a signal’s support is known and introduces iBPDN, extending stability results to compressible signals and noisy measurements. Partial support can aid recovery in slowly evolving sequences and some one-dimensional signals or images.
1 Introduction
- Compressed sensing recovers sparse or compressible signals from relatively few linear measurements when the sensing matrix satisfies the Restricted Isometry Property.The note identifies Gaussian, Bernoulli, and partial Fourier matrices as ensembles that satisfy RIP with overwhelming probability above a few multiples of the assumed sparsity.Source: §1 · pp. 1–2
- For slowly evolving sparse sequences, a previously recovered support can improve next-step reconstruction by reducing measurements or improving quality at a fixed measurement count [17].Known support can also aid recovery of certain one-dimensional signals and positive-intensity photographic images through their wavelet coefficients.Source: §1 · p. 2
- iBPDN minimizes the candidate signal’s ℓ1 norm outside the known support and extends stability results to compressible signals and noisy measurements, [17].The analysis adapts the proof of and relates the method to cancel-then-recover.Source: §1 · p. 2
2 Framework and Notations
The framework assumes a sparse or compressible signal and partial knowledge of its support, which may be erroneous. It uses established notation for the signal’s components, support, and sparsity.
2 Framework and Notations
- Signals are sparse or compressible in a basis Ψ; the presentation uses the canonical basis but also allows any orthonormal basis, including DCT or wavelets.For compressible signals, coefficients decay quickly rather than having only a few nonzeros.Source: §2 · p. 2
- The notation defines support, set-restricted vectors, and u_l as the vector retaining u’s l largest-amplitude components; ℓ0 counts nonzero entries but is not a true norm.For a non-canonical basis, u_l denotes the best l-term approximation in the ℓ2 sense.Source: §2 · p. 2
- The known support T may contain errors, and the size of the true support outside T is unconstrained; coefficient values there determine compressibility.The framework denotes the size of T by s = #T.Source: §2 · p. 3
3 Sensing Model
The sensing model acquires the signal through a matrix with additional white measurement noise bounded in ℓ2 norm. Recovery stability is linked to the matrix’s Restricted Isometry Property.
3 Sensing Model
- The signal is acquired through a sensing matrix Φ with additional white noise, whose ℓ2 norm is bounded by ε.The measurement vector is denoted y.Source: §3 · p. 3
- Recovery stability is linked to whether Φ satisfies the Restricted Isometry Property [4, 2, 3].The definition is framed for order q and q-sparse vectors.Source: §3 · p. 3
4 Reconstructing on Innovation
The reconstruction approach replaces an intractable sparsity search with an ℓ1 optimization that focuses on the unknown part of the support. The resulting iBPDN program extends Modified-CS to corrupted measurements.
4 Reconstructing on Innovation
- The proposed reconstruction minimizes the candidate’s ℓ1 norm outside T subject to the ℓ2 fidelity constraint ∥Φu−y∥2 ≤ ε.This is the convex relaxation of minimizing the ℓ0 count outside T.Source: §4 · p. 3
- Directly minimizing the ℓ0 norm outside T would be combinatorial and NP-hard, motivating an ℓ1 relaxation with possible RIP-conditioning requirements,.Source: §4 · p. 3
- iBPDN extends Modified-CS to handle corrupted measurements and targets sparsity in the unknown, or innovation, part of the signal support [17].The innovation set is (supp x) \ T, contained in the complement of the known support.Source: §4 · p. 3
5 iBPDN and ℓ2 −ℓ1 Instance Optimality
The theorem gives conditions for iBPDN to achieve ℓ2−ℓ1 instance optimality when part of the signal support is known. Its error bound accounts for measurement noise and the residual's compressibility.
5 iBPDN and ℓ2 −ℓ1 Instance Optimality
- If δ_2k^2 + 2δ_{s+2k} < 1, iBPDN has ℓ2−ℓ1 instance optimality under the stated RIP assumptions.The RIP orders are 2k and s + 2k; the condition makes the constants' denominator positive.Source: §5 · pp. 4–5
- The proof defines the residual outside known support and selects its k largest coefficients to organize the error bound.It then forms sets from the largest coefficients of the error outside the known support.Source: §5 · p. 4
- The proof adapts to partially known support and uses RIP control of disjoint-support inner products alongside measurement feasibility.Feasibility gives ∥Φh∥_2 ≤ 2ϵ.Source: §5 · pp. 4–5
- The reconstruction error is bounded in terms of measurement noise and the residual's k-term compressibility error.The bound uses constants C_{s,k} and D_{s,k}, which depend only on Φ.Source: §5 · pp. 4–5
6 Observations
The observations relate the theorem to standard BPDN and clarify its implications for exact sparsity and compressibility. The error measure applies to the signal residual outside the known support.
6 Observations
- With no known support, the theorem recovers the earlier BPDN sufficient condition.This is the case T = ∅ and s = 0.Source: §6 · p. 6
- For an exactly sparse signal with no measurement noise, the theorem guarantees perfect reconstruction, as in.Here the residual's k-term compressibility error is zero.Source: §6 · p. 6
- Compressibility is measured by the k-term error of the residual outside known support, generalizing the earlier BPDN error measure.The residual is r = x − x_T.Source: §6 · p. 6
7 Connection to δ-stable Embeddings and the Cancel-then-Recover strategy
The section explains Davenport et al.’s cancel-then-recover strategy and compares its guarantees with iBPDN. Both approaches address compressible signals, while iBPDN also provides whole-signal estimation and stability against noisy measurements.
7 Connection to δ-stable Embeddings and the Cancel-then-Recover strategy
- Cancel-then-recover removes the measurements’ contribution from the known support, then reconstructs the signal outside that support from the projected measurements.It forms eΦ = PΩ⊥Φ and ey = eΦx; Basis Pursuit or a greedy method such as CoSaMP can recover x_Tc.Source: §7 · p. 6
- A δ-stable embedding of (Σ2k, ΣT) makes the projected matrix eΦ RIP of order 2k; an order-(s+2k) RIP supplies such an embedding.The resulting RIP radius is δs+2k/(1−δs+2k).Source: §7 · p. 7
- The related Basis Pursuit program bounds recovery error outside T by a constant times the best k-term approximation error of the residual signal.The displayed bound is ∥x_Tc − ex_Tc∥2 ≤ eDδ′ e0(r, k).Source: §7 · p. 7
- The comparison states that both approaches are stable for compressible signals and consider RIP of order 2s + k.This comparison appears alongside the observation that the iBPDN guarantee concerns the whole signal, not only its behavior over T c.Source: §7 · p. 7
- Unlike cancel-then-recover, iBPDN provides stability against noisy measurements and guarantees estimation of the whole signal.The cancel-then-recover error guarantee described here concerns the complement T c.Source: §7 · p. 7
- The cancel-then-recover guarantee needs only a δ-stable embedding, weaker than requiring an order-(s+2k) RIP and potentially with a smaller radius.The passage leaves open whether the matrix in [9] must satisfy that RIP condition.Source: §7 · p. 7
8 Numerical Method
The numerical method solves iBPDN using monotone operator splitting and proximal methods. Its Douglas–Rachford iterates converge to a point whose projection onto the measurement tube solves iBPDN.
9 Numerical Method
- The method applies monotone operator splitting and proximal methods to solve iBPDN.The proximity operator is defined as the unique minimizer of a quadratic distance term plus a convex function.Source: §8 · pp. 7–8
- Cancel-then-recover noise robustness could be obtained by bounding the power of the noise projected onto Ω⊥.This concerns additional noise n when y = Φx + n.Source: §8 · p. 7
- For iBPDN, the objective term is the ℓ1 norm on the complement of the known support, constrained by the measurement-fidelity tube.The formulation uses f(u) = ∥u_Tc∥_1 and C(ε) = {v : ∥y − Φv∥_2 ≤ ε}.Source: §8 · p. 8
- The Douglas–Rachford sequence converges to u*, and projecting u* onto C(ε) yields an iBPDN solution.The iteration uses α_t ∈ (0, 2), S_γ = prox_γf, and P_C(ε) = prox_g.Source: §8 · p. 8
- The iBPDN soft-thresholding operator acts on coordinates outside the known support and leaves coordinates inside it unchanged.The threshold is γ; projection onto C(ε) is also needed, with efficient computation methods cited in.Source: §8 · p. 8
9 Conclusion
The note concludes that iBPDN has stability guarantees for compressible signals and noisy measurements, related to cancel-then-recover requirements. It identifies evaluation on signal sequences as future work.
9 Conclusion
- iBPDN has stability guarantees similar to BPDN for compressible signals and noisy measurements.The method generalizes the common Basis Pursuit DeNoise program to recovery with partially known support.Source: §9 · p. 8
- The obtained requirements are related to those in Davenport et al. for cancel-then-recover in this setting.Source: §9 · p. 8
- Future work will assess reconstruction quality against measurement count for signal sequences with quantifiable innovation over time.The planned setting includes sparse or compressible signals and quantifies the ratio of unknown to known support parts.Source: §9 · p. 8