Greed is good: algorithmic results for sparse approximation

By Joel A. Tropp. IEEE Transactions on Information Theory, 2004

3,838 citations recorded by the source corpus.

Subfields: Computational Mechanics, Mechanics of Materials, Signal Processing

View Paper: https://www.semanticscholar.org/paper/46ee0292a71fa86a9e2f9d691da5f0f1cf281f83

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 Mechanics of Materials

In Signal Processing

Citations in the corpus

Simultaneous sparse approximation via greedy pursuit (2005, result): “Using an argument analogous to that in [4, Thm. 3.1], we discover that It can be shown that the second fraction in (3) is no greater than In the numerator, we replace Ψ opt with Φ = [ Φ opt Ψ opt ] , using the fact that the columns of ( S − A opt ) are orthogonal to the columns of Φ opt .”
$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation (2006, background): “The simplest ones are the matching pursuit (MP) [12] and the orthogonal matching pursuit (OMP) algorithms [13]–[16].”
Post-Selection Inference for ℓ1-Penalized Likelihood Models (2017, background): “where (F, M) = EF [X −MW(β M)XM]EF [(X MW(β M)XM)] is a population version of the matrix appearing in the well-known irrepresentable condition (Tropp, 2004; Wainwright, 2009) and the remainder RM,2 goes to 0 in probability after appropriate rescaling Tian & Taylor (2015). Hence our “inactive constra”
Numerical construction of Green's functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations (2012, methodology): “A parallel evolution in the signal processing literature led to the development of widely used basis and matching pursuit algorithms [35, 36, 135], the Dantzig selector (DS) [31], and many others (see [49], Chapters 3 and 5, for a good overview).”
Fast Solution of $\ell _{1}$ -Norm Minimization Problems When the Solution May Be Sparse (2008, background): “Since there exists a wide range of cases where -minimization is known to find the sparsest solution while OMP is known to fail [9], [15], [51], HOMOTOPY gives in some sense the best of both worlds by a single algorithm: speed where possible, sparsity where possible.”
Estimation of Rapidly Time-Varying Sparse Channels (2007, background): “Finally, a larger , in general, will lead to a symbol matrix with better orthogonality among its columns, a property desirable for sparse processing algorithms [15].”
Low-dimensional models in spatio-temporal wind speed forecasting (2015, neutral): “An interested reader can refer to [23], [24] for several proposed recovery conditions.”
Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit (2015, background): “In particular, note that the matrix X need not satisfy the mutual incoherence [32] or restricted isometry properties [11], as two points in a sub-space could be arbitrarily close to each other.”
Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise (2011, methodology): “This lemma is a special case of Theorem 3.5 in Tropp (2004).”
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation (2009, methodology): “2, it is shown in [43] that BP will recover a single k-sparse vector.”
MR Image Reconstruction From Highly Undersampled k-Space Data by Dictionary Learning (2011, methodology): “However, there are greedy algorithms to solve this problem such as orthogonal matching pursuit (OMP) [11], [ 33 ].”
Online Kernel Principal Component Analysis: A Reduced-Order Model (2012, background): “The following result is essentially due to [47], [48].”
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery (2009, methodology): “We consider the problem of representing a vector y ∈ C L in a given dictionary D of size L × N with L N , so that for a coefﬁcient vector x ∈ C N .”
Channel Estimation via Orthogonal Matching Pursuit for Hybrid MIMO Systems in Millimeter Wave Communications (2016, background): “Because the RHS of (40) is positive, the condition can be reduced to the well-known bound [32] given by”
An Empirical Bayesian Strategy for Solving the Simultaneous Sparse Approximation Problem (2007, background): “The single response reduction of (6) has been studied exhaustively [11], [16], [20], [49].”
Compressed Sensing for Real-Time Energy-Efficient ECG Compression on Wireless Body Sensor Nodes (2011, methodology): “The latter is encoded using lossless Huffman coding to produce the encoded vector c.”
Compressed Sensing with Coherent and Redundant Dictionaries (2010, neutral): “Standard results then require that the measurement matrix satisfies a strict incoherence property [41,12], as even the RIP imposes this.”
$L_{1/2}$ Regularization: A Thresholding Representation Theory and a Fast Solver (2012, neutral): “The greedy strategies, such as the matching pursuit type of algorithms [28], OMP [29], ROMP [30], are very fast for non-highdimensional problems [31], [32].”