Home >Research Activities > DFT> Publications

 

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 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, 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. 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.