Decoding by Linear Programming

MaRDI QIDQ6475112arXivFDO

Authors Emmanuel Candes, Terence Tao

Publication date 15 February 2005

Published in arXiv

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

arXiv classification

cs.CRmath.MG

Abstract: This paper considers the classical error correcting problem which is frequently discussed in coding theory. We wish to recover an input vector $fin{R}^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 $el{l}_1$-minimization problem ($|x{|}_{el{l}_1}:=su{m}_i|x_i|$) ${\displaystyle }$ min_{g in R^n} | y - Ag |_{ell_1} ${\displaystyle }$ provided that the support of the vector of errors is not too large, $|e{|}_{el{l}_0}:=|i:e_{i}eq0|lehocdotm$ for some $ho>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.

Cited in

(2)

• Compressed Sensing with Quantized Tensor Trains (QTTs)
• Instability of Gaussian elimination is exponentially rare (proof of partial result)

This page was built for publication: Decoding by Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6475112)