Exponential bounds implying construction of compressed sensing matrices, errorcorrecting codes and neighborly polytopes by random sampling

Abstract. In [12] 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 ℓ1 minimization. They also proved an asymptotic rate the-orem, 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 ℓ1 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 prob-ability 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 [12] 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