Khajehnejad, M. Amin and Yoo, Juhwan and Anandkumar, Animashree and Hassibi, Babak (2011) Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing. In: 2011 IEEE International Symposium on Information Theory Proceedings. IEEE , Piscataway, NJ, pp. 1427-1431. ISBN 978-1-4577-0596-0 http://resolver.caltech.edu/CaltechAUTHORS:20120406-072754339
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120406-072754339
We introduce a new class of measurement matrices for compressed sensing, using low order summaries over binary sequences of a given length. We prove recovery guarantees for three reconstruction algorithms using the proposed measurements, including ℓ_1 minimization and two combinatorial methods. In particular, one of the algorithms recovers k-sparse vectors of length N in sublinear time poly(k log N), and requires at most O(k log N log log N) measurements. The empirical oversampling constant of the algorithm is significantly better than existing sublinear recovery algorithms such as Chaining Pursuit and Sudocodes. In particular, for 10^3 ≤ N ≤ 10^(12) and k = 100, the oversampling factor is between 5 to 25. We provide preliminary insight into how the proposed constructions, and the fast recovery scheme can be used in a number of practical applications such as market basket analysis, and real time compressed sensing implementation.
|Item Type:||Book Section|
|Additional Information:||© 2011 IEEE. Date of Current Version: 03 October 2011.|
|Other Numbering System:|
|Official Citation:||Khajehnejad, M.A.; Juhwan Yoo; Anandkumar, A.; Hassibi, B.; , "Summary based structures with improved sublinear recovery for compressed sensing," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.1427-1431, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6033775 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6033775&isnumber=6033677|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||06 Apr 2012 16:18|
|Last Modified:||06 Apr 2012 16:18|
Repository Staff Only: item control page