Sublinear Time Algorithms for the Sparse Recovery Problem.

Sublinear-time Algorithms;Sparse Recovery Problem;Off-the-Grid Fourier Sampling;Computer Science;Engineering;Computer Science & Engineering

Li, YiGilbert, Anna Catherine ;

University of Michigan

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

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/102438/leeyi_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.