Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery

Abstract

The most frequently used condition for sampling matrices employed in compressive sampling is the restricted isometry (RIP) property of the matrix when restricted to sparse signals. At the same time, imposing this condition makes it difficult to find explicit matrices that support recovery of signals from sketches of the optimal (smallest possible)dimension. A number of attempts have been made to relax or replace the RIP property in sparse recovery algorithms. We focus on the relaxation under which the near-isometry property holds for most rather than for all submatrices of the sampling matrix, known as statistical RIP or StRIP condition. We show that sampling matrices of dimensions $m\times N$ with maximum coherence $\mu =O((k{\log }^{3}N{)}^{-1/4})$ and mean square coherence ${\bar{\mu }}^2=O(1/(k\log N))$ support stable recovery of $k$-sparse signals using Basis Pursuit. These assumptions are satisfied in many examples. As a result, we are able to construct sampling matrices that support recovery with low error for sparsity $k$ higher than $\sqrt{m},$ which exceeds the range of parameters of the known classes of RIP matrices.

References in corpus (5)

• Sparsity and Incoherence in Compressive Sampling
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Two are better than one: Fundamental parameters of frame coherence
• The road to deterministic matrices with the restricted isometry property
• Statistical RIP and Semi-Circle Distribution of Incoherent Dictionaries