Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion

Hung Q. Ngo, Ely Porat & Atri Rudra
We present two recursive techniques to construct compressed sensing schemes that can be "decoded" in sub-linear 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...