Decoding by Linear Programming

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 {\mathbb{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 ${\ell }_1$-minimization problem ($\Vert x{\Vert }_{{\ell }_1}:={\sum }_i|x_i|$) $$\underset{g\in {\mathbb{R}}^n}{\min }\Vert y-Ag{\Vert }_{{\ell }_1}$$ provided that the support of the vector of errors is not too large, $\Vert e{\Vert }_{{\ell }_0}:=|\{i:e_i\ne 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.

22 pages, 4 figures, submitted

Cited by in corpus (14)

• The Kadison-Singer Problem in Mathematics and Engineering
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
• Reconstruction and subgaussian operators
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints
• The necessity and power of random, under-sampled experiments in biology
• On sparse interpolation and the design of deterministic interpolation points
• Direct l_(2,p)-Norm Learning for Feature Selection
• Link Prediction in Graphs with Autoregressive Features
• A null space analysis of the L1 synthesis method in dictionary-based compressed sensing
• Can we allow linear dependencies in the dictionary in the sparse synthesis framework?
• Relaxed Sparse Eigenvalue Conditions for Sparse Estimation via Non-convex Regularized Regression
• Model Identification of a Network as Compressing Sensing
• Keep the phase! Signal recovery in phase-only compressive sensing