Sparse Fourier Transform

Reading Materials:

On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions, J.Bailey, M.A.Iwen, C.V.Spencer (2012)

Nearly Optimal Sparse Fourier Transform, H.Hassanieh, P.Indyk, D.Katabi, E.Price (2012)

Simple and Practical Algorithm for Sparse Fourier Transform, H.Hassanieh, P.Indyk, D.Katabi, E.Price (2012)

Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions, B.Ghazi, H.Hassanieh, P.Indyk, D.Katabi, E.Price, L.Shi (2013)

Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(klogk) complexity, S.Pawar, K.Ramchandran (2013)

A robust sub-linear time R-FFAST algorithm for computing a sparse DFT, S.Pawar, K.Ramachandran (2015)

Combinatorial Sublinear-Time Fourier Algorithms, M.A.Iwen (2010)

Recent Developments in the Sparse Fourier Transform, A.C.Gilbert, P.Indyk, M.Iwen, L.Schmidt

Lecture Notes: L1 , L2 , L3