The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries

Abstract

In this article we present a statistical version of the Candes-Tao restricted isometry property (SRIP for short) which holds in general for any incoherent dictionary which is a disjoint union of orthonormal bases. In addition, we show that, under appropriate normalization, the eigenvalues of the associated Gram matrix fluctuate around 1 according to the Wigner semicircle distribution. The result is then applied to various dictionaries that arise naturally in the setting of finite harmonic analysis, giving, in particular, a better understanding on a remark of Applebaum-Howard-Searle-Calderbank concerning RIP for the Heisenberg dictionary of chirp like functions.

Submitted for The 2009 IEEE International Symposium on Information Theory; Key words: Compressive sensing, Stastical version of Candes-Tao RIP, Incoherent Dictionaries, Semicircle distribution

References in corpus (4)

• Efficient and Robust Compressed Sensing using High-Quality Expander Graphs
• Deterministic Designs with Deterministic Guarantees: Toeplitz Compressed Sensing Matrices, Sequence Designs and System Identification
• The finite harmonic oscillator and its associated sequences
• Incoherent dictionaries and the statistical restricted isometry property

Cited by in corpus (6)

• Sparse approximation property and stable recovery of sparse signals from noisy measurements
• Random Subsets of Structured Deterministic Frames have MANOVA Spectra
• Near-optimal Binary Compressed Sensing Matrix
• Deterministic Sampling of Sparse Trigonometric Polynomials
• Orthogonal symmetric Toeplitz matrices for compressed sensing: Statistical isometry property
• Turbo Analog Error Correcting Codes Decodable By Linear Programming