Sublinear-Time Sparse Recovery, and Its Power in the Design of Exact Algorithms

Abstract

In the sparse recovery problem one wants to reconstruct an approximatelly k-sparse vector x in R^n using time and number of measurements that are sublinear, i.e. way less n, ideally nearly linear in k. Depending on the setting, measurements correspond to one of the following: linear combinations of the entries of x, a non-linear function of some linear function of x , Fourier coefficients, the logical OR of entries in x. In this thesis I describe several new contributions to the field of sparse recovery, as well as indicate how sparse recovery techniques can be of great significance in the design of exact algorithms, outside of the scope of the problems they first were created for.