DocumentCode :
775171
Title :
Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
Author :
Mishali, Moshe ; Eldar, Yonina C.
Author_Institution :
Technion-Israel Inst. of Technol., Haifa
Volume :
56
Issue :
10
fYear :
2008
Firstpage :
4692
Lastpage :
4702
Abstract :
The rapid developing area of compressed sensing suggests that a sparse vector lying in a high dimensional space can be accurately and efficiently recovered from only a small set of nonadaptive linear measurements, under appropriate conditions on the measurement matrix. The vector model has been extended both theoretically and practically to a finite set of sparse vectors sharing a common sparsity pattern. In this paper, we treat a broader framework in which the goal is to recover a possibly infinite set of jointly sparse vectors. Extending existing algorithms to this model is difficult due to the infinite structure of the sparse vector set. Instead, we prove that the entire infinite set of sparse vectors can be recovered by solving a single, reduced-size finite-dimensional problem, corresponding to recovery of a finite set of sparse vectors. We then show that the problem can be further reduced to the basic model of a single sparse vector by randomly combining the measurements. Our approach is exact for both countable and uncountable sets, as it does not rely on discretization or heuristic techniques. To efficiently find the single sparse vector produced by the last reduction step, we suggest an empirical boosting strategy that improves the recovery ability of any given suboptimal method for recovering a sparse vector. Numerical experiments on random data demonstrate that, when applied to infinite sets, our strategy outperforms discretization techniques in terms of both run time and empirical recovery rate. In the finite model, our boosting algorithm has fast run time and much higher recovery rate than known popular methods.
Keywords :
signal representation; arbitrary sets; boosting algorithm; empirical boosting strategy; finite-dimensional problem; jointly sparse vectors; single sparse vector; suboptimal method; Basis pursuit; compressed sensing; multiple measurement vectors (MMV); multiple measurement vectors (MMVs); sparse representation;
fLanguage :
English
Journal_Title :
Signal Processing, IEEE Transactions on
Publisher :
ieee
ISSN :
1053-587X
Type :
jour
DOI :
10.1109/TSP.2008.927802
Filename :
4553693
Link To Document :
بازگشت