Sublinear Time Algorithms for the Sparse Recovery Problem.

Abstract

In the sparse recovery problem, we have a signal x in R^N that is sparse; i.e., it consists of k significant entries (heavy hitters) while the rest of the entries are essentially negligible. Let x_[k] in R^N consist of the k largest coefficients (in magnitude, i.e., absolute value) of x, zeroing out all other entries. We want to recover x_[k], the positions and values of only the heavy hitters, as the rest of the signal is not of interest. The Fourier case of this problem concerns the signal with a sparse Fourier transform and asks to recover the significant frequencies and the corresponding coefficients. This thesis investigates two cases of the sparse recovery problem of different error metrics and a generalization of the Fourier case that allows the frequencies to be real numbers instead of lattice points.