Block-length dependent thresholds in block-sparse compressed sensing

Abstract

One of the most basic problems in compressed sensing is solving an under-determined system of linear equations. Although this problem seems rather hard certain ${\ell }_1$-optimization algorithm appears to be very successful in solving it. The recent work of \cite{CRT,DonohoPol} rigorously proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that ${\ell }_1$-optimization algorithm succeeds in solving the system. In more recent papers \cite{StojnicICASSP09block,StojnicJSTSP09} we considered the setup of the so-called \textbf{block}-sparse unknown vectors. In a large dimensional and statistical context, we determined sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations such that an ${\ell }_2/{\ell }_1$-optimization algorithm succeeds in solving the system. The results established in \cite{StojnicICASSP09block,StojnicJSTSP09} assumed a fairly large block-length of the block-sparse vectors. In this paper we consider the block-length to be a parameter of the system. Consequently, we then establish sharp lower bounds on the values of the allowable block-sparsity as functions of the block-length.

References in corpus (15)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
• Joint-sparse recovery from multiple measurements
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
• On Verifiable Sufficient Conditions for Sparse Signal Recovery via ${\ell }_1$ Minimization
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Weighted ${\ell }_1$ Minimization for Sparse Recovery with Prior Information
• Sparse Recovery of Positive Signals with Minimal Expansion
• Breaking through the Thresholds: an Analysis for Iterative Reweighted ${\ell }_1$ Minimization via the Grassmann Angle Framework
• Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
• Simultaneous support recovery in high dimensions: Benefits and perils of block ${\ell }_1/{\ell }_{\infty }$-regularization

Cited by in corpus (17)

• C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
• On Phase Transition of Compressed Sensing in the Complex Domain
• Sharp MSE Bounds for Proximal Denoising
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
• Meshes that trap random subspaces
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals
• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• Minimum Complexity Pursuit: Stability Analysis
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds
• Compressed sensing of block-sparse positive vectors
• Towards a better compressed sensing
• Asymmetric Little model and its ground state energies
• From compression to compressed sensing
• Low noise sensitivity analysis of Lq-minimization in oversampled systems
• A problem dependent analysis of SOCP algorithms in noisy compressed sensing