Home Theory Evaluation Code Applications Hardware Publications News People Workshops


  • Sample-Optimal Sparse Fourier Transform in Any Constant Dimension
    Piotr Indyk and Michael Kapralov
    FOCS, October 2014.

  • (Nearly) Sample-Optimal Sparse Fourier Transform
    Piotr Indyk, Michael Kapralov, and Eric Price
    SODA, January 2014.

  • Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
    Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, Lixin Shi
    Allerton, October 2013.

  • Nearly Optimal Sparse Fourier Transform
    Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.
    STOC, May 2012.
    [PAPER]   [SLIDES]  

  • Simple and Practical Algorithm for Sparse Fourier Transform
    Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.
    SODA, January 2012.
    [PAPER]   [SLIDES]  


  • Light Field Reconstruction Using Sparsity in the Continuous Fourier Domain
    Lixin Shi, Haitham Hassanieh, Abe Davis, Dina Katabi and Fredo Durand
    ACM Transactions on Graphics, 2014.

  • High-Throughput Implementation of a Million-Point Sparse Fourier Transform
    Abhinav Agarwal, Haitham Hassanieh, Omid Abari, Ezz Hamed, Dina Katabi, and Arvind
    FPL, September 2014.

  • GHz-Wide Sensing and Decoding Using the Sparse Fourier Transform
    Haitham Hassanieh, Lixin Shi, Omid Abari, Ezzeldin Hamed, and Dina Katabi
    INFOCOM, April 2014.

  • Correlation Chemical Shift Imaging with Sparse-FFT and Real-time Motion and Shim Correction
    Ovidiu Andronesi, Lixin Shi, Haitham Hassanieh, Wolfgang Bogner, Borjan Gagoski, Aaron Hess, Dylan Tisdall, Andre van der Kouwe, Dina Katabi, and Elfar Adalsteinsson.
    ENC, March 2013.

  • A 0.75 Million-Point Fourier Transform Chip for Frequency-Sparse Signals
    O. Abari, E. Hamed, H. Hassanieh, A. Agarwal, D. Katabi, A. Chandrakasan, and V. Stojanovic.
    ISSCC, February 2014.

  • MRS Sparse-FFT: Reducing Acquisition Time and Artifacts for In Vivo 2D Correlation Spectroscopy
    Lixin Shi, Ovidiu Andronesi, Haitham Hassanieh, Badih Ghazi, Dina Katabi, and Elfar Adalsteinsson
    ISMRM, October 2013.

  • Faster GPS Via the Sparse Fourier Transform
    Haitham Hassanieh, Fadel Adib, Dina Katabi, and Piotr Indyk
    MOBICOM, August 2012.
    [PAPER]   [SLIDES]  

Related Work:

Below is a list of related work on the sparse Fourier transform. If we missed some papers or if in the future new papers are published, please email us and we will update the list.

  • Robustifying the Sparse Walsh-Hadamard Transform without Increasing the Sample Complexity of O(K log N), Xiao Li, Joseph Kurata Bradley, Sameer Pawar and Kannan Ramchandran, EECS, UC Berkeley, 2014, [PAPER]

  • A robust FFAST framework for computing a k-sparse n-length DFT in O(k logn) sample complexity using sparse-graph codes, Sameer Pawar and Kannan Ramchandran, EECS, UC Berkeley, February, 2014 [PAPER]

  • Faster GPS/IRNSS acquisition via sub sampled fast Fourier transform (ssFFT) and thresholding, M. Venu Gopala Rao and D. Venkata Ratnam, INDICON, December, 2013 [PAPER]

  • Computationally-efficient blind sub-Nyquist sampling for sparse spectra, Sameer Pawar, Venkatesan Ekambaram and Kannan Ramchandran, GlobalISIP, December, 2013 [PAPER]

  • Parallel sparse FFT, Cheng Wang, Mauricio Araya-Polo, Sunita Chandrasekaran, Amik St-Cyr, Barbara Chapman, and Detlef Hohl, IA, November, 2013 [PAPER]

  • A Fast Hadamard Transform for Signals with Sub-linear Sparsity, Robin Scheibler, Saeid Haghighatshoar and Martin Vetterli, Allerton October, 2013 [PAPER]

  • Optimized Sparse Fast Fourier Transform, Jörn Schumacher and Markus Püschel, http://www.spiral.net/software/sfft.html

  • High performance sparse fast Fourier transform, Jörn Schumacher Master thesis, Computer Science, ETH Zurich, Switzerland, 2013 [PAPER]

  • Sparse 2D Fast Fourier Transform Andre Rauh and Gonzalo R. Arce, SampTA, July, 2013 [PAPER]

  • A sparse prony fft, Sabine Heider, Stefan Kunis, Daniel Potts, and Michael Veit, SampTA, July, 2013 [PAPER]

  • Permuted & Filtered Spectrum Compressive Sensing, Biao Sun, Qian Chen, Xinxin Xu, Yun He, and Jianjun Jiang, IEEE Signal Processing Letters, Vol 20, Issue 7, pages 685 -- 688, July, 2013 [PAPER]

  • Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O (k log k) complexity , Sameer Pawar and Kannan Ramchandran, ISIT, July , 2013 [PAPER]

  • A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data, Andrew Christlieb, David Lawlor, and Yang Wang, arXiv:1304.4517, April, 2013 [PAPER]

  • sMFCC: exploiting sparseness in speech for fast acoustic feature extraction on mobile devices--a feasibility study, Shahriar Nirjon, Robert Dickerson, John Stankovic, Guobin Shen, Xiaofan Jiang, HotMobile, February, 2013 [PAPER]

  • Adaptive sub-linear Fourier algorithms, David Lawlor, Yang Wang, and Andrew Christlieb, Advances in Adaptive Data Analysis, Januray, 2013 [PAPER]

  • An Input-Adaptive Algorithm for High Performance Sparse Fast Fourier Transform, Shuo Chen and Xiaoming Li, [PAPER]

  • Sparse fast fourier transform on gpus and multi-core cpus, Jiaxi Hu, Zhaosen Wang, Qiyuan Qiu, Weijun Xiao, and David J. Lilja, IEEE 24th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), October, 2012 [PAPER]

  • What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid, Petros Boufounos, Volkan Cevher, Anna C. Gilbert,Yi Li, and Martin J. Strauss, RANDOM/APPROX, 2012 [PAPER]

  • Improved approximation guarantees for sublinear-time fourier algorithms, Mark Iwen, Applied and Computational Harmonic Analysis, Vol. 34, Issue 1, pages 57 -- 82, 2010 [PAPER]

  • Combinatorial sublinear-time Fourier algorithms, Mark Iwen, Foundations of Computational Mathematics, Vol. 10, Issue 3, pages 303 -- 338, 2010 [PAPER]

  • Deterministic sparse Fourier approximation via fooling arithmetic progressions, Adi Akavia, COLT, June. 2010 [PAPER]

  • AAFFT (Ann Arbor Fast Fourier Transform), Mark Iwen, http://sourceforge.net/projects/aafftannarborfa/

  • Empirical evaluation of a sub-linear time sparse dft algorithm, Mark Iwen, Anna Gilbert, and Martin Strauss, Communications in Mathematical Sciences, Vol. 5, Issue 4, December, 2007 [PAPER]

  • Improved time bounds for near-optimal space Fourier representations, Anna Gilbert, S. Muthukrishnan, and Martin Strauss, SPIE Wavelets, August, 2005 [PAPER]

  • Proving hard-core predicates using list decoding, Adi Akavia, Shafi Goldwasser, and Samuel Safra, FOCS, October, 2003 [PAPER]

  • Near-optimal sparse Fourier representations via sampling, Anna Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, and Martin Strauss, STOC, May, 2002 [PAPER]

  • Randomized interpolation and approximation of sparse polynomials, Yishay Mansour, ICALP, July, 1992 [PAPER]