Block-Sparse Signals: Uncertainty Relations and Efficient Recovery

By Yonina C. Eldar, Patrick Kuppinger, Helmut Bölcskei. IEEE Transactions on Signal Processing, 2009

1,381 citations recorded by the source corpus.

We consider efficient methods for the recovery of block-sparse signals-i.e., sparse signals that have nonzero entries occurring in clusters-from an underdetermined system of linear equations. 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 -sparse signals in no more than steps if the block-coherence is sufficiently small. The same condition on block-coherence is shown to guarantee successful recovery through a mixed -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.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5e23cc7fd742e55e3d990035e87a99a195b26e5b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Sparse Signal Recovery With Temporally Correlated Source Vectors Using Sparse Bayesian Learning (2011, methodology): “Compared to most existing algorithms derived in this model [22], [41], [59], an import ant difference is that T-SBL considers the correlation within e ach block.”
Super-Resolution With Sparse Mixing Estimators (2010, background): “Since approximation vectors often appear in groups, one can select simultaneously blocks of approximation vectors [23], [24], [52], which reduces the number of possible approximation spaces.”
Group-Sparse Representation With Dictionary Learning for Medical Image Denoising and Fusion (2012, positive): “Furthermore, the group coherence of learned dictionary can be reduced through the graph regularization, which is essential for the accuracy of group sparse coding [24].”
Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG Via Block Sparse Bayesian Learning (2012, methodology): “It has been known that exploiting such a block structure can further improve reconstruction performance [14], [17], [18].”
Extension of SBL Algorithms for the Recovery of Block Sparse Signals With Intra-Block Correlation (2012, methodology): “Typical algorithms include Model-CoSaMp [3], Block-OMP [4], and Group-Lasso type algorithms such as the original Group Lasso algorithm [2], Group Basis Pursuit [5], and Mixed Program [6].”
Low-dimensional models in spatio-temporal wind speed forecasting (2015, neutral): “Deﬁnition 1 (Block K -Sparse Signal): Let x ∈ R N be a concatenation of P vector-blocks x i ∈ R n , i.e., Several extensions of the standard CS recovery algorithms can account for additional structure in the sparse signal to be recovered [25], [26].”
Position and Orientation Estimation Through Millimeter-Wave MIMO in 5G Systems (2017, background): “Signiﬁcant progress has been made in mm-wave channel estimation, by exploiting sparsity and related compressed sensing tools, such as distributed compressed sensing-simultaneous orthogonal matching pursuit (DCS-SOMP) [7], compressive sampling matched pursuit (CoSOMP) [8], and group sparse compressed”
DR2-Net: Deep Residual Reconstruction Network for Image Compressive Sensing (2017, background): “Furthermore, many elaborate structures, such as total variation sparsity [32, 21], non-local sparsity [23, 8, 23], block sparsity [11], wavelet tree sparsity [1, 13] are used as prior knowledge of the original image signals, which are beneﬁcial to compressive sensing image reconstruction.”
Structured Compressed Sensing: From Theory to Applications (2011, methodology): “There also exists an extension of the coherence property to the sparse sum of subspaces case [120].”
Exploiting sparsity of interconnections in spatio-temporal wind speed forecasting using Wavelet Transform (2016, methodology): “In our work, we use Block Orthogonal Matching Pursuit (BOMP) algorithm [35, 36] for block sparse recovery [37].”
Robust Recovery of Signals From a Structured Union of Subspaces (2008, background): “Indeed, choosing alternative bases will lead to where is a block diagonal matrix with blocks of size . Defining , the block sparsity pattern of is equal to that of . On the other hand, the basis can affect the properties of the resulting matrix . This point is beyond the scope of the present paper; ”
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation (2009, methodology): “Several alternative methods have been proposed, that have polynomial complexity [11], [13], [ 20 ]–[22], [30], [45], [47].”
From Denoising to Compressed Sensing (2014, methodology): “To predict the performance of D-AMP, we will present a framework, called state evolution , to theoretically track the standard deviation of the noise, ˆ σ t at each iteration of D-AMP.”