Greedy-like algorithms for the cosparse analysis model
From MaRDI portal
Publication:2437331
DOI10.1016/J.LAA.2013.03.004zbMATH Open1332.94043arXiv1207.2456OpenAlexW2107059427MaRDI QIDQ2437331FDOQ2437331
Publication date: 3 March 2014
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: The cosparse analysis model has been introduced recently as an interesting alternative to the standard sparse synthesis approach. A prominent question brought up by this new construction is the analysis pursuit problem -- the need to find a signal belonging to this model, given a set of corrupted measurements of it. Several pursuit methods have already been proposed based on relaxation and a greedy approach. In this work we pursue this question further, and propose a new family of pursuit algorithms for the cosparse analysis model, mimicking the greedy-like methods -- compressive sampling matching pursuit (CoSaMP), subspace pursuit (SP), iterative hard thresholding (IHT) and hard thresholding pursuit (HTP). Assuming the availability of a near optimal projection scheme that finds the nearest cosparse subspace to any vector, we provide performance guarantees for these algorithms. Our theoretical study relies on a restricted isometry property adapted to the context of the cosparse analysis model. We explore empirically the performance of these algorithms by adopting a plain thresholding projection, demonstrating their good performance.
Full work available at URL: https://arxiv.org/abs/1207.2456
Recommendations
- A modified greedy analysis pursuit algorithm for the cosparse analysis model
- The cosparse analysis model and algorithms
- Phase transitions for greedy sparse approximation algorithms
- Near oracle performance and block analysis of signal space greedy methods
- \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
synthesiscompressed sensingiterative hard thresholdinganalysissparse representationsCoSaMPhard thresholding pursuitsubspace-pursuit
Estimation in multivariate analysis (62H12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)
Cites Work
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Sparsity and Smoothness Via the Fused Lasso
- Matching pursuits with time-frequency dictionaries
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- A simple proof of the restricted isometry property for random matrices
- Iterative hard thresholding for compressed sensing
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Sparse Recovery With Orthogonal Matching Pursuit Under RIP
- Adaptive greedy approximations
- Iteratively reweighted least squares minimization for sparse recovery
- Sparse representations in unions of bases
- The restricted isometry property and its implications for compressed sensing
- Uniform uncertainty principle for Bernoulli and subgaussian ensembles
- The cosparse analysis model and algorithms
- Performance Guarantees of the Thresholding Algorithm for the Cosparse Analysis Model
- Compressed Sensing and Redundant Dictionaries
- Analysis versus synthesis in signal priors
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Matrix recipes for hard thresholding methods
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Non-asymptotic theory of random matrices: extreme singular values
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- Compressed sensing with coherent and redundant dictionaries
- Hard Thresholding Pursuit: An Algorithm for Compressive Sensing
- New bounds on the restricted isometry constant \(\delta _{2k}\)
- Sparse Recovery Algorithms: Sufficient Conditions in Terms of Restricted Isometry Constants
- A Theory for Sampling Signals From a Union of Subspaces
- Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
- Robust Sparse Analysis Regularization
- Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model
- RIP-Based Near-Oracle Performance Guarantees for SP, CoSaMP, and IHT
Cited In (23)
- Analysis sparse representation for nonnegative signals based on determinant measure by DC programming
- Dimensionality reduction with subgaussian matrices: a unified theory
- Compressive Sensing in Acoustic Imaging
- Compressive Sensing with Redundant Dictionaries and Structured Measurements
- Near oracle performance and block analysis of signal space greedy methods
- TWO NEW LOWER BOUNDS FOR THE SPARK OF A MATRIX
- Robust analysis ℓ1-recovery from Gaussian measurements and total variation minimization
- Stochastic greedy algorithms for multiple measurement vectors
- Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
- Convergence analysis on the alternating direction method of multipliers for the cosparse optimization problem
- Sparsity Based Methods for Overparameterized Variational Problems
- Cosparsity in Compressed Sensing
- Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
- Multi-Layer Sparse Coding: The Holistic Way
- Sampling in the analysis transform domain
- Structured overcomplete sparsifying transform learning with convergence guarantees and applications
- \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
- 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
- Convergence on thresholding-based algorithms for dictionary-sparse recovery
- A modified greedy analysis pursuit algorithm for the cosparse analysis model
- Greedy signal space methods for incoherence and beyond
Uses Software
This page was built for publication: Greedy-like algorithms for the cosparse analysis model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437331)
