Block-Sparse Recovery via Convex Optimization

Abstract

Given a dictionary that consists of multiple blocks and a signal that lives in the range space of only a few blocks, we study the problem of finding a block-sparse representation of the signal, i.e., a representation that uses the minimum number of blocks. Motivated by signal/image processing and computer vision applications, such as face recognition, we consider the block-sparse recovery problem in the case where the number of atoms in each block is arbitrary, possibly much larger than the dimension of the underlying subspace. To find a block-sparse representation of a signal, we propose two classes of non-convex optimization programs, which aim to minimize the number of nonzero coefficient blocks and the number of nonzero reconstructed vectors from the blocks, respectively. Since both classes of problems are NP-hard, we propose convex relaxations and derive conditions under which each class of the convex programs is equivalent to the original non-convex formulation. Our conditions depend on the notions of mutual and cumulative subspace coherence of a dictionary, which are natural generalizations of existing notions of mutual and cumulative coherence. We evaluate the performance of the proposed convex programs through simulations as well as real experiments on face recognition. We show that treating the face recognition problem as a block-sparse recovery problem improves the state-of-the-art results by 10% with only 25% of the training data.

IEEE Transactions on Signal Processing

References in corpus (6)

• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• The composite absolute penalties family for grouped and hierarchical variable selection
• A geometric analysis of subspace clustering with outliers
• Joint-sparse recovery from multiple measurements
• Multi-Label Prediction via Compressed Sensing
• Sparse Recovery from Combined Fusion Frame Measurements

Cited by in corpus (26)

• MAJoRCom: A Dual-Function Radar Communication System Using Index Modulation
• Block-Sparsity-Induced Adaptive Filter for Multi-Clustering System Identification
• Group Sparse Recovery via the ${\ell }^0({\ell }^2)$ Penalty: Theory and Algorithm
• Theoretical Analysis for Extended Target Recovery in Randomized Stepped Frequency Radars
• Sparse Subspace Clustering: Algorithm, Theory, and Applications
• Interference Exploitation-based Hybrid Precoding with Robustness Against Phase Errors
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Sparse Representation Classification Beyond L1 Minimization and the Subspace Assumption
• Estimation of block sparsity in compressive sensing
• Convex Estimation of Sparse-Smooth Power Spectral Densities from Mixtures of Realizations with Application to Weather Radar
• Improved Support Recovery Guarantees for the Group Lasso With Applications to Structural Health Monitoring
• Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
• The high order block RIP condition for signal recovery
• Robust Face Recognition via Block Sparse Bayesian Learning
• Piecewise Sparse Recovery in Unions of Bases
• Modal Regression based Atomic Representation for Robust Face Recognition
• Group Model Selection Using Marginal Correlations: The Good, the Bad and the Ugly
• A sharp sufficient condition of block signal recovery via $l_2/l_1$-minimization
• Composition-Aware Spectroscopic Tomography
• A Multiple Hypothesis Testing Approach to Low-Complexity Subspace Unmixing
• Irreducible infeasible subsystems of semidefinite systems
• Sparse Representation Classification via Screening for Graphs
• Approximate Subspace-Sparse Recovery with Corrupted Data via Constrained ${\ell }_1$-Minimization
• Sparse Illumination Learning and Transfer for Single-Sample Face Recognition with Image Corruption and Misalignment
• Learning optimally separated class-specific subspace representations using convolutional autoencoder