Decoding by Linear Programming
| dc.creator | Candes, Emmanuel | |
| dc.creator | Tao, Terence | |
| dc.date | 2005-02-15 | |
| dc.date.accessioned | 2026-07-07T05:17:03Z | |
| dc.date.available | 2026-07-07T05:17:03Z | |
| dc.description | This paper considers the classical error correcting problem which is frequently discussed in coding theory. We wish to recover an input vector $f \in \R^n$ from corrupted measurements $y = A f + 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 $\ell_1$-minimization problem ($\|x\|_{\ell_1} := \sum_i |x_i|$) $$ \min_{g \in \R^n} \| y - Ag \|_{\ell_1} $$ provided that the support of the vector of errors is not too large, $\|e\|_{\ell_0} := |\{i : e_i \neq 0\}| \le ρ\cdot m$ for some $ρ> 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. | |
| dc.description | 22 pages, 4 figures, submitted | |
| dc.identifier | https://arxiv.org/abs/math/0502327 | |
| dc.identifier | http://arxiv.org/abs/math/0502327 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74215 | |
| dc.subject | Metric Geometry | |
| dc.subject | Cryptography and Security | |
| dc.subject | 94B05 | |
| dc.title | Decoding by Linear Programming | |
| dc.type | text |