Compressed Sensing with Coherent and Redundant Dictionaries

By E.J. Candes, Yonina C. Eldar, Deanna Needell. arXiv.org, 2010

961 citations recorded by the source corpus.

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 ‘1-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 rst 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 ‘1-analysis for such problems.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Signal Processing

View Paper: https://www.semanticscholar.org/paper/a600896d3dee91a3c1edae3a745d81b69976bb08

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Electrical and Electronic Engineering

In Signal Processing

Citations in the corpus

Discrete Signal Processing on Graphs: Sampling Theory (2015, background): “In [42], the authors proposed a general way to perform compressed sensing with non-sparse signals using dictionaries.”
Spectral compressive sensing (2013, methodology): “The CS framework was also recently extended to signals having a sparse representation in a redundant and coherent frame through the use of analysis sparsity [4].”
Distributed Compressive Sensing: A Deep Learning Approach (2015, background): “, Ψ ∈ <N×N1 where N < N1 (compressed sensing for over-complete dictionaries is introduced in [7]).”
Compressed Sensing for Wireless Communications: Useful Tips and Tricks (2015, background): “Although such assumption i s valid in many applications, there are still plenty of scenarios where the target signal m ay not be sparsely represented in an orthonomal basis, but in an overcomplete dictionary [75].”
FREAK: Fast Retina Keypoint (2012, methodology): “In general, adding redundancy allow us to use less receptive fields which is a known strategy employed in compressed sensing or dictionary learning [6].”
Using deep stacking network to improve structured compressed sensing with Multiple Measurement Vectors (2013, background): “This basis can be complete, i.e.,Ψ ∈ ℜN×N , or over-complete, i.e., Ψ ∈ ℜN×N1 whereN N1 (compressed sensing for overcomplete dictionaries was introduced in [4]).”
Stability and robustness of ℓ1-minimizations with Weibull matrices and redundant dictionaries (2014, background): “…+ e)‖2 ≤ C√ s σs(x)1 +Dη,(2) ∗Key words: compressive sensing, `1-minimization, basis pursuit, robust null space property, quotient property, Weibull random variables, frames and redundant dictionaries †AMS classification: 42C15, 65K10, 94A12, 94A20 ‡The author is supported by the NSF grant…”
Compressed Sensing (2012, background): “Very few articles study the problem of incorporating a sparsifying orthonormal basis or frame, and we mention [55, 9].”
The Cosparse Analysis Model and Algorithms (2011, positive): “More recently, Cand`es et al. [9] provided a theoretical study on the error when the analysis-based ℓ 1 -minimization is used in the context of compressed sensing.”
Templates for convex cone problems with applications to sparse signal recovery (2010, result): “An exception is the very recent paper [11] which provides the first results for `1-analysis.”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, positive): “As shown recently in [10], concentration inequalities of type (3) allow for the extension of the compressed sensing methodology to redundant dictionaries – in particular, tight frames – as opposed to orthonormal bases only.”
Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model (2013, background): “This case of analysis dictionary training is a challenging problem, which has recently started to attract attention [13]–[16].”
Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known Patterns (2017, background): “2) The number of measurements p must satisfy [99], [98], [33], [100], [104] p ∼ O ( K log( n/K )) .”
Millimeter Wave Beam-Selection Using Out-of-Band Spatial Information (2017, neutral): “maxm<n |[ ]∗:,m [ ]:,n | ‖[ ]:,m‖2‖[ ]:,n‖2 [42].”