Norbert Wiener at the board Norbert Wiener Center

Home >Research Activities > DFT> Publications




Publications related to the sparse fast Fourier transform.

  • O. Abari, E. Hamed, H. Hassanieh, A. Agarwal, D. Katabi, A. Chandrakasan, and V. Stojanovic, A 0.75 Million-Point Fourier Transform Chip for Frequency-Sparse Signals ISSCC'14, International Solid-State Circuits Conference, San Francisco USA, February 2014.

  • F. Adib, D. Katabi, and P. Indyk, H. Hassanieh, Faster GPS Via the Sparse Fourier Transform, MobiCom'12, August 22-26, 2012, Istanbul, Turkey.

  • A. Akavia, Deterministic sparse Fourier approximation via fooling arithmetic progressions, COLT, June. 2010

  • A. Akavia, S. Goldwasser, and S. Safra, Proving hard-core predicates using list decoding, FOCS, October, 2003

  • P. Boufounos, V. Cevher, A. C. Gilbert, Y. Li, and M. J. Strauss, What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid, RANDOM/APPROX, 2012

  • S. Chen and X. Li, An Input-Adaptive Algorithm for High Performance Sparse Fast Fourier Transform,

  • A. Christlieb, D. Lawlor, and Y. Wang, A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data, arXiv:1304.4517, April, 2013

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

  • A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, Near-optimal sparse Fourier representations via sampling, STOC, May, 2002

  • A. C. Gilbert, P. Indyk, M. Iwen, and L. Schmidt, Recent Developments in the Sparse Fourier Transform, IEEE Signal Process. Mag., 91--100, September 2014.

  • A. C. Gilbert, S. Muthukrishnan, and M. Strauss, Improved time bounds for near-optimal space Fourier representations, SPIE Wavelets, August, 2005

  • H. Hassanieh, L. Shi, O. Abari, E. Hamed, D. Katabi,GHz-Wide Sensing and Decoding Using the Sparse Fourier Transform INFOCOM'14, IEEE International Conference on Computer Communications, April 2014.

  • H. Hassanieh, P. Indyk, D. Katabi, and E. Price, Simple and Practical Algorithm for Sparse Fourier Transform, STOC, May 2012.

  • S. Heider, S. Kunis, D. Potts, and M. Veit, A sparse prony fft, SampTA, July, 2013

  • J. Hu, Z. Wang, Q. Qiu, W. Xiao, and D. J. Lilja, Sparse fast fourier transform on gpus and multi-core cpus, IEEE 24th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), October, 2012

  • P. Indyk, M. Kapralov, and E. Price, (Nearly) Sample-Optimal Sparse Fourier Transform, SODA, January 2014.

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

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

  • M. Iwen, AAFFT (Ann Arbor Fast Fourier Transform),

  • M. Iwen, A. C. Gilbert, and M. Strauss, Empirical evaluation of a sub-linear time sparse dft algorithm, Communications in Mathematical Sciences, Vol. 5, Issue 4, December, 2007

  • M. Kapralov, Piotr Indyk and E. Price, Nearly Optimal Sparse Fourier Transform, 2013

  • D. Lawlor, Y. Wang, and A. Christlieb, Adaptive sub-linear Fourier algorithms, Advances in Adaptive Data Analysis, Januray, 2013

  • X. Li, J. K. Bradley, S. Pawar and K. Ramchandran, Robustifying the Sparse Walsh-Hadamard Transform without Increasing the Sample Complexity of O(K log N), EECS, UC Berkeley, 2014,

  • Y. Mansour, Randomized interpolation and approximation of sparse polynomials ICALP, July, 1992

  • S. Nirjon, R. Dickerson, J. Stankovic, G. Shen, X. Jiang, sMFCC: exploiting sparseness in speech for fast acoustic feature extraction on mobile devices--a feasibility study, HotMobile, February, 2013

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

  • S. Pawar, V. Ekambaram and K. Ramchandran, Computationally-efficient blind sub-Nyquist sampling for sparse spectra, GlobalISIP, December, 2013

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

  • A. Rauh and G. R. Arce, Sparse 2D Fast Fourier Transform, SampTA, July, 2013

  • R. Scheibler, S. Haghighatshoar and M. Vetterli, A Fast Hadamard Transform for Signals with Sub-linear Sparsity, Allerton October, 2013

  • J. Schumacher and M. Puschel, Optimized Sparse Fast Fourier Transform,

  • J. Schumacher, High performance sparse fast Fourier transform, Master thesis, Computer Science, ETH Zurich, Switzerland, 2013

  • B. Sun, Q. Chen, X. Xu, Y. He, and J. Jiang, Permuted and Filtered Spectrum Compressive Sensing, IEEE Signal Processing Letters, Vol 20, Issue 7, pages 685 -- 688, July, 2013

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

  • C. Wang, M. Araya-Polo, S. Chandrasekaran, A. St-Cyr, B. Chapman, and D. Hohl, Parallel sparse FFT, IA, November, 2013

Thanks to the sparse Fourier transform group for providing these references.

University of Maryland

Stay Connected

FacebookYouTube Wikipedia

Norbert Wiener Center
Department of Mathematics
University of Maryland
College Park, MD 20742
Phone: (301) 405-5158
The Norbert Wiener Center is part of the College of Computer, Mathematical, and Natural Sciences.