Greedy-Like Algorithms for the Cosparse Analysis Model

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 ${\ell }_1$ 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.

Cited by in corpus (22)

• Smoothing and Decomposition for Analysis Sparse Recovery
• Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
• Sparsity Averaging for Compressive Imaging
• ${\ell }^1$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
• Learning Model-Based Sparsity via Projected Gradient Descent
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints
• Robust analysis ${\ell }_1$-recovery from Gaussian measurements and total variation minimization
• Dimensionality reduction with subgaussian matrices: a unified theory
• Efficient Least Residual Greedy Algorithms for Sparse Recovery
• Generalizing CoSaMP to Signals from a Union of Low Dimensional Linear Subspaces
• Stochastic Greedy Algorithms For Multiple Measurement Vectors
• Analysis ${\ell }_1$-recovery with frames and Gaussian measurements
• Generalized Approximate Message Passing for Cosparse Analysis Compressive Sensing
• Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries
• Projection onto the Cosparse Set is NP-Hard
• Generalized Inpainting Method for Hyperspectral Image Acquisition
• Can we allow linear dependencies in the dictionary in the sparse synthesis framework?
• On sparsity averaging
• A Nonconvex Approach for Structured Sparse Learning
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Unified Theory for Recovery of Sparse Signals in a General Transform Domain
• Online and Stable Learning of Analysis Operators