On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements

By Mihailo Stojnic, Farzad Parvaresh, Babak Hassibi. IEEE Transactions on Signal Processing, 2008

488 citations recorded by the source corpus.

Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations A x = y for a given y. In general, whenever the sparsity of x is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Candes, Donoho, and Tao shows that minimization of the lscr 1 norm of x subject to Ax = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x , the sparsity of x should be K < 0.239 N. Here, we consider the case where x is block sparse, i.e., x consists of n = N /d blocks where each block is of length d and is either a zero vector or a nonzero vector (under nonzero vector we consider a vector that can have both, zero and nonzero components). Instead of lscr1 -norm relaxation, we consider the following relaxation: times min ||X 1||2 + ||X 2||2 + ldrldrldr + ||X n ||2, subject to A x = y (*) where X i = (x ( i-1)d+1, x ( i-1)d+2, ldrldrldr , x i d)T for i = 1, 2, ldrldrldr , N. Our main result is that as n rarr infin, (*) finds the sparsest solution to A=x = y, with overwhelming probability in A, for any x whose sparsity is k/n < (1/2) - O (isin), provided m /n > 1 - 1/d, and d = Omega(log(1/isin)/isin3) . The relaxation given in (*) can be solved in polynomial time using semi-definite programming.

Subfields: Computational Mechanics, Radiology, Nuclear Medicine and Imaging

View Paper: https://www.semanticscholar.org/paper/6e0a9536996351a3fbfd16b5644f9a86e7cdd21b

How researchers see this paper

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

In Computational Mechanics

In Radiology, Nuclear Medicine and Imaging

Citations in the corpus

The Benefit of Group Sparsity (2009, background): “In [10], the authors attempted to derive a bound on the number of samples needed to recover block sparse signals, where the coe cients in each block are either all zero or all nonzero.”
Model-Based Compressive Sensing (2008, methodology): “It has been shown that the block-sparse structure enables si gnal recovery from a reduced number of CS measurements, both for the single signal case [8 , 9] and the signal ensemble case [10], through the use of specially tailored recovery al gorithms [8, 9, 42].”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, background): “, [5, 27, 66]), which require that all submatrices up to a certain size are close to isometries.”
Sparse Subspace Clustering: Algorithm, Theory, and Applications (2012, background): “Unlike blocksparse recovery problems [42], [43], [44], [45], [46], [47] where the bases for the subspaces are known and given, we do not have the bases for subspaces nor do we know which data points belong to which subspace, making our case more challenging.”
Learning with structured sparsity (2009, background): “For example, in group sparsity, one assumes that variables in the same group tend to be zero or nonzero simultaneously.”
Robust Recovery of Signals From a Structured Union of Subspaces (2008, background): “We then prove that if the measurement matrix satisﬁes the block RIP, then our proposed convex algorithm will recover the underlying block sparse signal.”
Solving Inverse Problems With Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity (2010, background): “One simultaneously selects b locks of approximation atoms, thereby reducing the number of poss ible approximation spaces [3], [26], [27], [39], [40], [69].”
Super-Resolution With Sparse Mixing Estimators (2010, background): “Since approxima tion vectors often appear in groups, one can select simultaneously blocks of approximation vect ors [25], [24], [52], which reduces the number of possible approximation spaces.”
Structured Compressed Sensing: From Theory to Applications (2011, background): “Examples include group selection consistency [136], [137], asymptotic prediction properties [137], [138], and block sparsity for logistic regression [139].”