Sparse nonnegative solution of underdetermined linear equations by linear programming.

By David L. Donoho, Jared Tanner. Proceedings of the National Academy of Sciences of the United States of America, 2005

645 citations recorded by the source corpus.

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering, Numerical Analysis

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

How researchers see this paper

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

In Discrete Mathematics and Combinatorics

In Electrical and Electronic Engineering

In Numerical Analysis

Citations in the corpus

Statistical mechanics of complex neural systems and high dimensional data (2013, methodology): “ measurements. Thus replica theory predicts phase a transition between a perfect and an imperfect reconstruction regime in the α-fplane, as veriﬁed in Fig. 8A. This phase boundary was ﬁrst derived in [123, 122] using very diﬀerent methods of convex geometry. The phase boundary simpliﬁes in the f → 0”
Optimal errors and phase transitions in high-dimensional generalized linear models (2017, methodology): “…and theoretically relevant in many different contexts: i ) In signal processing, GLM estimation with a random matrix Φ has been studied with considerable attention in the context of compressed sensing (9–11), where an n -dimensional sparse signal is recovered from m n noisy measurements.”
Statistical physics of inference: thresholds and algorithms (2015, background): “It is possible to compute exactly the performance of `1-reconstruction in the limit N → ∞, and the analytic study shows the appearance of a sharp phase transition [82].”
Iteratively reweighted least squares minimization for sparse recovery (2008, background): “of l1-minimization saw a dramatic increase in the last 5 years [20, 24 , 21, 25, 7, 4, 3, 6], with the development of fairly general mathematical frameworks in which l1-minimization, known heuristically to be sparsity-promoting, can be proved to recover sparse solutions exactly.”
Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization (2012, background): “ndition (GLP) in (1.3) holds. We start by studying the noiseless (ε= 0) and exactly sparse case. Figure 2 provides some intuition for the problem on the basis of geometric ideas used and developed in [15, 16, 19, 48]. The left panel displays a polyhedral cone C = cone{Xj} p j=1, p= 6 contained in R3”
Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation (2019, methodology): “rices and spin-glass models in large spatial dimensions[21, 19]. Such limits are also well-studied in modern statistics[25] (for example to understand phase-transition phenomena in the LASSO algorithm[6]). In this limit, we give analytical formulae for TE and GE with l2 or ridge regularization. For ”
Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing (2009, background): “The classical example of cyclic polytopes shows that (LP) can have a notably higher success rate for very special matrices than it does for random matrices (Donoho & Tanner, 2005a).”
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization (2007, background): “ional settings. Intriguingly, Figure 4 also demonstrates a \phase transition" between perfect recovery and failure. As observed in several recent papers by Donoho and his collaborators (See e.g. [18, 19]), the random sparsity recovery problem has two distinct connected regions of parameter spac”
High-dimensional covariance matrix estimation with missing observations (2012, background): “This recent paradigm where high-dimensional objects of interest admit in fact a small intrinsic dimension has produced spectacular results in several fields, such as compressed sensing where it is possible to recover s-sparse vectors of dimension p with only n = O (s log(ep/s)) measurements provided”
Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis. (2012, background): “…phase boundary αc ( f ) such that if α > αc ( f ), then L1 minimization will typically yield perfect signal reconstruction, whereas if α < αc ( f ), it will yield a nonzero error (see Figure 3) (Donoho & Tanner 2005a,b, Donoho et al. 2009, Kabashima et al. 2009, Ganguli & Sompolinsky 2010b).”
Precise Undersampling Theorems (2010, background): “What can replace the sampling theorem in this setting? In this paper, we describe a range of recent work [5], [7], [10]–[13] on what we here call undersampling theorems.”
On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations (2008, result): “(enforcing sparsity). For example, recent work reported in [ 11 , 12, 13] proves that the p = 0”