Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries

DOI10.1109/TIT.2013.2273491zbMATH Open1364.94119arXiv1208.0353OpenAlexW2077520262MaRDI QIDQ5346325FDOQ5346325

D. Needell, Michael B. Wakin, Mark A. Davenport

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper we describe a variant of the iterative recovery algorithm CoSaMP for this more challenging setting. We utilize the D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are "signal-focused"; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. Developing a practical algorithm that can provably compute the required near-optimal projections remains a significant open problem, but we include simulation results using various heuristics that empirically exhibit superior performance to traditional recovery algorithms.

Full work available at URL: https://arxiv.org/abs/1208.0353

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (18)

• Greedy approximate projection for magnetic resonance fingerprinting with partial volumes
• Estimation in High Dimensions: A Geometric Perspective
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A geometrical stability condition for compressed sensing
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• Near oracle performance and block analysis of signal space greedy methods
• Flavors of Compressive Sensing
• Sparsity Based Methods for Overparameterized Variational Problems
• Data-driven algorithm selection and tuning in optimization and signal processing
• Sampling in the analysis transform domain
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Dictionary-sparse recovery via thresholding-based algorithms
• Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
• Sampling rates for \(\ell^1\)-synthesis
• Estimating Sparse Signals Using Integrated Wideband Dictionaries
• Arbitrary block-sparse signal reconstruction based on incomplete single measurement vector
• Convergence on thresholding-based algorithms for dictionary-sparse recovery
• Greedy signal space methods for incoherence and beyond

Uses Software

• CoSaMP

This page was built for publication: Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346325)