PaperlayerView exact revision on arXiv

Source-linked AI summary

Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries

Mark A. Davenport, Deanna Needell, Michael B. Wakin

arXiv:1208.0353v3cs.ITmath.IT

TL;DR

Signals sparse in redundant dictionaries can be difficult to recover with coefficient-focused CS, where standard guarantees may not apply or reflect signal error. Signal Space CoSaMP instead estimates signals under D-RIP and near-optimal projection assumptions. Its analysis extends to arbitrary signals, with small recovery error when mismatch is small or coefficients are compressible; computing the required projections provably remains open.

  • Problem

    For signals sparse in redundant dictionaries, coefficient-focused recovery can lack applicable guarantees and coefficient accuracy need not reflect signal-space error.

    Source: §1.1 · pp. 2–3

  • Method

    Signal Space CoSaMP modifies CoSaMP to estimate the signal directly, using D-RIP and near-optimal projections onto the sparse-signal model.

    Source: §1.1 · p. 3, §1.3 · p. 5

  • Results

    The analysis extends to arbitrary signals, with recovery error small when mismatch is small or the coefficient vector is compressible.

    Source: §2.2 · pp. 7–8

  • Takeaways & Limitations

    Signal-space recovery guarantees can be developed for arbitrary dictionaries without requiring AD to satisfy the RIP, subject to the stated D-RIP and projection conditions.

    Source: §1.1 · p. 3

    A practical algorithm provably computing the required near-optimal projections remains an open problem.

    Source: §1.3 · p. 6

Abstract

from arXiv · show

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper we describe a variant of the iterative recovery algorithm CoSaMP for this more challenging setting. We utilize the D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are "signal-focused"; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. Developing a practical algorithm that can provably compute the required near-optimal projections remains a significant open problem, but we include simulation results using various heuristics that empirically exhibit superior performance to traditional recovery algorithms.

1 Introduction

The introduction reframes recovery for signals sparse in redundant dictionaries: coefficient-focused CS can misstate both recovery feasibility and signal-space error. It proposes signal-focused CoSaMP and states the D-RIP and projection requirements for its guarantees.

1.1 Overview

  • Redundancy can make coefficient representations nonunique, while dictionary coherence and poor conditioning weaken standard RIP-based recovery and obscure signal-space error.Thus an accurate coefficient estimate need not guarantee an accurate signal estimate.Source: §1.1 · pp. 2–3
  • Signal Space CoSaMP adapts CoSaMP to estimate the signal directly, with guarantees under D-RIP rather than requiring AD to satisfy the RIP.For unitary D, it reduces to standard CoSaMP.Source: §1.1 · p. 3

1.2 Related Work

  • Unlike PLA, which extends IHT in signal space, this work extends CoSaMP and allows near-optimal projections; analysis-sparsity methods target a different signal family.The paper distinguishes its signal-space synthesis-sparsity approach from model-based CS, which operates in coefficient space.Source: §1.2 · p. 4

1.3 Requirements

  • D-RIP concerns signals with sparse representations in D, and random Gaussian or subgaussian sensing matrices satisfy it with high probability when m = O(k log(d/k)).The algorithm also requires approximate projections onto the model family, judged by their effect in signal space; a provably practical projection method remains open.Source: §1.3 · pp. 5–6

2 Algorithm and Recovery Guarantees

Signal Space CoSaMP recovers the signal in signal space under a D-RIP assumption, with guarantees for exactly sparse and arbitrary signals. Its recovery bounds depend on near-optimal sparse projections, which remain computationally unresolved.

2.1 A Bound for the Recovery of Sparse Signals

  • For exactly D-sparse signals, D-RIP of order 4k gives an iterative signal-error bound whose constants depend on δ4k and the projection approximation parameters.The theorem assumes a k-sparse α with x=Dα.Source: §2.1 · p. 6
  • With δ4k=0.029 and near-optimal projections using ϵ1=1/10 and ϵ2=1, O(log(∥x∥2/η)) iterations suffice to reduce recovery error to the measurement-noise level.The transient error term can be made arbitrarily small by taking enough iterations.Source: §2.1 · p. 7
  • No efficient method is known for computing the required near-optimal projections, so the algorithm’s actual complexity depends on the chosen approximation method.Using OMP or CoSaMP gives the stated running-time bounds, but the near-optimality of these practical choices is not theoretically backed.Source: §2.1 · p. 7

2.2 A Discussion Concerning the Recovery of Arbitrary Signals

  • The method treats A(x−Dαk) as added measurement noise and chooses αk to minimize the resulting recovery bound for arbitrary signals.The analysis allows signals that do not have an exact sparse representation in D.Source: §2.2 · p. 7
  • For nonunitary D, the bounds are difficult to improve because the measurement residual is hard to control without additional assumptions.The paper notes that further modifications can bound this residual under some additional assumptions.Source: §2.2 · pp. 7–8
  • When the mixed ℓ2/ℓ1 mismatch to the k-sparse dictionary model is small, the recovery error is small; this mismatch plays a role analogous to classical tail bounds.A large mismatch indicates that the signal is far from compressible in the model.Source: §2.2 · p. 8
  • Under the stronger assumption that AD satisfies RIP, the analysis can measure model mismatch in coefficient space; compressible coefficients yield reasonably small recovery error.This is a stronger condition than the D-RIP assumption used for the signal-space guarantee.Source: §2.2 · p. 8

3 Simulations

Across the simulations, Signal Space CoSaMP variants often outperform their traditional counterparts, but which solver works best depends on the coefficient pattern. The experiments range from a renormalized orthogonal dictionary to well-separated, clustered, and hybrid patterns in an overcomplete DFT dictionary.

3 Simulations

  • The simulations use heuristic near-optimal support estimators because computing the required signal-space projections is the main practical difficulty and can be challenging for practical dictionaries.They use noiseless Gaussian measurements with signal length 256 and sparsity 8, and count recovery as perfect above 100 dB SNR.Source: §3 · pp. 8–9

3.2 Overcomplete DFT Dictionary

  • The simulations compare well-separated coefficients with at least eight zeros between nonzero entries against coefficients clustered in one randomly positioned block.Neighboring columns in the 4× overcomplete DFT dictionary are highly coherent, whereas distant columns are not.Source: §3.2 · p. 9, §3.2.2 · p. 12

3.1 Renormalized Orthogonal Dictionary

  • With orthogonal but unnormalized columns, Signal Space CoSaMP with optimal projections outperforms unmodified CoSaMP across measurement counts.In the demonstration with the identity dictionary’s first half of diagonal entries rescaled to 100, Signal Space CoSaMP recovered nearly all trials perfectly with roughly 50 or more measurements, while traditional CoSaMP almost never recovered the correct signal.Source: §3.1 · p. 9, Figure 1 · p. 10

3.2.1 Well-separated coefficients

  • For well-separated coefficients, ℓ1-minimization inside Signal Space CoSaMP performs best, while traditional ℓ1-minimization also outperforms traditional OMP.The authors relate this pattern to exact optimal-support recovery by ℓ1-minimization when the projected signal’s optimal support is sufficiently separated, though that condition is not guaranteed at every iteration.Source: §3.2.1 · pp. 10–11

3.2 Overcomplete DFT Dictionary

  • In the 4× overcomplete DFT dictionary, OMP and ℓ1-minimization perform well for well-separated coefficients, while CoSaMP performs well for clustered coefficients; Signal Space variants generally outperform their traditional counterparts.The hybrid pattern was difficult for all three Signal Space CoSaMP methods and all three standard CS methods.Source: Figure 2 · p. 11, §3.2.3 · p. 13

3.2.1 Well-separated coefficients

  • All tested methods include least-squares debiasing on an estimated support, which can be numerically challenging for highly coherent dictionaries; Tikhonov regularization is used to improve conditioning.The norm bound was set to ten times the true coefficient norm; CoSaMP and its Signal Space variant performed somewhat better when given the true norm as an oracle in the well-separated case.Source: §3.2.1 · p. 11

3.2.2 Clustered coefficients

  • For clustered coefficients, traditional CoSaMP outperforms OMP, and Signal Space CoSaMP using CoSaMP performs somewhat better than traditional CoSaMP.Neither ℓ1-based method performs well at the 100 dB perfect-recovery threshold, although both frequently reach 50 dB or more; convergence to the correct support can be slow with neighboring active atoms.Source: §3.2.2 · p. 12

3.2.3 Additional investigations

  • The best support-estimation heuristic depends on the sparsity pattern, and all three Signal Space CoSaMP methods struggle on a hybrid pattern mixing separated and clustered coefficients.For clustered coefficients, the optimal approximation’s support need not itself be clustered, which can make CoSaMP struggle to identify it accurately.Source: §3.2.3 · pp. 12–13

A Proof of Theorem 2.1

The proof of Theorem 2.1 is organized around four lemmas concerning the recovery error after each iteration. The listed Identify and Merge lemmas bound projection residuals in terms of one another.

A Proof of Theorem 2.1

  • The Identify lemma bounds the residual outside the identified support using the recovery error, the D-RIP constant, the support-estimation parameter, and measurement noise.Its stated bound is ((2 + ϵ1)δ4k + ϵ1)∥v∥2 + (2 + ϵ1)√(1 + δ4k)∥e∥2.Source: A Proof of Theorem 2.1 · p. 13
  • The Merge lemma bounds the signal residual outside the merged support by the Identify-stage residual outside the identified support.The proof passage identifies v as the recovery error in signal space after ℓ iterations.Source: A Proof of Theorem 2.1 · p. 13

A.1 Proof of Lemma A.1

The proof of Lemma A.1 bounds the Identify-stage residual by decomposing the projection error around the selected and optimal supports. D-RIP and support-estimation accuracy then control the resulting terms.

A.1 Proof of Lemma A.1

  • A D-RIP consequence bounds the projected operator error, while nested-support projection identities and orthogonal-projection norm bounds control intermediate terms.The proof invokes the D-RIP consequence and the identity PA = PAPB when A is a subset of B.Source: §A.1 · pp. 13–14
  • The proof writes the measured proxy as A*Av + A*e and compares the selected 2k-support with the optimal 2k-support and the support estimated from the current error.The notation sets Ω = SD(ẽv, 2k), Ω* = Λopt(ẽv, 2k), and R = SD(v, 2k).Source: §A.1 · p. 14
  • The component of v outside Ω is bounded by (2 + ϵ1) times the projected reconstruction discrepancy and projected noise, plus ϵ1 times ∥v∥2.∥PΩ⊥v∥2 ≤ (2 + ϵ1)∥PR∪Ω* A*Av − v∥2 + (2 + ϵ1)∥PR∪Ω* A*e∥2 + ϵ1∥v∥2.Source: §A.1 · p. 15

A.2 Proof of Lemma A.2

The proof begins by using the merged support to represent the current iterate, so its projection outside that support is zero.

A.2 Proof of Lemma A.2

  • Because xℓ lies in the span of the dictionary columns indexed by T, its orthogonal projection outside T vanishes.This establishes the starting identity for the Lemma A.2 proof.Source: §A.2 · p. 16

A.3 Proof of Lemma A.3

The proof uses the D-RIP of order 4k on a vector with a 4k-sparse representation in D. It then considers vectors in R(D^T), including PT x, and applies triangle inequalities.

A.3 Proof of Lemma A.3

  • x − ex has a 4k-sparse representation in D, so the proof applies the D-RIP of order 4k.Source: §A.3 · p. 16
  • The proof considers the D-RIP bound for any z in R(D^T), including z = PT x.Source: §A.3 · p. 16
  • Triangle inequalities are used in the derivation before the D-RIP is applied to obtain the next bound.Source: §A.3 · p. 16

A.4 Proof of Lemma A.4

The proof compares the selected support Γ with the optimal size-k support Γ∗ and uses the nearest-neighbor property of PΓ∗ to derive an approximation bound.

A.4 Proof of Lemma A.4

  • Γ = SD(ex, k) gives xℓ+1 = PΓex, while Γ∗ = Λopt(ex, k) denotes the optimal size-k support for approximating ex.Source: §A.4 · p. 16
  • The proof uses the triangle inequality and equation (4) to combine its intermediate bounds.Source: §A.4 · p. 17
  • The derivation bounds the error by (2 + ϵ2) ∥x − ex∥2.Source: §A.4 · p. 17
  • PΓ∗ex is the nearest neighbor to ex among vectors having a k-sparse representation in D.Source: §A.4 · p. 17
Loading 1208.0353v3…