Robust Recovery of Signals From a Structured Union of Subspaces

By Yonina C. Eldar, Moshe Mishali. IEEE Transactions on Information Theory, 2008

1,052 citations recorded by the source corpus.

Traditional sampling theories consider the problem of reconstructing an unknown signal x from a series of samples. A prevalent assumption which often guarantees recovery from the given measurements is that x lies in a known subspace. Recently, there has been growing interest in nonlinear but structured signal models, in which x lies in a union of subspaces. In this paper, we develop a general framework for robust and efficient recovery of such signals from a given set of samples. More specifically, we treat the case in which x lies in a sum of k subspaces, chosen from a larger set of m possibilities. The samples are modeled as inner products with an arbitrary set of sampling functions. To derive an efficient and robust recovery algorithm, we show that our problem can be formulated as that of recovering a block-sparse vector whose nonzero elements appear in fixed blocks. We then propose a mixed lscr2/lscr1 program for block sparse recovery. Our main result is an equivalence condition under which the proposed convex algorithm is guaranteed to recover the original signal. This result relies on the notion of block restricted isometry property (RIP), which is a generalization of the standard RIP used extensively in the context of compressed sensing. Based on RIP, we also prove stability of our approach in the presence of noise and modeling errors. A special case of our framework is that of recovering multiple measurement vectors (MMV) that share a joint sparsity pattern. Adapting our results to this context leads to new MMV recovery methods as well as equivalence conditions under which the entire set can be determined efficiently.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/7470c6e232b90878898399215b58366a8c6bcdb2

How researchers see this paper

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

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Deep Networks for Direction-of-Arrival Estimation in Low SNR (2020, methodology): “introduced in [15] and was also employed later in [16].”
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals (2009, background): “We refer the reader to [29], and [33]–[35] for theoretical guarantees regarding MMV recovery algorithms.”
Structured Compressed Sensing: From Theory to Applications (2011, methodology): “To write down the problem explicitly, we deﬁne the mixed norm as (48) We may then recover by solving [17], [134], [136], [137] subject to (49) The optimization constraints can be relaxed to address the case of noisy measurements, in a way similar to the standard BPIC algorithm.”
Robust Compressed Sensing MRI with Deep Generative Priors (2021, background): “2 Related Work Generative priors have shown great utility to improving compressed sensing and other inverse problems, starting with [13], who generalized the theoretical framework of compressed sensing and restricted eigenvalue conditions [81, 23, 12, 15, 39, 11, 10, 25] for signals lying on the ran”
Sparse Signal Recovery With Temporally Correlated Source Vectors Using Sparse Bayesian Learning (2011, methodology): “9T-SBL can be directly used to solve the block sparsity models [13], [22], [41].”
Classification and clustering via dictionary learning with structured incoherence and shared features (2010, background): “, [4, 6, 7, 29], where it was shown that both the speed and accuracy of sparse coding techniques such as soft-thresholding and orthogonal matching pursuit depend on the incoherence between the dictionary atoms.”
Distributed Compressive CSIT Estimation and Feedback for FDD Multi-User Massive MIMO Systems (2014, methodology): “In [35], [36], a mixed-norm BP is developed to recover the block sparse signals and in [37], a select-discard OMP (SD-OMP) is proposed to recover partially joint sparse signals.”
Kronecker Compressive Sensing (2012, methodology): “Prior work for CS of multidimensional signals focuses on the e xample applications given in this paper – hyperspectral imaging [8, 38–40] and video acquisition [7, 9–12, 14, 17, 18] – with limited additional work in sensor networks [6, 15, 16] and confocal microscopy [13].”
Nonparametric Bayesian Dictionary Learning for Analysis of Noisy and Incomplete Images (2011, background): “Specifically, because natural images manifest segments and self-similarity, one may view the dictionary-learning framework within a union-of-subspaces setting [15], [23].”
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].”
Visual classification with multi-task joint sparse representation (2010, methodology): “In this paper, motivated by the success of multitask sparse linear regression models [10][15][25], we investigate into the problem of multi-task joint sparse representation along with its applications in visual recognition.”
Direction-of-Arrival Estimation Using a Mixed $\ell _{2,0}$ Norm Approximation (2010, background): “The problem is to find and from .”