Exponential Bounds Implying Construction of Compressed Sensing Matrices, Error-Correcting Codes, and Neighborly Polytopes by Random Sampling
Authors
Discussion
Loading...
Member takes
Implication
Theoretical analysis derives finite-sample exponential bounds for compressed sensing matrices and error-correcting codes, enabling explicit construction via random sampling.
Key Points
- Establish explicit, non-asymptotic exponential probability bounds guaranteeing the successful construction of compressed sensing matrices, error-correcting codes, and neighborly polytopes at finite dimensions.
- Evaluated the expected discrepancy between the number of k-dimensional faces of generator polytopes (the simplex T^(N-1) and cross-polytope C^N) and their randomly projected counterparts AQ.
- Derived non-asymptotic exponential bounds on the probability of sampling invalid measurement matrices for specific parameter triples (k, n, N) under l1 minimization.
- Derived explicit finite-N probability bounds that converge directly to sharp asymptotic thresholds (n > 2k log(N/n) for sparse signal recovery and n > 2e k log(N/n) for error correction).
- Proved that valid compressed sensing matrices, real error-correcting codes, and centrally k-neighborly polytopes with 2N vertices can be generated with high probability through random sampling.
Cite This Study
Donoho et al. (2010) studied this question.