Compressed Sensing and Redundant Dictionaries

By Holger Rauhut, Karin Schnass, Pierre Vandergheynst. IEEE Transactions on Information Theory, 2007

577 citations recorded by the source corpus.

This paper extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via basis pursuit (BP) from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing, and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

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

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Image Super-Resolution Via Sparse Representation (2010, background): “Furthermore, if D satisfies an appropriate near-isometry condition, then for a wide variety of matricesL, any sufficiently sparse linear representation of a high-resolution image patch x in terms of the D can be recovered (almost) perfectly from the lowresolution image patch [9], [21].”
Spectral compressive sensing (2013, background): “However, simultaneously, the frame becomes increasingly coherent [13, 14], which decreases recovery performance (see Fig.”
Compressed and Privacy-Sensitive Sparse Regression (2009, methodology): “The proof follows the same reasoning as in [13], and is omitted.”
Compressed Sensing for Wireless Communications: Useful Tips and Tricks (2015, methodology): “atrix. After obtaining ˆs from the CS technique, we generate the estimated signal xˆ = Dˆs. Notice that due to the non-orthogonality of D, new theories are required to guarantee robust recovery [23], [26]. As an example to show the beneﬁt of dictionary learning, we consider the downlink channel esti”
Image super-resolution as sparse representation of raw image patches (2008, background): “Rather than trying to learn such a dictionary [19, 1] or using a generic set of basis vectors [21] (e.”
Compressed sensing imaging techniques for radio interferometry (2008, background): “A real basisΨ ∈ RN×T = {Ψiw}16i6N;16w6T is defined, which may be either orthogonal, with T = N , or redundant, withT > N (Rauhut et al. 2008).”
Secure and Robust Iris Recognition Using Random Projections and Sparse Representations (2011, background): “It has been shown that for sufficiently sparse and under certain conditions on D, the solution to the following optimization problem will approximate the sparsest near-solution of (23) [40]: 1882 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.”
Highly Undersampled Magnetic Resonance Image Reconstruction via Homotopic $\ell_{0}$ -Minimization (2009, background): “Redundant transformations and tight frames such as curvelets [6] have also recently been investigated [7].”
Signal Processing With Compressive Measurements (2010, background): “scribed in [46], which simply thresholds to keep only the”
Channel Estimation via Orthogonal Matching Pursuit for Hybrid MIMO Systems in Millimeter Wave Communications (2016, background): “On the other hand, the OMP-based estimator needs O L ln G2 measurements that can be much less than NT NR [37], [38].”
Compressed Sensing (2012, background): “Very few articles study the problem of incorporating a sparsifying orthonormal basis or frame, and we mention [55, 9].”
Robust Face Recognition via Sparse Representation (2009, background): “The case where x0 is instead sparse in some overcomplete basis A, and we observe that random measurements ~ y 1⁄4 R Ax0 has also been studied in [45].”
Linear Convergence of Iterative Soft-Thresholding (2007, unknown): “Let us note that the FBI property is of the same flavor as the so-called RIP (restricted isometry property) which is an important ingredient in compressive sampling [1, 6, 30].”
Compressed Sensing with Coherent and Redundant Dictionaries (2010, unknown): “[38,6]), this would yield an m × n fast transform with optimal number of measurements, m = O(s log n), obeying the D-RIP.”
Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces (2009, background): “The papers by Candes, Romberg and Tao [6], [7], [8] and by Donoho [9] have shown that under certain conditions on the signal structure and the sampling operator (which are often satisﬁed by certain random matrices), the original signal can be reconstructed using weakly polynomial time algorithms.”
Learning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization (2009, methodology): “We start by reviewing prior related work, following by the presentation of our proposed algorithm and the first results showing the computational and reconstruction advantages of this new approach.”