November 22, 2005IEEE Transactions on Information Theory
Decoding by Linear Programming
Authors
Discussion
Loading...
Member takes
Implication
Theoretical analysis demonstrates exact signal recovery from corrupted measurements via linear programming, indicating robust error-correction capabilities for sparse corruptions.
Key Points
- To determine whether an unknown real-valued input vector can be exactly reconstructed from corrupted linear measurements using convex optimization.
- Formulated the real-valued error-correction problem as an l1-norm minimization task solvable via linear programming.
- Established mathematical recovery guarantees by characterizing coding matrices under the uniform uncertainty principle.
- Conducted numerical simulation experiments to evaluate signal recovery across varying fractions of corrupted measurements.
- Proved that the original input vector is the unique exact solution to the l1-minimization problem when error support is bounded to a fraction of measurements (||e||_0 <= rho * m).
- Demonstrated numerically that exact signal recovery succeeds reliably even when a substantial proportion of measurements are corrupted.
Cite This Study
Candès et al. (2005) studied this question.