Suprema of Chaos Processes and the Restricted Isometry Property

Abstract

We present a new bound for suprema of a special type of chaos processes indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time-frequency structured random matrices. In both cases the required condition on the number $m$ of rows in terms of the sparsity $s$ and the vector length $n$ is $m\gtrsim s{\log }^{2}s{\log }^{2}n$.

revised version, accepted for publication in Communications on Pure and Applied Mathematics, a number of typos removed

References in corpus (2)

• The restricted isometry property for time-frequency structured random matrices
• Restricted Isometries for Partial Random Circulant Matrices

Cited by in corpus (6)

• Noncommutative Bennett and Rosenthal inequalities
• Coded Acquisition of High Frame Rate Video
• Concentration of Measure Inequalities for Toeplitz Matrices with Applications
• New bounds for circulant Johnson-Lindenstrauss embeddings
• New Analysis of Manifold Embeddings and Signal Recovery from Compressive Measurements
• Short Term Memory Capacity in Networks via the Restricted Isometry Property