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. 

Homepage：http://www.math.ust.hk/~yangwang/