Sub-Linear Algorithm for Recovering Sparse Fourier Series
Speaker
Prof. Yang Wang
Department of Mathematics, Hong Kong University of Science and Technology
Abstract

We present new deterministic algorithms for the sparse Fourier transform problem, in which we seek to identify $k \leq N$ significant Fourier coefficients from a signal of bandwidth $N$. Previous deterministic algorithms exhibit quadratic runtime scaling, while our algorithms scales linearly with $k$ in the average case in the noiseless setting. We also present a multi-scale algorithm for noisy signals which proves to be extremely robust and efficient. This multi-scale algorithm is based on the beta-expansion scheme for robust A/D conversion. We also present the first efficient algorithm for ultra-high dimensions signals.