Improved sparse approximation over quasiincoherent dictionaries
Published 21 June 2004
Joel A. Tropp, Anna C. Gilbert, S. Muthukrishnan, Michael Strauss
Citations74
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
A new greedy algorithm for solving the sparse approximation problem over quasiincoherent dictionaries that provides strong guarantees on the quality of the approximations it produces, unlike most other methods for sparse approximation.
Abstract
This paper discusses a new greedy algorithm for solving the sparse approximation problem over quasiincoherent dictionaries. These dictionaries consist of waveforms that are uncorrelated "on average," and they provide a natural generalization of incoherent dictionaries. The algorithm provides strong guarantees on the quality of the approximations it produces, unlike most other methods for sparse approximation. Moreover, very efficient implementations are possible via approximate nearest-neighbor data structures.
Keywords
Computer ScienceEngineering
Matrix Analysis
22,234 Citations1985Roger A. Horn, Charles R. Johnson
Cambridge University Press eBooksMatrix Analysis
10,056 Citations1985Roger A. Horn, Charles R. Johnson
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.
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 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.
Proceedings of the National Academy of SciencesOptimally sparse representation in general (nonorthogonal) dictionaries via ℓ <sup>1</sup> minimization
2,941 Citations2003David L. Donoho, Michael Elad
This article obtains parallel results in a more general setting, where the dictionary D can arise from two or several bases, frames, or even less structured systems, and sketches three applications: separating linear features from planar ones in 3D data, noncooperative multiuser encoding, and identification of over-complete independent component models.
IEEE Transactions on Information TheoryUncertainty principles and ideal atomic decomposition
1,967 Citations2001David L. Donoho, Xiaoming Huo
It is proved that if S is representable as a highly sparse superposition of atoms from this time-frequency dictionary, then there is only one such highly sparse representation of S, and it can be obtained by solving the convex optimization problem of minimizing the l/sup 1/ norm of the coefficients among all decompositions.
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.
Optical EngineeringAdaptive time-frequency decompositions
348 Citations1994Geoffrey M. Davis
An algorithm is derived that isolates the coherent structures of a signal and describes an application to pattern extraction from noisy signals, using a greedy algorithm called a matching pursuit, which computes a suboptimal expansion.
Astronomy and AstrophysicsAstronomical image representation by the curvelet transform
257 Citations2003Jean‐Luc Starck, David L. Donoho +1 more
Digital implementations of two newly developed multiscale representation systems, namely, the ridgelet and curvelet transforms and the Morphological Component Analysis are outlined, which consists in separating features in an image which do not present the same morphological characteristics.
Approximation of functions over redundant dictionaries using coherence
190 Citations2003Anna C. Gilbert, S. Muthukrishnan +1 more
The technical crux of the result is the proof that two commonly used local search techniques, when combined appropriately, gives a provably near-optimal signal representation over redundant dictionaries with small coherence.
High-dimensional computational geometry
116 Citations2000Rajeev Motwani, Piotr Indyk
This thesis shows that it is in fact possible to obtain efficient algorithms for the nearest neighbor problem and a wide range of metrics, including Euclidean, Manhattan or maximum norms and Hausdorff metrics; some of the results hold even for general metrics.
Constructive ApproximationBest Approximation with Walsh Atoms
11 Citations1997Lars Villemoes
It is shown that up to a constant factor, a linear combination of K atoms can be represented to relative error by alinear combination of $K^2 \log(1/\varepsilon)$ orthogonal atoms.