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

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. 

About the Speaker


2016-01-08 11:30 AM
Room: A203 Meeting Room
CSRC 新闻 CSRC News CSRC Events CSRC Seminars CSRC Divisions