Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class

Abstract

In compressed sensing, it is often desirable to consider signals possessing additional structure beyond sparsity. One such structured signal model - which forms the focus of this paper - is the local sparsity in levels class. This class has recently found applications in problems such as compressive imaging, multi-sensor acquisition systems and sparse regularization in inverse problems. In this paper we present uniform recovery guarantees for this class when the measurement matrix corresponds to a subsampled isometry. We do this by establishing a variant of the standard restricted isometry property for sparse in levels vectors, known as the restricted isometry property in levels. Interestingly, besides the usual log factors, our uniform recovery guarantees are simpler and less stringent than existing nonuniform recovery guarantees. For the particular case of discrete Fourier sampling with Haar wavelet sparsity, a corollary of our main theorem yields a new recovery guarantee which improves over the current state-of-the-art.

References in corpus (15)

• Sparsity and Incoherence in Compressive Sampling
• Structured Compressed Sensing: From Theory to Applications
• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
• Compressed Sensing and Parallel Acquisition
• On asymptotic structure in compressed sensing
• Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
• Interpolation via weighted $l_1$ minimization
• On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels
• Uniform Recovery from Subgaussian Multi-Sensor Measurements
• Optimal Sparse Recovery for Multi-Sensor Measurements
• A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements
• Compressed sensing with structured sparsity and structured acquisition
• Sparsity and Parallel Acquisition: Optimal Uniform and Nonuniform Recovery Guarantees

Cited by in corpus (2)

• Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
• Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements