Decoding by Linear Programming

Details Decoding by Linear Programming Decoding by Linear Programming

2005-02-15

arxiv.org/abs/math/0502327v1

Mathematics

Metric Geometry

22 pages, 4 figures, submitted

Scientific paper

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 \rho \cdot m$ for some $\rho > 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.

Affiliated with

Also associated with

No associations

Rating

Decoding by Linear Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decoding by Linear Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding by Linear Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-84008