Error Correction via Linear Programming

Suppose we wish to transmit a vector f ϵ R n reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?

Authors

• Emmanuel J. Candès
• Mark Rudelson
• Terence Tao
• Roman Vershynin

Keywords

• Error correction
• Linear programming
• Linear code
• Vectors
• Mathematics
• Error correction codes
• Encoding
• Particle measurements
• Functional analysis
• Decoding
• Positive Constant
• Minimization Problem
• Convex Optimization
• Measurement Matrix
• Convex Polytope
• Coding Matrix
• Unit Cube
• Column Vector
• Encryption
• Functional Class
• Plaintext
• Small Class
• Linear Measurements
• Type Of Matrix
• Random Matrix
• Forward Error Correction
• Finite Field
• Solid Spheres
• Random Subspace
• Gaussian Measurement
• Gaussian Matrix
• Basis Pursuit
• Restricted Isometry
• Restricted Isometry Property
• Breakpoint Locations
• Grassmannian
• Coding Theory
• Statistical Learning Theory