Error correction via linear programming

By E.J. Candes, Mark Rudelson, Terence Tao, Roman Vershynin. IEEE Annual Symposium on Foundations of Computer Science, 2005

303 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/04c89a05810eb787476ac3039bb23582eba100f9

How researchers see this paper

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

Citations in the corpus

The Dantzig selector: Statistical estimation when P is much larger than n (2005, unknown): “,XhTj i≤θ X j∈T01 |cj|2 ! 1/2 khTj kℓ2 ≤ θ √ 1−δ kPV XhTj kℓ2khTj kℓ2, which upon combining with (3.8) gives kPV XhTj kℓ2 ≤ θ √ 1−δ (3.9) khTj kℓ2. We then develop an upperboundon P j≥2khTj kℓ2 as in [12]. By construction, the magnitude of each component hTj+1 [i] of hTj+1 is less than the average o”
Generalized Orthogonal Matching Pursuit (2011, unknown): “Let”
Advances on Spectrum Sensing for Cognitive Radio Networks: Theory and Applications (2017, background): “In fact, in complexity theory, 0 minimisation can be classified as an NP-hard problem in general [120].”
Distributed Compressive Sensing (2009, unknown): “[27]andDonoho[28]haverecentlyproposedtractablerecoveryproceduresbased onlinearprogramming,demonstratingtheremarkablepropertythatsuchproceduresprovidethe sameresultasthecombinatorialsearchaslongascKprojectionsareusedtoreconstructthesignal (typicallyc≈3or4)[31] [32] [33].”
Minimization of ℓ1-2 for Compressed Sensing (2015, methodology): “It is worth noting that similar results was proved in [9] for the lp unconstrained problem using the second-order optimality condition.”
Lower Bounds in Differential Privacy (2011, background): “We remark that the relation between LP decoding and Euclidean spaces is very well known in context of compressed sensing [4].”
Exact Reconstruction of Sparse Signals via Nonconvex Minimization (2007, result): “The theorem generalizes the corresponding result of Candes et al. for and in [8].”
Analog-to-Information Conversion via Random Demodulation (2006, methodology): “While solving this ‘ 0 optimization problem is prohibitively complex (it is believed to be NP-hard [4]), if we use M = O ( K log( N/K )) measurements, then we need only solve for the ‘ 1 -sparsest coefﬁcients α that agree with the measurements y [2], [3] This optimization problem, also known as…”
Noncommutative Bennett and Rosenthal inequalities (2011, methodology): “However, the restricted isometry property(RIP) on Φ is an extremely important tool for exact reconstruction due to Candes and Tao [7](see also [5]).”
Reconstruction and Subgaussian Operators in Asymptotic Geometric Analysis (2007, background): “This particular problem has been addressed by several authors with view of application to signal reconstruction (see [D2, CT1, CT2, CT3 ] for the most recent contributions), in the following context: The sets considered were either the unit ball in ‘n 1 or the unit balls in weak ‘n p spaces for 0 ”
Complementarity Formulations of ' 0 -norm Optimization Problems (2013, background): “Theoretical results are known that provide sufficient conditions under which an optimal solution to (2) is also optimal to (1) [7, 14, 21, 38].”
Robust Face Recognition via Sparse Representation (2009, background): “For example, [12] shows that even for a random matrix B drawn from a Gaussian ensemble, EBP(B) > ρ0m with overwhelming probability, as m→∞.”
Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity (2008, methodology): “[2], [4]–[6].”
One‐Bit Compressed Sensing by Linear Programming (2011, unknown): “In particular, if A has Gaussian i.i.d. entries, then we may take m D O.s log .n=s// and still recover x exactly with high probability [8, 9]; see [26] for an overview.”