Exponential Bounds Implying Construction of Compressed Sensing Matrices, Error-Correcting Codes, and Neighborly Polytopes by Random Sampling

2010/03/24 by David L. Donoho, Jared Tanner · 77 citations
Computer Science · Engineering · Mathematics · #Arithmetic #Combinatorics #Computer science #Discrete mathematics #Distributed Sensor Networks and Detection Algorithms #Emphasis (telecommunications) #Mathematics #Notation #Sparse and Compressive Sensing Techniques #Wireless Communication Security Techniques

paper · open access · doi:10.1109/tit.2010.2040892

published in IEEE Transactions on Information Theory 56(4), 2002-2016 (Institute of Electrical and Electronics Engineers)

openalex publication_date 2010/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

In“Counting faces of randomly projected polytopes when the projection radically lowers dimension”the authors proved an asymptoticsampling theorem for sparse signals, showing thatnrandom measurements permit to reconstruct anN-vector havingknonzeros providedn gt; 2 ⋅ k ⋅ log(N/n) (1+o(1))reconstruction usesℓ₁minimization. They also proved anasymptotic rate theorem, showing existence of real error-correcting codes for messages of lengthNwhich can correct all possiblek-element error patterns using justngeneralized checksum bits, wheren gt; 2e⋅ k log(N/n) (1 + o(1))decoding usesℓ₁minimization. Both results require an asymptotic framework, withNgrowing large. For applications, on the other hand, we are concerned with specific triplesk, n, N. We exhibit triples(k,n,N)for which Compressed Sensing Matrices and Real Error-Correcting Codes surely exist and can be obtained with high probability by random sampling. These derive from exponential bounds on the probability of drawing ‘bad’ matrices. The bounds give conditions effective at finite-N, and converging to the known sharp asymptotic conditions for largeN. Compared to other finite-Nbounds known to us, they are much stronger, and much more explicit. Our bounds derive from asymptotics in“Counting faces of randomly projected polytopes when the projection radically lowers dimension”counting the expected number ofk-dimensional faces of the randomly projected simplexT^N-1and cross-polytopeC^N. We develop here finite-Nbounds on the expected discrepancy between the number ofk-faces of the projected polytopeAQand its generatorQ, forQ=T^N-1andC^N. Our bounds also imply existence of interesting geometric objects. Thus, we exhibit triples(k,n,N)for which polytopes with2Nvertices can be centrallyk-neighborly.

Citations

• Compressed sensing

Cited by

• Least Squares Superposition Codes of Moderate Dictionary Size, Reliable at Rates up to Capacity
• Restricted Isometry Random Variables: Probability Distributions, RIC Prediction and Phase Transition Analysis for Gaussian Encoders
• Living on the edge: Phase transitions in convex programs with random data
• Phase Transition of Convex Programs for Linear Inverse Problems with Multiple Prior Constraints
• Compressed Sensing: How sharp is the Restricted Isometry Property
• Is "Compressed Sensing" compressive? Can it beat the Nyquist Sampling Approach?
• Sharp recovery bounds for convex demixing, with applications
• Sparsity/Undersampling Tradeoffs in Anisotropic Undersampling, with\n Applications in MR Imaging/Spectroscopy
• Reconstruction of Binary Functions and Shapes From Incomplete Frequency Information
• How little data is enough? Phase-diagram analysis of sparsity-regularized X-ray computed tomography. [europepmc]
• Compressed Sensing of Vibration Signal for Fault Diagnosis of Bearings, Gears, and Propellers Under Speed Variation Conditions. [europepmc]

Related

• Vanishingly Sparse Matrices and Expander Graphs, With Application to\n Compressed Sensing
• Sparse Coding and Autoencoders
• On construction and analysis of sparse random matrices and expander graphs with applications to compressed sensing
• Compressed Sensing with Sparse Binary Matrices: Instance Optimal Error Guarantees in Near-Optimal Time
• Compression is Comprehension, and the Unreasonable Effectiveness of Digital Computation in the Natural World