Decoding by Linear Programming

2005/02/15 by Emmanuel Candes, Terence Tao, Candes, Emmanuel +1 · 45 citations
Computer Science · Mathematics · #94B05 #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #cs.CR #math.MG #msc:94B05

paper · pdf · doi:10.48550/arxiv.math/0502327

22 pages, 4 figures, submitted

arxiv created 2005/02/15 · arxiv updated 2009/12/01

Abstract

This paper considers the classical error correcting problem which is frequently discussed in coding theory. We wish to recover an input vector f ∈ \Rⁿ 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 ℓ₁-minimization problem (‖x‖_ℓ1 := ∑_i |x_i|) min_{g ∈ \Rⁿ} ‖ y - Ag ‖_ℓ1 provided that the support of the vector of errors is not too large, ‖e‖_ℓ0 := |\i : e_i ≠ 0\| ≤ ρ⋅ m for some ρ> 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.

Cited by

• Near-Optimal Coalition Structures in Polynomial Time
• Weighted Group Lasso for a static EEG problem
• Unlocking the Address Book: Dissecting the Sparse Semantic Structure of LLM Key-Value Caches via Sparse Autoencoders
• A Novel Pilot Scheme for Uplink Channel Estimation for Sub-array Structured ELAA in XL-MIMO systems
• Numerical optimization for the compatibility constant of the lasso
• Weight Variance Amplifier Improves Accuracy in High-Sparsity One-Shot Pruning
• Cross-Layer Design for Near-Field mmWave Beam Management and Scheduling under Delay-Sensitive Traffic
• Optimization landscape of ℓ₀-Bregman relaxations
• Compressive Sensing Photoacoustic Imaging Receiver with Matrix-Vector-Multiplication SAR ADC
• Sparse Linear Regression is Easy on Random Supports
• Upper bounds for the L^q empirical process via generic chaining
• Geometric Data Valuation via Leverage Scores
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
• The Scaling Properties of Implicit Deductive Reasoning in Transformers
• Is Dimensionality a Barrier for Retrieval Models?
• Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery
• ℓ₂/ℓ₂ Sparse Recovery via Weighted Hypergraph Peeling
• CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing
• Survival of the fittest Cox model: Pivotal variable selection for time-to-event data
• A Dimension-Keeping Semi-Tensor Product Framework for Compressed Sensing
• Approximate Proximal Operators for Analog Compressed Sensing Using PN-junction Diode
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation
• Rethinking the shape convention of an MLP
• Structurally informed data assimilation in two dimensions
• Overshifted Parameter-Shift Rules: Optimizing Complex Quantum Systems with Few Measurements
• Compressed Newton-direction-based Thresholding Methods for Sparse Optimization Problems
• Optimality and computational barriers in variable selection under dependence
• Splitting Alternating Algorithms for Sparse Solutions of Linear Systems with Concatenated Orthogonal Matrices
• Towards Atoms of Large Language Models
• Improved RIP Bounds for Gaussian Partial Circulant Matrices
• Joint Pilot Allocation and Sequence Design for MIMO-OFDM Systems With Channel Sparsity
• Towards Interpretable and Efficient Attention: Compressing All by Contracting a Few
• Bridging Batch and Streaming Estimations to System Identification under Adversarial Attacks
• Polynomial Optimization via Random Projection and Consensus
• Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance
• Comparison between Supervised and Unsupervised Learning in Deep Unfolded Sparse Signal Recovery
• Functional Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem
• A James-Stein Estimator based Generalized OMP Algorithm for Robust Signal Recovery using Sparse Representation
• Stoch-IDENT: New Method and Mathematical Analysis for Identifying SPDEs from Data
• Basis pursuit by inconsistent alternating projections
• Nearly optimal bounds on the Fourier sampling numbers of Besov spaces
• Dynamic Rank Adjustment for Accurate and Efficient Neural Network Training
• How Diffusion Prior Landscapes Shape the Posterior in Blind Deconvolution
• Resilient State Recovery using Prior Measurement Support Information

Related

• The Limits of Error Correction with lp Decoding
• Introduction to Mathematical Programming-Based Error-Correction Decoding
• Highly robust error correction by convex programming
• Error-correction of linear codes via colon ideals
• Data recovery from corrupted observations via l1 minimization