Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values

Abstract

The stability of sparse signal reconstruction is investigated in this paper. We design efficient algorithms to verify the sufficient condition for unique ${\ell }_1$ sparse recovery. One of our algorithm produces comparable results with the state-of-the-art technique and performs orders of magnitude faster. We show that the ${\ell }_1$-constrained minimal singular value (${\ell }_1$-CMSV) of the measurement matrix determines, in a very concise manner, the recovery performance of ${\ell }_1$-based algorithms such as the Basis Pursuit, the Dantzig selector, and the LASSO estimator. Compared with performance analysis involving the Restricted Isometry Constant, the arguments in this paper are much less complicated and provide more intuition on the stability of sparse signal recovery. We show also that, with high probability, the subgaussian ensemble generates measurement matrices with ${\ell }_1$-CMSVs bounded away from zero, as long as the number of measurements is relatively large. To compute the ${\ell }_1$-CMSV and its lower bound, we design two algorithms based on the interior point algorithm and the semi-definite relaxation.

References in corpus (4)

• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• Sparse Volterra and Polynomial Regression Models: Recoverability and Estimation
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (14)

• Unknown sparsity in compressed sensing: Denoising and inference
• Estimating Unknown Sparsity in Compressed Sensing
• Signal Recovery in Unions of Subspaces with Applications to Compressive Imaging
• Enhanced block sparse signal recovery based on $q$-ratio block constrained minimal singular values
• Minimization of the $q$-ratio sparsity with $1<q\le \infty$ for signal recovery
• Recovery of Signals with Low Density
• Sparse recovery based on q-ratio constrained minimal singular values
• On $q$-ratio CMSV for sparse recovery
• The Stability of Low-Rank Matrix Reconstruction: a Constrained Singular Value View
• Stability Analysis for a Class of Sparse Optimization Problems
• A note on sharp oracle bounds for Slope and Lasso
• Solve-Select-Scale: A Three Step Process For Sparse Signal Estimation
• Multi-Structural Signal Recovery for Biomedical Compressive Sensing
• Compressed Sensing Recoverability In Imaging Modalities