Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery

Abstract

We consider compressed sensing of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. An uncertainty relation for block-sparse signals is derived, based on a block-coherence measure, which we introduce. We then show that a block-version of the orthogonal matching pursuit algorithm recovers block $k$-sparse signals in no more than $k$ steps if the block-coherence is sufficiently small. The same condition on block-coherence is shown to guarantee successful recovery through a mixed ${\ell }_2/{\ell }_1$-optimization approach. This complements previous recovery results for the block-sparse case which relied on small block-restricted isometry constants. The significance of the results presented in this paper lies in the fact that making explicit use of block-sparsity can provably yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.

Submitted to the IEEE Trans. on Signal Processing, version 2 has updated figures

References in corpus (5)

• Consistency of the group Lasso and multiple kernel learning
• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
• Time Delay Estimation from Low Rate Samples: A Union of Subspaces Approach
• The Benefit of Group Sparsity
• Xampling: Analog to Digital at Sub-Nyquist Rates

Cited by in corpus (114)

• Structured Compressed Sensing: From Theory to Applications
• Sparse Signal Recovery with Temporally Correlated Source Vectors Using Sparse Bayesian Learning
• Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation
• Position and Orientation Estimation through Millimeter Wave MIMO in 5G Systems
• DR2-Net: Deep Residual Reconstruction Network for Image Compressive Sensing
• Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG via Block Sparse Bayesian Learning
• Xampling: Signal Acquisition and Processing in Union of Subspaces
• Sparse Representation for Wireless Communications: A Compressive Sensing Approach
• C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
• Joint Sparse Recovery Method for Compressed Sensing with Structured Dictionary Mismatches
• Model-free inference of direct network interactions from nonlinear collective dynamics
• Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation
• Block-Sparse Recovery via Convex Optimization
• Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery
• Measure What Should be Measured: Progress and Challenges in Compressive Sensing
• A Majorize-Minimize subspace approach for l2-l0 image regularization
• Two-Dimensional Pattern-Coupled Sparse Bayesian Learning via Generalized Approximate Message Passing
• Funnel-Structured Cascade for Multi-View Face Detection with Alignment-Awareness
• Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
• Intelligent Meta-Imagers: From Compressed to Learned Sensing
• A Block Sparsity Based Estimator for mmWave Massive MIMO Channels with Beam Squint
• Sparse sensing and DMD based identification of flow regimes and bifurcations in complex flows
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Asynchronous Code-Division Random Access Using Convex Optimization
• Block-Sparsity-Induced Adaptive Filter for Multi-Clustering System Identification
• Reconciling Compressive Sampling Systems for Spectrally-sparse Continuous-time Signals
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Corrupted Sensing: Novel Guarantees for Separating Structured Signals
• Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
• Communications-Inspired Projection Design with Application to Compressive Sensing
• Sparse Recovery from Combined Fusion Frame Measurements
• OMP Based Joint Sparsity Pattern Recovery Under Communication Constraints
• Phase Transitions in Frequency Agile Radar Using Compressed Sensing
• Reconstruction of Signals Drawn from a Gaussian Mixture from Noisy Compressive Measurements
• Classification and Reconstruction of High-Dimensional Signals from Low-Dimensional Features in the Presence of Side Information
• Group Sparse Recovery via the ${\ell }^0({\ell }^2)$ Penalty: Theory and Algorithm
• Block-length dependent thresholds in block-sparse compressed sensing
• A New Analysis for Support Recovery with Block Orthogonal Matching Pursuit
• Restricted Isometry Property of Gaussian Random Projection for Finite Set of Subspaces
• Theoretical Analysis for Extended Target Recovery in Randomized Stepped Frequency Radars
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach
• Recursive ${\ell }_{1,\infty }$ Group lasso
• Off-Grid Direction-of-Arrival Estimation Using Second-Order Taylor Approximation
• Exploiting Restricted Boltzmann Machines and Deep Belief Networks in Compressed Sensing
• Compressed Sensing of Simultaneous Low-Rank and Joint-Sparse Matrices
• Compressive Spectrum Sensing Using Sampling-Controlled Block Orthogonal Matching Pursuit
• Group Iterative Spectrum Thresholding for Super-Resolution Sparse Spectral Selection
• Variance State Propagation for Structured Sparse Bayesian Learning
• Laser excited super resolution thermal imaging for nondestructive inspection of internal defects
• Limits on Sparse Data Acquisition: RIC Analysis of Finite Gaussian Matrices
• Compressive MUSIC: A Missing Link Between Compressive Sensing and Array Signal Processing
• Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
• Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty
• Block-Sparse Tensor Recovery
• Rank Awareness in Joint Sparse Recovery
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Hierarchized block wise image approximation by greedy pursuit strategies
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Near-optimal phase retrieval of sparse vectors
• A Unified Framework for Solving a General Class of Nonconvexly Regularized Convex Models
• Sparse Representation Classification Beyond L1 Minimization and the Subspace Assumption
• A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit
• Estimation of block sparsity in compressive sensing
• Approximate Message Passing with Nearest Neighbor Sparsity Pattern Learning
• Convex Estimation of Sparse-Smooth Power Spectral Densities from Mixtures of Realizations with Application to Weather Radar
• Robust Time-Frequency Reconstruction by Learning Structured Sparsity
• Hierarchical Isometry Properties of Hierarchical Measurements
• Variational Inference of Structured Line Spectra Exploiting Group-Sparsity
• Greedy Algorithms for Hybrid Compressed Sensing
• Compressive auto-indexing in femtosecond nanocrystallography
• Maximum entropy low-rank matrix recovery
• Large-Scale Subspace Clustering via k-Factorization
• Analysis of Block OMP using Block RIP
• Observer-based switched-linear system identification
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• A Framework for the Analysis of Computational Imaging Systems with Practical Applications
• ORKA: Object reconstruction using a K-approximation graph
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds
• Piecewise Sparse Recovery in Unions of Bases
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP) Algorithm
• Sparse Reconstruction-based Detection of Spatial Dimension Holes in Cognitive Radio Networks
• High-Dimensional Screening Using Multiple Grouping of Variables
• On the convergence of group-sparse autoencoders
• Channel Estimation for Massive MIMO Communication System Using Deep Neural Network
• Compressed sensing of block-sparse positive vectors
• Jointly Sparse Signal Recovery and Support Recovery via Deep Learning with Applications in MIMO-based Grant-Free Random Access
• Group Model Selection Using Marginal Correlations: The Good, the Bad and the Ugly
• Distributed Error-Identification and Correction using Block-Sparse Optimization
• Recoverability of Group Sparse Signals from Corrupted Measurements via Robust Group Lasso
• Height estimation for automotive MIMO radar with group-sparse reconstruction
• Composition-Aware Spectroscopic Tomography
• Fusion Frame Homotopy and Tightening Fusion Frames by Gradient Descent
• Restricted Structural Random Matrix for Compressive Sensing
• The Use of Mutual Coherence to Prove ${\ell }^1/{\ell }^0$-Equivalence in Classification Problems
• Sparse recovery guarantees for block orthogonal binary matrices constructed via Generalized Euler Squares
• LAMP: A Locally Adapting Matching Pursuit Framework for Group Sparse Signatures in Ultra-Wide Band Radar Imaging
• Block Bayesian Sparse Learning Algorithms With Application to Estimating Channels in OFDM Systems
• Sparsity-Driven Moving Target Detection in Distributed Multistatic FMCW Radars
• Approximate Subspace-Sparse Recovery with Corrupted Data via Constrained ${\ell }_1$-Minimization
• Irreducible infeasible subsystems of semidefinite systems
• Statistical inference for block sparsity of complex signals
• Multichannel group sparsity methods for compressive channel estimation in doubly selective multicarrier MIMO systems (extended version)
• Sparse Representation Classification via Screening for Graphs
• Efficient Recovery of Block Sparse Signals via Zero-point Attracting Projection
• Random linear under-determined systems with block-sparse solutions -- asymptotics, large deviations, and finite dimensions
• Sparse Representation of 3D Images for Piecewise Dimensionality Reduction with High Quality Reconstruction
• Robust Group LASSO Over Decentralized Networks
• Theoretical Linear Convergence of Deep Unfolding Network for Block-Sparse Signal Recovery
• DC algorithms for a class of sparse group ${\ell }_0$ regularized optimization problems
• Hybrid Model and Data Driven Algorithm for Online Learning of Any-to-Any Path Loss Maps
• On block coherence of frames
• Construction of wavelet dictionaries for ECG modelling