Robust Recovery of Signals From a Structured Union of Subspaces
Top Cited Papers
- 20 October 2009
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 55 (11), 5302-5316
- https://doi.org/10.1109/tit.2009.2030471
Abstract
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.Keywords
All Related Versions
This publication has 44 references indexed in Scilit:
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- Characterization of Oblique Dual Frame PairsEURASIP Journal on Advances in Signal Processing, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Oblique dual frames and shift-invariant spacesApplied and Computational Harmonic Analysis, 2004
- Sampling signals with finite rate of innovationIEEE Transactions on Signal Processing, 2002
- Generalizations of the sampling theorem: Seven decades after NyquistIEEE Transactions on Circuits and Systems I: Regular Papers, 2001
- Generalized sampling theorems in multiresolution subspacesIEEE Transactions on Signal Processing, 1997
- Matching pursuits with time-frequency dictionariesIEEE Transactions on Signal Processing, 1993
- A theory for multiresolution signal decomposition: the wavelet representationIEEE Transactions on Pattern Analysis and Machine Intelligence, 1989