The restricted isometry property for random block diagonal matrices

Armin Eftekhari, Han Lun Yap, Christopher J. Rozell, Michael B. Wakin

Research output: Contribution to journalArticlepeer-review

Abstract

In Compressive Sensing, the Restricted Isometry Property (RIP) ensures that robust recovery of sparse vectors is possible from noisy, undersampled measurements via computationally tractable algorithms. It is by now well-known that Gaussian (or, more generally, sub-Gaussian) random matrices satisfy the RIP under certain conditions on the number of measurements. Their use can be limited in practice, however, due to storage limitations, computational considerations, or the mismatch of such matrices with certain measurement architectures. These issues have recently motivated considerable effort towards studying the RIP for structured random matrices. In this paper, we study the RIP for block diagonal measurement matrices where each block on the main diagonal is itself a sub-Gaussian random matrix. Our main result states that such matrices can indeed satisfy the RIP but that the requisite number of measurements depends on certain properties of the basis in which the signals are sparse. In the best case, these matrices perform nearly as well as dense Gaussian random matrices, despite having many fewer nonzero entries.
Original languageEnglish
Pages (from-to)1-31
Number of pages31
JournalApplied and Computational Harmonic Analysis
Volume38
Issue number1
Early online date15 Feb 2014
DOIs
Publication statusPublished - 1 Jan 2015

Fingerprint Dive into the research topics of 'The restricted isometry property for random block diagonal matrices'. Together they form a unique fingerprint.

Cite this