Introduction
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 MillionPoint Fourier Transform Chip for FrequencySparse Signals ISSCC'14,
International SolidState 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 2226, 2012, Istanbul, Turkey.
 A. Akavia, Deterministic sparse Fourier approximation via fooling arithmetic progressions, COLT, June. 2010
 A. Akavia, S. Goldwasser, and S. Safra, Proving hardcore 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 InputAdaptive Algorithm for High Performance Sparse Fast Fourier Transform,
 A. Christlieb, D. Lawlor, and Y. Wang, A Multiscale Sublinear Time Fourier Algorithm for Noisy Data, arXiv:1304.4517, April, 2013
 B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, L. Shi, SampleOptimal AverageCase Sparse Fourier Transform in Two Dimensions,
Allerton, October 2013.
 A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, Nearoptimal 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., 91100, September 2014.
 A. C. Gilbert, S. Muthukrishnan, and M. Strauss, Improved time bounds for nearoptimal space Fourier representations,
SPIE Wavelets, August, 2005
 H. Hassanieh, L. Shi, O. Abari, E. Hamed, D. Katabi,GHzWide 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 multicore cpus,
IEEE 24th International Symposium on Computer Architecture and High Performance Computing (SBACPAD), October, 2012
 P. Indyk, M. Kapralov, and E. Price, (Nearly) SampleOptimal Sparse Fourier Transform, SODA,
January 2014.
 M. Iwen, Improved approximation guarantees for sublineartime fourier algorithms, Applied and Computational Harmonic Analysis, Vol. 34,
Issue 1, pages 57  82, 2010
 M. Iwen, Combinatorial sublineartime 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 sublinear 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 sublinear Fourier algorithms,
Advances in Adaptive Data Analysis, Januray, 2013
 X. Li, J. K. Bradley, S. Pawar and K. Ramchandran,
Robustifying the Sparse WalshHadamard 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 devicesa feasibility study, HotMobile, February, 2013
 S. Pawar and K. Ramchandran, A robust FFAST framework for computing a ksparse nlength DFT in O(k logn) sample complexity using sparsegraph codes,
EECS, UC Berkeley, February, 2014
 S. Pawar, V. Ekambaram and K. Ramchandran, Computationallyefficient blind subNyquist sampling for sparse spectra,
GlobalISIP, December, 2013
 S. Pawar and K. Ramchandran, Computing a ksparse nlength 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 Sublinear Sparsity,
Allerton October, 2013

J. Schumacher and M. Puschel, Optimized Sparse Fast Fourier Transform,
http://www.spiral.net/software/sfft.html

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. ArayaPolo, S. Chandrasekaran, A. StCyr, B. Chapman, and D. Hohl, Parallel sparse FFT,
IA, November, 2013
Thanks to the sparse Fourier transform group for providing these references.
