The restricted isometry property for time-frequency structured random matrices

• 成果类型: Article
• 署名作者: Pfander, Goetz E.; Rauhut, Holger; Tropp, Joel A.
• 署名单位: Constructor University; University of Bonn; California Institute of Technology
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-012-0441-4
• 发表日期: 2013
• 页码: 707-737
• 关键词: Concentration Inequalities; signal recovery; SPARSE; reconstruction; uncertainty

摘要

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 x n (2) Gabor synthesis matrix is small provided that s a parts per thousand currency sign c n (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.