Paper Info
Title
Exponential bounds implying construction of compressed sensing matrices, error-correcting codes, and neighborly polytopes by random sampling
Abstract
In "Counting faces of randomly projected polytopes when the projection radically lowers dimension" the authors proved an asymptotic sampling theorem for sparse signals, showing that n random measurements permit to reconstruct an N-vector having k nonzeros provided n 2 ċ k ċ log(N/n)(1+o(1)) reconstruction uses l1 minimization. They also proved an asymptotic rate theorem, showing existence of real error-correcting codes for messages of length N which can correct all possible k-element error patterns using just n generalized checksum bits, where n 2e ċ k ċ log(N/n)(1+o(1)) decoding uses l1 minimization. Both results require an asymptotic framework, with N growing large. For applications, on the other hand, we are concerned with specific triples k, 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 large N. Compared to other finite-N bounds 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 of k-dimensional faces of the randomly projected simplex TN-1 and cross-polytope CN. We develop here finite-N bounds on the expected discrepancy between the number of k-faces of the projected polytope AQ and its generator Q, for Q = TN-1 and CN. Our bounds also imply existence of interesting geometric objects. Thus, we exhibit triples (k, n, N) for which polytopes with 2N vertices can be centrally k-neighborly.
Year
DOI
Venue
2010
10.1109/TIT.2010.2040892
IEEE Transactions on Information Theory
Keywords
Field
DocType
error correction codes,matrix algebra,probability,signal sampling,asymptotic rate theorem,compressed sensing matrices,error correcting codes,exponential bounds,random sampling probability,sampling theorem,sparse signals,$ell_1$-minimization,compressed sensing,error-correction by linear programming,neighborly polytopes,random matrices
Discrete mathematics,Combinatorics,Vertex (geometry),Matrix (mathematics),Simplex,Polytope,Expected value,Nyquist–Shannon sampling theorem,Asymptotic analysis,Mathematics,Random matrix
Journal
Volume
Issue
ISSN
56
4
0018-9448
Citations 
PageRank 
References 
24
2.72
9
Authors
2
Name
Order
Citations
PageRank
D. L. Donoho193501189.81
Jared Tanner252542.48