Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values

DOI10.1109/TSP.2011.2164913MaRDI QIDQ4573351zbMATH OpenFDO

Authors Gongguo Tang, Arye Nehorai

Publication date 18 July 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The stability of sparse signal reconstruction is investigated in this paper. We design efficient algorithms to verify the sufficient condition for unique $el{l}_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 $el{l}_1$-constrained minimal singular value ($el{l}_1$-CMSV) of the measurement matrix determines, in a very concise manner, the recovery performance of $el{l}_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 $el{l}_1$-CMSVs bounded away from zero, as long as the number of measurements is relatively large. To compute the $el{l}_1$-CMSV and its lower bound, we design two algorithms based on the interior point algorithm and the semi-definite relaxation.

Recommendations

• Sparse Recovery Conditions and Performance Bounds for $\ell _p$-Minimization
• On the Performance of Sparse Recovery Via \ell_p-Minimization (0 \leq p \leq 1)
• Performance Analysis for Sparse Support Recovery
• Minimization of L₁ over L₂ for sparse signal recovery with convergence guarantee
• Computable Performance Bounds on Sparse Recovery
• scientific article; zbMATH DE number 7750674
• On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
• Methods for sparse and low-rank recovery under simplex constraints
• Sparse recovery with integrality constraints
• Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants

Cited in

(9)

• On the sparsity of Lasso minimizers in sparse data recovery
• Compressive sensing using chaotic sequence based on Chebyshev map
• Stability analysis of a class of sparse optimization problems
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications
• Sparse recovery: the square of _1/_2 norms
• Computing proximity operators of scale and signed permutation invariant functions
• A note on sharp oracle bounds for Slope and Lasso
• An efficient proximal algorithm for squared L1 over L2 regularized sparse recovery

This page was built for publication: Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values

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