Ngo, Hung Q. ;
Porat, Ely ;
Rudra, Atri
Efficiently Decodable Compressed Sensing by ListRecoverable Codes and Recursion
Abstract
We present two recursive techniques to construct compressed sensing schemes that can be "decoded" in sublinear time. The first technique is based on the well studied code composition method called code concatenation where the "outer" code has strong list recoverability properties. This technique uses only one level of recursion and critically uses the power of list recovery. The second recursive technique is conceptually similar, and has multiple recursion levels. The following compressed sensing results are obtained using these techniques:
 Strongly explicit efficiently decodable l_1/l_1 compressed sensing matrices: We present a strongly explicit ("for all") compressed sensing measurement matrix with O(d^2log^2 n) measurements that can output nearoptimal dsparse approximations in time poly(d log n).
 Nearoptimal efficiently decodable l_1/l_1 compressed sensing matrices for nonnegative signals: We present two randomized constructions of ("for all") compressed sensing matrices with near optimal number of measurements: O(d log n loglog_d n) and O_{m,s}(d^{1+1/s} log n (log^(m) n)^s), respectively, for any integer parameters s,m>=1. Both of these constructions can output near optimal dsparse approximations for nonnegative signals in time poly(d log n).
To the best of our knowledge, none of the results are dominated by existing results in the literature.
BibTeX  Entry
@InProceedings{ngo_et_al:LIPIcs:2012:3401,
author = {Hung Q. Ngo and Ely Porat and Atri Rudra},
title = {{Efficiently Decodable Compressed Sensing by ListRecoverable Codes and Recursion}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {230241},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3401},
URN = {urn:nbn:de:0030drops34011},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.230},
annote = {Keywords: Compressed Sensing, SubLinear Time Decoding, ListRecoverable Codes}
}
2012
Keywords: 

Compressed Sensing, SubLinear Time Decoding, ListRecoverable Codes 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 