Efficient Software Implementation of the Nearly Optimal Sparse Fast Fourier Transform for the Noisy Case

Authors

DOI:

https://doi.org/10.17230//ingciencia.11.22.4

Keywords:

Sparse Fourier Transform, multicore programming, computer cluster

Abstract

In this paper we present an optimized software implementation (sFFT-4.0) of the recently developed Nearly Optimal Sparse Fast Fourier Transform (sFFT) algorithm for the noisy case. First, we developed a modified version of the Nearly Optimal sFFT algorithm for the noisy case, this modified algorithm solves the accuracy issues of the original version by modifying the flat window and the procedures; and second, we implemented the modified algorithm on a multicore platform composed of eight cores. The experimental results on the cluster indicate that the developed implementation is faster than direct calculation using FFTW library under certain conditions of sparseness and signal size, and it improves the execution times of previous implementations like sFFT-2.0. To the best knowledge of the authors, the developed implementation is the first one of the Nearly Optimal sFFT algorithm for the noisy case.

MSC: 65T50

Downloads

Download data is not yet available.

Author Biographies

  • Alexander López-Parrado, Universidad del Quindío. Universidad del Valle. Princeton University
    Profesor Asistente programa de Ingeniería Electrónica.
  • Jaime Velasco Medina, Universidad del Valle
    Profesor titular Escuela de Ingeniería Eléctrica y Electrónica y Director grupo Bionanoelectrónica.

References

H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Simple and practical algorithm for sparse Fourier transform,” in ACM-SIAM Symposium on Discrete Algorithms (SODA). Kyoto, Japan: SIAM, 2012, pp. 1183–1194. [Online]. Available: http://dl.acm.org/citation.cfm?id=2095116.2095209

——, “Nearly optimal sparse Fourier transform,” in Proceedings of the 44th symposium on Theory of Computing (STOC), New York, USA, May 2012. pp. 563–578.

P. Indyk, M. Kapralov, and and Eric Price, “(Nearly) Sample-Optimal Sparse Fourier Transform,” in ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland, USA, 2014.

H. Hassanieh, L. Shi, O. Abari, E. Hamed, and D. Katabi, “GHz-wide sensing and decoding using the sparse Fourier transform,” in INFOCOM, 2014 Proceedings IEEE. IEEE, 2014, pp. 2256–2264. [Online]. Available: http://dx.doi.org/10.1109/INFOCOM.2014.6848169

A. C. Gilbert, S. Muthukrishnan, and M. J. Strauss, “Improved time bounds for near-optimal sparse Fourier representations,” in Proceedings of SPIE Wavelets XI, San Diego, USA, 2005, pp. 1–15.

A. C. Gilbert, Y. Li, E. Porat, and M. J. Strauss, “Approximate sparse recovery: optimizing time and measurements,” in Proceedings of the 42nd ACM symposium on Theory of computing, Cambridge, USA, 2012.

A. C. Gilbert, M. J. Strauss, and J. A. Tropp, “A Tutorial on Fast Fourier Sampling,” IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 57–66, 2008. [Online]. Available: http://dx.doi.org/10.1109/MSP.2007.915000

M. Frigo and S. G. Johnson, FFTW, 3rd ed., Massachusetts Institute of Technology, 2012. [Online]. Available: http://www.fftw.org/

C. Wang, M. Araya-Polo, S. Chandrasekaran, A. St-Cyr, B. Chapman, and D. Hohl, “Parallel Sparse FFT,” in Proceedings of the 3rd Workshop on Irregular Applications: Architectures and Algorithms,

New York, NY, USA, 2013, pp. 10:1—-10:8. [Online]. Available: http://dx.doi.org/10.1145/2535753.2535764

J. Hu, Z. Wang, Q. Qiu, W. Xiao, and D. J. Lilja, “Sparse Fast Fourier Transform on GPUs and Multi-core CPUs,” in Computer Architecture and High Performance Computing (SBAC-PAD), 2012 IEEE

th International Symposium on, Oct. 2012, pp. 83–91. [Online]. Available: http://dx.doi.org/10.1109/SBAC-PAD.2012.34

J. Schumacher, “High Performance Sparse Fast Fourier Transform,” Master Thesis, ETH Zurich, Department of Computer Science, 2013. [Online]. Available: http://goo.gl/3alHvS

A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data, II,” Applied and Computational Harmonic Analysis, vol. 2, no. 1, pp. 85–100, 1995. [Online]. Available: http://dx.doi.org/10.1006/acha.1995.1007

M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 10th ed. Washington, DC, USA: Dover, 1972.

OpenMP, OpenMP Application Program Interface, OpenMP Architecture Review Board Std., 2013.

Downloads

Published

2015-08-03

Issue

Vol. 11 No. 22 (2015)

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).

 

How to Cite

López-Parrado, A., & Velasco Medina, J. (2015). Efficient Software Implementation of the Nearly Optimal Sparse Fast Fourier Transform for the Noisy Case. Ingeniería Y Ciencia, 11(22), 73-94. https://doi.org/10.17230//ingciencia.11.22.4