Compressed Sensing and Redundant Dictionaries
IEEE Transactions on Information TheoryPublished 28 April 2008Open access
Holger Rauhut, Karin Schnass, Pierre Vandergheynst
Citations551
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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, and signals that are sparse with respect to the dictionary can be recovered via basis pursuit from a small number of random measurements.
Abstract
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.
Keywords
Computer ScienceEngineering
IEEE Transactions on Information TheoryCompressed sensing
23,147 Citations2006David L. Donoho
It is shown that "most" subspaces in Ropfm are near-optimal, and that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces.
Compressed sensing
17,129 Citations2004David L. Donoho
IEEE Transactions on Information TheorySignal Recovery From Random Measurements Via Orthogonal Matching Pursuit
9,670 Citations2007Joel A. Tropp, Anna C. Gilbert
IEEE Transactions on Signal Processing$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
9,506 Citations2006Michal Aharon, Michael Elad +1 more
A novel algorithm for adapting dictionaries in order to achieve sparse signal representations, the K-SVD algorithm, an iterative method that alternates between sparse coding of the examples based on the current dictionary and a process of updating the dictionary atoms to better fit the data.
IEEE Transactions on Signal ProcessingMatching pursuits with time-frequency dictionaries
9,115 Citations1993Stéphane Mallat, Zhifeng Zhang
The authors introduce an algorithm, called matching pursuit, that decomposes any signal into a linear expansion of waveforms that are selected from a redundant dictionary of functions, chosen in order to best match the signal structures.
Communications on Pure and Applied MathematicsStable signal recovery from incomplete and inaccurate measurements
7,170 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown that it is possible to recover x0 accurately based on the data y from incomplete and contaminated observations.
SIAM Journal on Scientific ComputingAtomic Decomposition by Basis Pursuit
6,899 Citations1998Scott Shaobing Chen, David L. Donoho +1 more
Basis Pursuit (BP) is a principle for decomposing a signal into an "optimal" superposition of dictionary elements, where optimal means having the smallest l1 norm of coefficients among all such decompositions.
IEEE Transactions on Information TheoryNear-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
6,835 Citations2006Emmanuel J. Candès, Terence Tao
If the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program.
Springer series in statisticsWeak Convergence and Empirical Processes
5,037 Citations1996Aad van der Vaart, Jon A. Wellner
This chapter discusses Convergence: Weak, Almost Uniform, and in Probability, which focuses on the part of Convergence of the Donsker Property which is concerned with Uniformity and Metrization.
IEEE Transactions on Information TheoryGreed is Good: Algorithmic Results for Sparse Approximation
3,648 Citations2004Joel A. Tropp
This article presents new results on using a greedy algorithm, orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries and develops a sufficient condition under which OMP can identify atoms from an optimal approximation of a nonsparse signal.
SIAM Journal on ComputingSparse Approximate Solutions to Linear Systems
2,822 Citations1995B. K. Natarajan
It is shown that the problem is NP-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most at most $\left\lceil 18 \mbox{ Opt} ({\bf \epsilon}/2) \|{\bf A}^+\|^2_2 \ln(\|b\|_2/{\bf
Communications on Pure and Applied MathematicsFor most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution
2,541 Citations2006David L. Donoho
The techniques include the use of random proportional embeddings and almost‐spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices.
Constructive ApproximationA Simple Proof of the Restricted Isometry Property for Random Matrices
2,439 Citations2008Richard G. Baraniuk, Mark A. Davenport +2 more
Simple and direct proofs of Kashin’s theorems on widths of finite balls in Euclidean space and proofs of the existence of optimal Compressed Sensing measurement matrices are obtained and it is proved that these measurements have a certain universality with respect to the sparsity-inducing basis.
IEEE Transactions on Information TheoryStable recovery of sparse overcomplete representations in the presence of noise
2,209 Citations2005David L. Donoho, Michael Elad +1 more
This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system and shows that similar stability is also available using the basis and the matching pursuit algorithms.
Probability in Banach Spaces
1,414 Citations1991Michel Ledoux, Michel Talagrand
Probability in Banach Spaces: Isoperimetry and Processes
1,276 Citations1991Michel Ledoux, Michel Talagrand
Constructive ApproximationAdaptive greedy approximations
1,141 Citations1997Geoffrey M. Davis, Stéphane Mallat +1 more
A notion of the coherence of a signal with respect to a dictionary is derived from the characterization of the approximation errors of a pursuit from their statistical properties, which can be obtained from the invariant measure of the pursuit.
Journal of the American Statistical AssociationProbability Inequalities for the Sum of Independent Random Variables
756 Citations1962G. G. Bennett
Database-friendly random projections
698 Citations2001Dimitris Achlioptas
This work gives a novel construction of the embedding of k-dimensional Euclidean space, suitable for database applications, which amounts to computing a simple aggregate over k random attribute partitions.
Journal of the American Mathematical SocietyCounting faces of randomly projected polytopes when the projection radically lowers dimension
462 Citations2008David L. Donoho, Jared Tanner
This paper develops asymptotic methods to count faces of random high-dimensional polytopes; a seemingly dry and unpromising pursuit that has surprising implications in statistics, probability, information theory, and signal processing with potential impacts in practical subjects like medical imaging and digital communications.
Constructive ApproximationUniform Uncertainty Principle for Bernoulli and Subgaussian Ensembles
320 Citations2008Shahar Mendelson, Alain Pajor +1 more
The paper considers random matrices with independent subgaussian columns and provides a new elementary proof of the Uniform Uncertainty Principle for such matrices and combines a simple measure concentration and a covering argument, which are standard tools of high-dimensional convexity.
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
230 Citations2006Mark Rudelson, Roman Vershynin
The first guarantees for universal measurements (i.e. which work for all sparse functions) with reasonable constants are proved, based on the technique of geometric functional analysis and probability in Banach spaces.
Applied and Computational Harmonic AnalysisRandom sampling of sparse trigonometric polynomials
199 Citations2006Holger Rauhut
This work proposes to recover the trigonometric polynomial by Basis Pursuit, i.e., by l 1 -minimization, and model the random sampling points by a continuous uniform distribution on the cube, where the sampling points are restricted to a grid but allow them to have arbitrary position.
Journal of the American Statistical AssociationProbability Inequalities for the Sum of Independent Random Variables
150 Citations1962George N. Bennett
EURASIP Journal on Advances in Signal ProcessingFast Minimization by Iterative Thresholding for Multidimensional NMR Spectroscopy
65 Citations2007Iddo Drori
The first method which takes advantage of the sparsity of the wavelet representation of the NMR spectra and reconstructs the spectra from partial random measurements of its free induction decay by solving the following optimization problem.
The Johnson-Lindenstrauss Lemma Meets Compressed Sensing
57 Citations2006Richard G. Baraniuk, Mark A. Davenport +2 more
ArXiv.orgSparse reconstruction by convex relaxation: Fourier and Gaussian measurements
39 Citations2006Mark Rudelson, Roman Vershynin
Average Case Analysis of Multichannel Thresholding
25 Citations2007Rémi Gribonval, Boris Mailhé +3 more
This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries and works out both worst case and average case recovery analyses of this algorithm.
ArXiv.orgCounting faces of randomly-projected polytopes when the projection radically lowers dimension
8 Citations2006David L. Donoho, Jared Tanner