Error correction via linear programming

Emmanuel J. Candès, Mark Rudelson, Terence Tao, Roman Vershynin

Type: Article

Publication Date: 2005-01-01

Citations: 273

DOI: https://doi.org/10.1109/sfcs.2005.5464411

Abstract

Suppose we wish to transmit a vector f ϵ R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?

Locations

CaltechAUTHORS (California Institute of Technology) - View - PDF
CaltechAUTHORS (California Institute of Technology) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Decoding by Linear Programming	2005	Emmanuel J. Candès Terence Tao
+ PDF Chat	Decoding by Linear Programming	2005	Emmanuel J. Candès Terence Tao
+	Highly robust error correction by convex programming	2006	Emmanuel J. Candès Paige Randall
+ PDF Chat	The limits of error correction with l<inf>p</inf> decoding	2010	Meng Wang Weiyu Xu Ao Tang
+	Introduction to Mathematical Programming-Based Error-Correction Decoding	2015	Michael Helmling
+	Linear Codes	2017	Minjia Shi Adel Alahmadi Patrick Solé
+ PDF	Dense error correction via l1-minimization	2009	John Wright Yi Ma
+	The Limits of Error Correction with lp Decoding	2010	Meng Wang Weiyu Xu Ao Tang
+	Linear Programming Bounds	2019	Peter Boyvalenkov Danyo Danev
+ PDF Chat	Error-Resilient Weakly Constrained Coding via Row-by-Row Coding	2024	Prachi Mishra Navin Kashyap
+	Linear Programming Bounds.	2019	Peter Boyvalenkov Danyo Danev
+	Correcting Errors in Linear Measurements and Compressed Sensing of Multiple Sources	2013	Alexander Petukhov Inna Kozlov
+	Correcting Errors in Linear Measurements and Compressed Sensing of Multiple Sources	2013	A. K. Petukhov Inna Kozlov
+	Error correction based on partial information	2017	Itzhak Tamo Min Ye Alexander Barg
+	Error correction based on partial information.	2017	Itzhak Tamo Min Ye Alexander Barg
+	Dense Error Correction Via $\ell^1$-Minimization	2010	John Wright Yi Ma
+	Error Correction Based on Partial Information	2019	Itzhak Tamo Min Ye Alexander Barg
+	Solving Linear Equations Parameterized by Hamming Weight.	2014	V. Arvind Sebastian Kuhnert Johannes Köbler Jacobo Torán
+	Linear error-block codes	2005	Keqin Feng Lanju Xu Fred J. Hickernell
+	Linear Approximation	1967	Günter Meinardus

Works That Cite This (102)

Action	Title	Year	Authors
+ PDF Chat	The Restricted Isometry Property of Subsampled Fourier Matrices	2017	Ishay Haviv Oded Regev
+	Gaussian averages of interpolated bodies and applications to approximate reconstruction	2007	Y. Gordon Alexander E. Litvak Shahar Mendelson Alain Pajor
+	Stochastic Gradient Descent Variants for Corrupted Systems of Linear Equations	2020	Jamie Haddock Deanna Needell Elizaveta Rebrova William Swartworth
+	Reconstruction and subgaussian operators	2005	Shahar Mendelson Alain Pajor Nicole Tomczak-Jaegermann
+	Universality laws for randomized dimension reduction, with applications	2015	Samet Oymak Joel A. Tropp
+	Compressive sensing: a paradigm shift in signal processing	2008	Olga Holtz
+	Fast Approximate Construction of Best Complex Antipodal Spherical Codes	2017	Miguel Heredia Conde Otmar Loffeld
+	Deterministic Bounds for Restricted Isometry of Compressed Sensing Matrices	2011	Shriram Sarvotham Richard G. Baraniuk
+	Gaussian polytopes: A cumulant-based approach	2018	Julian Grote Christoph Thäle
+	Lattices from equiangular tight frames	2016	Albrecht Böttcher Lenny Fukshansky Stephan Ramon Garcia Hiren Maharaj Deanna Needell

Works Cited by This (28)

Action	Title	Year	Authors
+ PDF	Recovery of Short, Complex Linear Combinations Via&lt;tex&gt;$ell _1$&lt;/tex&gt;Minimization	2005	Joel A. Tropp
+ PDF	On the distribution of the largest eigenvalue in principal components analysis	2001	Iain M. Johnstone
+	None	2003	Peter G. Casazza Jelena Kovačević
+ PDF	The Concentration of Measure Phenomenon	2005	Michel Ledoux
+	LECTURES ON DISCRETE GEOMETRY (Graduate Texts in Mathematics 212) By JIRÍ MATOUŠEK: 481 pp., £31.50 (US$39.95), ISBN 0-387-95374-4 (Springer, New York, 2002).	2003	Imre Bárány
+	Quantized Frame Expansions with Erasures	2001	Vivek K Goyal Jelena Kovačević Jonathan A. Kelner
+	Breakdown of equivalence between the minimal<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si120.gif" overflow="scroll"><mml:msup><mml:mrow><mml:mo>ℓ</mml:mo></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:math>-norm solution and the sparsest solution	2005	Y. Tsaig David L. Donoho
+	Condition numbers of random matrices	1991	Stanisław J. Szarek
+	Sparse Approximate Solutions to Linear Systems	1995	B. K. Natarajan
+	For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution	2006	David L. Donoho