Decoding by linear programming
By E.J. Candes, Terence Tao. 2005
7,654 citations recorded by the source corpus.
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.
Subfields: Computational Mechanics, Computer Networks and Communications, Control and Systems Engineering
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
- E.J. Candes
- Martin J. Wainwright
- Francis R. Bach
- Julien Mairal
- Yonina C. Eldar
- Richard Baraniuk
- Prateek Jain
- Wotao Yin
In Computer Networks and Communications
- Ali H. Sayed
- Martin J. Wainwright
- Angelia Nedić
- Francis R. Bach
- Tong Zhang
- Michael G. Rabbat
- Richard Baraniuk
- Wotao Yin
In Control and Systems Engineering
- Francis R. Bach
- Cun-Hui Zhang
- Martin J. Wainwright
- Nati Srebro
- Peter Buhlmann
- David L. Donoho
- Steven L. Brunton
- E.J. Candes
Citations in the corpus
- Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “We design a sparse encoding process, based on real-error correction [CT05], which enables efficient encoding, and the worker nodes alternatively locally encode using the sparse structure.”
- Exact Matrix Completion via Convex Optimization (2008, background): “random variables and the sequences fA(k)gare also independent from each other (the sequences fA(k)gand fb kgare available to the analyst). Building on the concept of restricted isometry introduced in [12] in the context of sparse signal recovery, [27] establishes the rst sucient conditions for which”
- Introduction to the non-asymptotic analysis of random matrices (2010, background): “A basic result in compressed sensing, due to Candès and Tao [17, 16], is that for sparse signals | supp(x)| ≤ k, the convex problem recovers the signal x from its measurement y exactly, provided that the measurement matrix A is quantitatively non-degenerate.”
- A Singular Value Thresholding Algorithm for Matrix Completion (2008, methodology): “Our algorithm is inspired by recent work in the area of 1 minimization, and especially by the work on linearized Bregman iterations for compressed sensing; see [11, 12, 13, 27, 55, 67] for linearized Bregman iterations and [17, 19, 20, 21, 30] for some information about the field of compressed sensi”
- Nearly unbiased variable selection under minimax concave penalty (2010, methodology): “On the other hand, for given do ≡ dn it is closely related to the restricted isometry constant δd ≡max{|‖ΣAu‖− 1| : |A|= d,‖u‖= 1} [Candés and Tao (2005)], although c∗ > 2 is allowed in (2.”
- “Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “The same result can also be derived by recasting the decoding problem as a sparse reconstruction problem, and borrowing ideas from standard compressive sensing literature [24] which also yields a concrete, decoding algorithm.”
- Uncertainty Principles and Vector Quantization (2006, methodology): “Known also as the Restricted Isometry Condition, UUP was shown in [8] to be a guarantee that one can efficiently solve underdetermined systems of linear equations Ux = b under the assumption that the solution is sparse, | supp( x ) | ≤ δN . developing This is a part of the fast area of Compressed…”
- Multi-Stage Multi-Task Feature Learning (2012, neutral): “M L ] 2 Keywords: Multi-Task Learning, Multi-Stage, Non-convex, Sparse Learning”
- Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, background): “Note that this is similar to the restricted isometry property (RIP) used in compressed sensing [4], except that (4) is only required for submatrices of the form SA.”
- On the conditions used to prove oracle results for the Lasso (2009, background): “We now present some definitions from [10].”
- Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization (2009, methodology): “These results imply that for generic systems of equations, it is possible to correct a constant fraction of arbitrary errors in polynomial time [Candès and Tao 2005].”
- Confidence intervals and hypothesis testing for high-dimensional regression (2013, methodology): “A copious theoretical literature (Candès and Tao, 2005; Bickel et al., 2009; Bühlmann and van de Geer, 2011) shows that, under suitable assumptions on X, the LASSO is nearly as accurate as if the support S was known a priori.”
- Understanding the Sparsity: Augmented Matrix Factorization with Sampled Constraints on Unobservables (2014, background): “This definition of the RIP is a generalization to matrices from sparse vectors in [9].”
- Sparse Subspace Clustering: Algorithm, Theory, and Applications (2013, positive): “Using advances in sparse [29], [30], [31] and low-rank [32], [33], [34] recovery algorithms, the Sparse Subspace Clustering (SSC) [35], [36], [37], Low-Rank Recovery (LRR) [38], [39], [40], and Low-Rank Subspace Clustering (LRSC) [41] algorithms pose the clustering problem as one of finding a sparse”
- Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity (2008, methodology): “There exists an intimate relationship between the LP reconstruction accuracy and the RIP property, first described by Candés and Tao in [4].”