Uncertainty principles and ideal atomic decomposition

By David L. Donoho, Xiaoming Huo. 2001

2,128 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

The Dantzig selector: Statistical estimation when P is much larger than n (2005, background): “eters β is feasible and, hence, kβˆk ℓ1 ≤kβkℓ1. Decompose βˆ as βˆ=β +h and let T 0 be the support of β, T 0 ={i:βi 6=0 }. Then h obeys two geometric constraints: 1. First, as essentially observed in [20], kβkℓ1 −khT0kℓ1 +khTc 0 kℓ1 ≤kβ +hkℓ1 ≤kβkℓ1, where again the ith component of the vector hT0 i”
Wavelet Scattering Regression of Quantum Chemical Energies (2016, background): “However, these hypotheses are violated when Φ(x) = (φk(x))k includes highly correlated functions [19, 18, 13].”
The Cosparse Analysis Model and Algorithms (2011, positive): “A Sufficient Condition for the Success of the l1-minimization In the sparse synthesis framework, there is a well-known necessary and sufficient condition called the null space property (NSP) [15] that guarantees the success of the synthesis l1-minimization”
Precise Undersampling Theorems (2010, background): “The earliest undersampling theorems were based on notion of coherence and covered only cases where k G ffiffi n p , [8], [23]–[27] which is much weaker than the n we know to be descriptive of actual performance (this was already discussed and demonstrated in [23]).”
For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution (2006, background): “Since for an n by m matrix with m > n, the incoherence is bounded by M ≥ 1/ √ n [5], this result accomodates at most O( √ n) nonzeros.”
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation (2009, background): “Assuming the columns of A are normalized, ‖al‖2 = 1, we can guarantee that (6) holds as long as the coherence μ of A is small enough, where [17] μ = max j 6=l |〈aj , al〉|.”
$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation (2006, background): “Extensive study of these algorithms in recent years has established that if the sought solution is sparse enough, these techniques recover it well in the exact case [16], [26]–[30].”
Synthesis of Sparse Arrays With Focused or Shaped Beampattern via Sequential Convex Optimizations (2012, methodology): “To further enhance the sparsity of the solution of the problem (8), an algorithm that consists in solving a sequence of weighted minimization problems has been recently proposed by [19], [20].”
Sparse solutions to linear inverse problems with multiple measurement vectors (2005, background): “obtained solution. Several results have been recently developed for the case [ 43 ]‐[49].”
Sparse Bayesian learning for basis selection (2004, background): “Additionally, in [24] and [25], much attention is placed on such dictionaries.”
Restricted Eigenvalue Properties for Correlated Gaussian Designs (2010, background): “See the papers (Cohen et al., 2009; Donoho and Huo, 2001; Elad and Bruckstein, 2002; Feuer and Nemirovski, 2003 ) for more discussion of restricted nullspaces and equivalence to exact recovery of basis pursuit.”
Sparse Representation for Signal Classification (2006, background): “In [11], it is proved that if certain conditions on the sparsity is satisfied, i.”
Compressed sensing (2006, background): “There is by now an extensive literature exhibiting results on equivalence of and minimization [27]–[34].”
Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions (2004, background): “For example, consider as in [9, 10] the Dirac comb signal: we suppose that the sample size N is a perfect square and let f be equal to 1 at multiples of √ N and 0 everywhere else”
Recovery of exact sparse representations in the presence of bounded noise (2005, background): “In order to define when this is the case, we introduce the mutual coherence [2]”