Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2013 | public
Journal Article Open

The restricted isometry property for time-frequency structured random matrices


This paper establishes the restricted isometry property for a Gabor system generated by n^2 time–frequency shifts of a random window function in n dimensions. The sth order restricted isometry constant of the associated n × n^2 Gabor synthesis matrix is small provided that s ≤ cn^(2/3) / log^2 n. This bound provides a qualitative improvement over previous estimates, which achieve only quadratic scaling of the sparsity s with respect to n. The proof depends on an estimate for the expected supremum of a second-order chaos.

Additional Information

© 2012 Springer-Verlag. Received: 16 June 2011; Revised: 21 May 2012; Accepted: 5 June 2012; Published online: 26 June 2012. Götz E. Pfander appreciates the support by the Deutsche Forschungsgemeinschaft (DFG) under grant 50292 DFG PF-4 Sampling Operators. Holger Rauhut acknowledges generous support by the Hausdorff Center for Mathematics, and funding by the Starting Independent Researcher Grant StG-2010 258926-SPALORA from the European Research Council (ERC). Joel A. Tropp was supported in part by the Defense Advanced Research Projects Agency (DARPA) and the Office of Naval Research (ONR) under Grants N66001-06-1-2011 and N66001-08-1-2065.

Attached Files

Submitted - 1106.3184v1.pdf


Files (350.5 kB)
Name Size Download all
350.5 kB Preview Download

Additional details

August 22, 2023
August 22, 2023