The restricted isometry property for time-frequency structured random matrices

Abstract

We establish the restricted isometry property for finite dimensional Gabor systems, that is, for families of time--frequency shifts of a randomly chosen window function. We show that the $s$-th order restricted isometry constant of the associated $n\times n^2$ Gabor synthesis matrix is small provided $s\le c{n}^{2/3}/{\log }^{2}n$. This improves on previous estimates that exhibit quadratic scaling of $n$ in $s$. Our proof develops bounds for a corresponding chaos process.

25 pages

References in corpus (2)

• Identification of Matrices having a Sparse Representation
• The Gelfand widths of ${\ell }_p$-balls for $0<p\le 1$

Cited by in corpus (14)

• Measure What Should be Measured: Progress and Challenges in Compressive Sensing
• RSP-Based Analysis for Sparsest and Least ${\ell }_1$-Norm Solutions to Underdetermined Linear Systems
• Polynomial Fourier Domain as a Domain of Signal Sparsity
• The Faber-Krahn inequality for the Short-time Fourier transform
• Quasi-Linear Compressed Sensing
• Suprema of Chaos Processes and the Restricted Isometry Property
• Random Subsets of Structured Deterministic Frames have MANOVA Spectra
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• Symmetric Toeplitz-Structured Compressed Sensing Matrices
• Compressed Sensing Based on Random Symmetric Bernoulli Matrix
• Nonlinear approximation with nonstationary Gabor frames
• Preconditioning filter bank decompositions using structured normalized tight frames
• Mixed Compressed Sensing Based on Random Graphs
• Analog Coding Frame-work