The restricted isometry property for time-frequency structured random matrices

Abstract

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

Additional details