Source-linked AI summary
Compressed Sensing with Coherent and Redundant Dictionaries
Emmanuel J. Candes, Yonina C. Eldar, Deanna Needell, Paige Randall
TL;DR
The paper addresses compressed sensing for signals sparse or compressible only in highly redundant and coherent dictionaries, where standard theory is limited. It develops a dictionary-adapted measurement condition and analyzes ℓ1-analysis recovery. The results show accurate signal recovery without imposing incoherence on the dictionary, while requiring rapidly decaying analysis coefficients.
Problem
Compressed sensing theory largely lacks guarantees for signals represented by redundant, coherent dictionaries, despite their widespread use.
Method
The paper introduces a dictionary-adapted restricted isometry condition and studies ℓ1-analysis recovery for measurements of signals represented through redundant dictionaries.
Results
Accurate recovery is guaranteed for rapidly decaying D∗f, including Gaussian sensing with m on the order of s log(d/s), even when dictionary coherence is maximal.
Takeaways & Limitations
Compressed sensing can recover the signal itself from few random measurements in coherent redundant dictionaries, even when the coefficient vector is not uniquely recoverable.
Takeaways & Limitations
The guarantees may fail when D∗f is not close to sparse, such as for some concatenations of orthonormal bases.
Abstract
from arXiv · showhide
This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an L1-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence restriction on the dictionary and our results may be the first of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of L1-analysis for such problems.
1 Introduction
Compressed sensing traditionally relies on sparsity in orthonormal or incoherent dictionaries, leaving coherent redundant representations insufficiently addressed. The paper introduces D-RIP-based guarantees showing that ℓ1-analysis can accurately recover signals whose dictionary coefficients decay rapidly, even with highly coherent dictionaries.
- Motivation: Compressed sensing acquires compressible signals from far fewer nonadaptive measurements than traditionally assumed.The measurements are linear, and the sensing matrix may have substantially fewer rows than columns.
- Motivation: Overcomplete dictionaries are widely used when no suitable sparsifying orthonormal basis exists or when redundant representations provide practical flexibility.Examples include curvelets, Gabor representations, tight frames, and inverse problems such as deconvolution and tomography.
- Motivation: Traditional compressed sensing theory leaves a gap for redundant coherent dictionaries because it generally assumes orthonormality or extreme dictionary incoherence.For nonunitary dictionaries, the effective matrix AD can have correlated entries and may fail standard compressed sensing assumptions.
- Motivation: Coherence can prevent unique coefficient recovery while still permitting recovery of the signal f = Dx itself.Identical dictionary columns make sparse coefficients nonunique, but the represented signal may remain recoverable.
- Main results: The paper's main result establishes accurate ℓ1-analysis recovery when D∗f has rapidly decreasing coefficients, using a measurement condition that supports redundant dictionaries.For a tight frame and Gaussian sensing matrix, m is on the order of s log(d/s), with error controlled by noise and the coefficient tail.
- Implications: The guarantees cover practical coherent representations, including curvelet images, multitone signals, pulse trains, and sparse expansions supported by suitable frame structure.For curvelet images, the coefficient decay yields an ℓ2 error of about s^-1 from about s log n random samples; multitone and pulse-train recovery require measurements roughly proportional to the number of components, up to a log factor.
- Limitations: ℓ1-analysis is not guaranteed to work well when D∗f is not close to sparse, as can occur with concatenations of orthonormal bases.In that setting, the coefficient sequence may be spread out, so the theorem gives no good error bound and ℓ1-analysis may be the wrong method.
2 Proof of Main Result
The proof establishes recovery guarantees for ℓ1-analysis by combining a cone constraint, tail bounds on D∗h, feasibility-based measurement control, and the D-RIP with tight-frame structure. Parameter selection then yields explicit restricted-isometry conditions and error constants.
- The proof analyzes h = f − ˆf through a sequence of lemmas, exploiting sparsity in D∗h rather than applying RIP directly to a sparse coefficient vector.The argument uses the D-RIP and the fact that D is a tight frame to control the actual signal error.
- The minimization property of ˆf gives a cone constraint on D∗h, after which the complement of the largest coefficients is partitioned into decreasing-magnitude blocks.T0 contains the largest s coefficients of D∗f; the remaining coordinates are divided into sets T1, T2, … of size M.
- 2ε bounds ∥Ah∥2 because both f and ˆf are feasible for the measurement constraint.The bound follows from the triangle inequality applied to Af − y and A ˆf − y, each of which is at most ε.
- The D-RIP and tight-frame identity DD∗ = I translate the measurement and coefficient bounds into a bound on ∥h∥2.The proof explicitly uses the D-RIP consequence and the isometry of D∗ to control the actual reconstruction error.
- δ7s ≤ 0.6 suffices for the theorem, while choosing c1 = 1/2, c2 = 1/10, and M = 6s gives a stronger δ7s ≤ 1/2 condition.For δ7s ≤ 1/4, the theorem constants are C1 = 10.3 and C2 = 7.33; δ7s ≤ 0.6 follows whenever δ2s ≤ 0.08.
3 Numerical Results
Numerical experiments show that ℓ1-analysis can recover radar signals represented in highly redundant dictionaries from few measurements, with improved accuracy after reweighting and robustness to measurement noise.
- Radar experiment: 400 measurements recover a six-pulse radar signal using a Gabor dictionary with about 491,520 atoms and substantial oversampling.The signal is not exactly sparse in the dictionary because pulse envelopes and time-frequency parameters do not match its atoms exactly.
- Noiseless recovery: ℓ1-analysis recovers the radar pulses and carrier frequencies well from a very small set of noiseless measurements.Recovery is reported as accurate in both the time and frequency domains, with small differences from the actual signal.
- Noise robustness: Recovery error varies linearly with the measurement-noise level, and reweighting further improves performance.The noise experiment uses white measurement noise with standard deviation σ; the authors report that the constants in Theorem 1.4 appear small.
- Reweighted recovery: One reweighted ℓ1-analysis iteration reduces the RMSE to less than a third of the comparison shown for the unreweighted recovery.The reweighted method solves sequential weighted ℓ1-minimization problems using weights from the preceding solution.
- Method comparison: ℓ1-analysis and ℓ1-synthesis both perform very well on a compressible time-domain signal, while reweighted ℓ1-analysis achieves still lower recovery error.The comparison is presented in Figure 8 across the three recovery methods.
4 Discussion
The discussion contrasts Split-analysis and ℓ1-synthesis with ℓ1-analysis, then describes fast measurement matrices satisfying the D-RIP for redundant coherent dictionaries.
- Limitations and alternatives: ℓ1-analysis may fail when a dictionary combines bases and D∗f does not decay rapidly, motivating methods that separately exploit component sparsity.Concatenated bases can spread the analysis coefficients even when the signal is sparse in each constituent basis.
- Limitations and alternatives: Split-analysis decomposes the signal into components expected to be sparse, minimizes separate analysis ℓ1 norms under a shared measurement constraint, and sums the reconstructions.The reconstructed signal is ˆf = ˆf1 + ˆf2.
- Limitations and alternatives: ℓ1-synthesis instead minimizes over a sparse coefficient expansion f = Dx and reconstructs the signal as ˆf = Dˆx.Its geometry differs fundamentally from ℓ1-analysis, and simulations show substantially different performance across signal families.
- Fast transforms: Randomly signed subsampled Fourier matrices provide fast transforms satisfying the D-RIP for redundant dictionaries, with sparsity level s = O(m/log^4 n).The matrix-vector multiply costs O(n log n), while storage costs O(m log n).
- Fast transforms: The D-RIP offers redundant-dictionary compressed sensing the same measurement, multiplication, and storage advantages as standard RIP-based compressed sensing.The discussion concludes that compressed sensing remains viable for coherent and redundant dictionaries with fast measurement matrices.