Compressed Sensing with Coherent and Redundant Dictionaries

Emmanuel J. Candès, Yonina C. Eldar, Deanna Needell

Abstract

Traditional compressed sensing (CS) theory requires signals to be sparse in an orthonormal basis or an incoherent dictionary. However, practical applications often utilize redundant and highly correlated dictionaries, such as Gabor frames or Curvelets, where standard theory fails. This paper bridges this gap by introducing the Restricted Isometry Property adapted to $D$ (D-RIP) and advocating for an $\ell_1$-analysis approach. We demonstrate that accurate signal recovery is possible even when dictionary atoms are highly correlated, shifting the focus from coefficient recovery to signal reconstruction.

Introduction

Compressed Sensing (CS) has revolutionized signal processing by allowing for the recovery of sparse signals from fewer measurements than required by the Nyquist-Shannon sampling theorem. A fundamental pillar of standard CS is the assumption of sparsity in an orthonormal basis or an "incoherent" dictionary—one where the columns (atoms) are significantly different from each other.

In practice, however, signals are often represented using redundant dictionaries, where the number of atoms exceeds the signal dimension. Examples include Gabor frames for audio processing and Curvelets for image analysis. In these cases, atoms are frequently highly correlated (coherent). Standard theory suggests that if two atoms are nearly identical, they cannot be distinguished, rendering signal recovery impossible. This paper addresses how to perform compressed sensing when the dictionary is both redundant and coherent.

Methodology: From Synthesis to Analysis

The authors propose a shift from the traditional $\ell_1$-synthesis approach to $\ell_1$-analysis.

In the standard synthesis approach, one seeks sparse coefficients $x$ such that the signal $f = Dx$. In contrast, the analysis approach seeks a signal $f$ whose "analysis coefficients" ($D^*f$) are sparse. The optimization problem is formulated as: $$\min \|D^* \tilde{f}\|_1 \text{ subject to } \|A\tilde{f} - y\|_2 \le \epsilon$$

The mapping from the coefficient domain through the signal domain to the compressed sensing domain.

To provide theoretical guarantees for this approach, the authors introduce the Restricted Isometry Property adapted to $D$ (D-RIP). Unlike the standard RIP, which requires the sensing matrix $A$ to preserve the lengths of all sparse vectors, D-RIP only requires $A$ to preserve the lengths of vectors that lie in the image of sparse vectors under the dictionary $D$. This flexibility allows the dictionary itself to be highly coherent without compromising the ability to reconstruct the signal $f$.

Experimental Setup

The theoretical framework was evaluated using simulations that mirror real-world challenges:

  • Radar Signal Simulation: The study used a superposition of six trapezoidal radar pulses with random carrier frequencies and arrival times.
  • Highly Redundant Dictionaries: A Gabor dictionary, oversampled by a factor of 60, was used to represent these signals.
  • Measurement Process: Gaussian random sensing matrices were employed to compress the signal from 8,192 Nyquist intervals down to 400 measurements.

Key Insights and Results

The research yields several critical insights into the nature of compressed sensing:

  • Coherence is Not the Enemy: While high coherence makes it impossible to identify specific active coefficients, it does not prevent the perfect reconstruction of the actual signal.
  • Analysis vs. Synthesis: In redundant settings, $\ell_1$-analysis is geometrically more robust and accurate than the synthesis approach.
  • Theoretical Robustness: The authors provide a rigorous error bound (Theorem 1.4), proving that recovery error is proportional to measurement noise and the quality of the signal's sparse approximation.
  • Performance Gains: Iterative "reweighted $\ell_1$-analysis" was shown to reduce the root-mean-squared error (RMSE) by a factor of 3 to 4 compared to standard methods.

Discussion and Limitations

While the D-RIP framework is powerful, it has limitations. For dictionaries formed by concatenating very different bases (e.g., Identity and Fourier), the analysis coefficients $D^*f$ may not be sparse even if the signal is sparse in $D$. To address this, the authors suggest "Split-analysis" as a future research direction. Additionally, the computational cost of solving $\ell_1$-analysis for massive, oversampled dictionaries remains high, necessitating the development of more efficient, specialized solvers.

Summary updated

BibTeX
@inproceedings{candes2010compressed,
  author = {Emmanuel J. Candès and Yonina C. Eldar and Deanna Needell},
  title = {{Compressed Sensing with Coherent and Redundant Dictionaries}},
  booktitle = {Applied and Computational Harmonic Analysis},
  year = {2010},
  doi = {10.1016/j.acha.2010.10.002},
}
Figure