Sparse Signal Reconstruction via Iterative Support Detection

Abstract

We present a novel sparse signal reconstruction method "ISD", aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the classical l_1 minimization approach. ISD addresses failed reconstructions of l_1 minimization due to insufficient measurements. It estimates a support set I from a current reconstruction and obtains a new reconstruction by solving the minimization problem \min{\sum_{i\not\in I}|x_i|:Ax=b}, and it iterates these two steps for a small number of times. ISD differs from the orthogonal matching pursuit (OMP) method, as well as its variants, because (i) the index set I in ISD is not necessarily nested or increasing and (ii) the minimization problem above updates all the components of x at the same time. We generalize the Null Space Property to Truncated Null Space Property and present our analysis of ISD based on the latter. We introduce an efficient implementation of ISD, called threshold--ISD, for recovering signals with fast decaying distributions of nonzeros from compressive sensing measurements. Numerical experiments show that threshold--ISD has significant advantages over the classical l_1 minimization approach, as well as two state--of--the--art algorithms: the iterative reweighted l_1 minimization algorithm (IRL1) and the iterative reweighted least--squares algorithm (IRLS). MATLAB code is available for download from http://www.caam.rice.edu/~optimization/L1/ISD/.

References in corpus (1)

• Sparsity and Incoherence in Compressive Sampling

Cited by in corpus (27)

• Sparse Signal Estimation by Maximally Sparse Convex Optimization
• Exploiting Prior Knowledge in Compressed Sensing Wireless ECG Systems
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Enhanced Sparsity by Non-Separable Regularization
• MAP Support Detection for Greedy Sparse Signal Recovery Algorithms in Compressive Sensing
• ReProCS: A Missing Link between Recursive Robust PCA and Recursive Sparse Recovery in Large but Correlated Noise
• Triangulated Surface Denoising using High Order Regularization with Dynamic Weights
• Nonconvex Sorted ${\ell }_1$ Minimization for Sparse Approximation
• Improving A*OMP: Theoretical and Empirical Analyses With a Novel Dynamic Cost Model
• Quantitative Group Testing and the rank of random matrices
• Exact Reconstruction Conditions for Regularized Modified Basis Pursuit
• Edge-adaptive l2 regularization image reconstruction from non-uniform Fourier data
• Exact penalty decomposition method for zero-norm minimization based on MPEC formulation
• Recoverability Analysis for Modified Compressive Sensing with Partially Known Support
• Active User Detection of Uplink Grant-Free SCMA in Frequency Selective Channel
• Spatially correlated channel estimation based on block iterative support detection for large-scale MIMO
• Enhanced joint sparsity via Iterative Support Detection
• Truncated Nuclear Norm Minimization for Image Restoration Based On Iterative Support Detection
• On Collaborative Compressive Sensing Systems: The Framework, Design and Algorithm
• Linear Spatial Pyramid Matching Using Non-convex and non-negative Sparse Coding for Image Classification
• Truncated Sparse Approximation Property and Truncated $q$-Norm Minimization
• Time Invariant Error Bounds for Modified-CS based Sparse Signal Sequence Recovery
• Universally Elevating the Phase Transition Performance of Compressed Sensing: Non-Isometric Matrices are Not Necessarily Bad Matrices
• Spark Level Sparsity and the ${\ell }_1$ Tail Minimization
• Support Recovery with Stochastic Gates: Theory and Application for Linear Models
• Iterative ${\ell }_1$ minimization for non-convex compressed sensing
• Exact Recovery Conditions for Sparse Representations with Partial Support Information