|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Decoding by Linear Programming | | Emmanuel Candes
; Terence Tao
; | | Date: |
15 Feb 2005 | | Subject: | Metric Geometry; Cryptography and Security MSC-class: 94B05 | math.MG cs.CR | | Abstract: | 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
eq 0}| le
ho cdot m$ 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. | | Source: | arXiv, math.MG/0502327 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER