Sublinear Time Algorithms for the Sparse Recovery Problem.

[摘要] 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.

[发布机构] University of Michigan

[效力级别] Sparse Recovery Problem

[关键词] Sublinear-time Algorithms;Sparse Recovery Problem;Off-the-Grid Fourier Sampling;Computer Science;Engineering;Computer Science & Engineering