Robust Recovery of Signals From a Structured Union of Subspaces
Open accessThe DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Abstract
Traditional sampling theories consider the problem of reconstructing an unknown signalxfrom a series of samples. A prevalent assumption which often guarantees recovery from the given measurements is thatxlies in a known subspace. Recently, there has been growing interest in nonlinear but structured signal models, in whichxlies 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 whichxlies in a sum ofksubspaces, chosen from a larger set ofmpossibilities. 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/lscr1program 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
A theory for multiresolution signal decomposition: the wavelet representation
Mallat, S. G. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.192463 · Cited by 21,372
Donoho, D. L. (2004) · Cited by 16,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Matching pursuits with time-frequency dictionaries
Mallat, S. G., & Zhang, Z. (1993) · IEEE Transactions on Signal Processing · doi:10.1109/78.258082 · Cited by 9,112
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Stable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candes, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,839
Communication in the presence of noise
Shannon, C. E. (1949) · Proceedings of the IRE · doi:10.1109/jrproc.1949.232969 · Cited by 6,539
Communication In The Presence Of Noise
Shannon, C. E. (1998) · Proceedings of the IEEE · doi:10.1109/jproc.1998.659497 · Cited by 4,804
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Needell, D., & Tropp, J. A. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2008.07.002 · Cited by 4,326
The restricted isometry property and its implications for compressed sensing
Candès, E. J. (2008) · Comptes Rendus. Mathématique · doi:10.1016/j.crma.2008.03.014 · Cited by 3,686
Certain Topics in Telegraph Transmission Theory
Nyquist, H. (1928) · Transactions of the American Institute of Electrical Engineers · doi:10.1109/t-aiee.1928.5055024 · Cited by 3,089
A sparse signal reconstruction perspective for source localization with sensor arrays
Malioutov, D., Cetin, M., & Willsky, A. S. (2005) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.850882 · Cited by 2,638 · cited 1×
“Using and was suggested in [29], [43], leading to the iterative algorithm M-FOCUSS.”
MethodA Simple Proof of the Restricted Isometry Property for Random Matrices
Baraniuk, R., Davenport, M., DeVore, R., & Wakin, M. (2008) · Constructive Approximation · doi:10.1007/s00365-007-9003-x · Cited by 2,372
Iterative hard thresholding for compressed sensing
Blumensath, T., & Davies, M. E. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2009.04.002 · Cited by 2,275
The Shannon sampling theorem—Its various extensions and applications: A tutorial review
Jerri, A. J. (1977) · Proceedings of the IEEE · doi:10.1109/proc.1977.10771 · Cited by 1,749
Sparse solutions to linear inverse problems with multiple measurement vectors
Cotter, S. F., Rao, B. D., Engan, K., & Kreutz-Delgado, K. (2005) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.849172 · Cited by 1,393
Sampling-50 years after Shannon
Unser, M. (2000) · Proceedings of the IEEE · doi:10.1109/5.843002 · Cited by 1,358
Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit
Tropp, J. A., Gilbert, A. C., & Strauss, M. J. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.030 · Cited by 1,347
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
Eldar, Y. C., Kuppinger, P., & Bolcskei, H. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2044837 · Cited by 1,313
Self-citationCommunications in the presence of noise
Shannon, C. E. (1949) · Medical Entomology and Zoology · Cited by 1,198
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
Mishali, M., & Eldar, Y. C. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042414 · Cited by 1,168
Self-citationSampling signals with finite rate of innovation
Vetterli, M., Marziliano, P., & Blu, T. (2002) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2002.1003065 · Cited by 1,079
Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals
Mishali, M., & Eldar, Y. C. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2012791 · Cited by 819
Self-citationTheoretical Results on Sparse Representations of Multiple-Measurement Vectors
Chen, J., & Huo, X. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.881263 · Cited by 810
Algorithms for simultaneous sparse approximation. Part II: Convex relaxation
Tropp, J. A. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.031 · Cited by 691
Convex Optimization in Signal Processing and Communications
(2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511804458 · Cited by 554
Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang–Fix
Dragotti, P. L., Vetterli, M., & Blu, T. (2007) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.890907 · Cited by 428
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
Eldar, Y. C., & Rauhut, H. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2034789 · Cited by 356
Self-citationA Theory for Sampling Signals From a Union of Subspaces
Lu, Y. M., & Do, M. N. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.914346 · Cited by 286
Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
Blumensath, T., & Davies, M. E. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2013003 · Cited by 269
Generalizations of the sampling theorem: Seven decades after Nyquist
Vaidyanathan, P. P. (2001) · IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications · doi:10.1109/81.948437 · Cited by 223
Recovering Sparse Signals Using Sparse Measurement Matrices in Compressed DNA Microarrays
Parvaresh, F., Vikalo, H., Misra, S., & Hassibi, B. (2008) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2008.924384 · Cited by 219
Sampling with Arbitrary Sampling and Reconstruction Spaces and Oblique Dual Frame Vectors
Eldar, Y. C. (2003) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-003-0004-2 · Cited by 194
Self-citationTime-Delay Estimation From Low-Rate Samples: A Union of Subspaces Approach
Gedalyahu, K., & Eldar, Y. C. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2044253 · Cited by 187
Self-citationCondition numbers of random matrices
Szarek, S. J. (1991) · Journal of Complexity · doi:10.1016/0885-064x(91)90002-f · Cited by 172
Compressed Sensing of Analog Signals in Shift-Invariant Spaces
Eldar, Y. C. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2020750 · Cited by 166
Self-citationEldar, Y. C., & Michaeli, T. (2009) · IEEE Signal Processing Magazine · doi:10.1109/msp.2009.932125 · Cited by 140
Self-citationSampling Without Input Constraints: Consistent Reconstruction in Arbitrary Spaces
Eldar, Y. C. (2004) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-8212-5_2 · Cited by 66
Self-citationA minimum squared-error framework for generalized sampling
Eldar, Y. C., & Dvorkind, T. G. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.873488 · Cited by 65
Self-citationUncertainty Relations for Shift-Invariant Analog Signals
Eldar, Y. C. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2032711 · Cited by 48
Self-citationUncertainty Relations for Analog SignalsPreprint
Eldar, Y. C. (2008) · Cited by 12
Self-citation
Cited by
Robust Recovery of Subspace Structures by Low-Rank Representation
Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., & Ma, Y. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.88 · Cited by 3,594
Sparse Subspace Clustering: Algorithm, Theory, and Applications
Elhamifar, E., & Vidal, R. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.57 · Cited by 3,106
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
Eldar, Y. C., Kuppinger, P., & Bolcskei, H. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2044837 · Cited by 1,313
Self-citationModel-Based Compressive Sensing
Baraniuk, R. G., Cevher, V., Duarte, M. F., & Hegde, C. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2040894 · Cited by 1,308
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
Mishali, M., & Eldar, Y. C. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042414 · Cited by 1,168
Self-citation
Metadata
- Authors
- Eldar, Y. C., & Mishali, M.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2009-11
- Volume
- 55
- Issue
- 11
- Pages
- 5302-5316
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2147276092
- Cited by
- 1,044
- References
- 44
- FWCI
- 75.89
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.