Download pdf
From FFT to sparse FFT: Innovations in efficient signal processing for large sparse data
- 1 University of Waterloo
* Author to whom correspondence should be addressed.
Abstract
This paper explores the advancements from the traditional Fast Fourier Transform (FFT) to the Sparse Fast Fourier Transform (sFFT) and their implications for efficient signal processing of large, sparse datasets. FFT has long been a fundamental component in digital signal processing, significantly lowering the runtime of the Discrete Fourier Transform. However, the ingress of big data has necessitated much more efficient algorithms. In contrast, the sFFT exploits the sparsity in the signals themselves to reduce computational demand, and it becomes very efficient. This paper will discuss the theoretical backing of these two developments, FFT and sFFT, and the algorithmic development in both. In addition, it will also discuss the practical applications of both with emphasis on how the latter outperforms the former in large, sparse data. Comparative analysis shows that sFFT has far greater efficiency and noise tolerance, which is of value for network traffic analysis, astrophysical data analysis, and real-time medical imaging. The purpose of this paper is to provide clarity regarding these transformations and their relationship to being paradigms in modern signal analysis.
Keywords
Fast Fourier transform, Sparse fast Fourier transform, Signal processing, Computational efficiency
[1]. Oppenheim, A. V., & Schafer, R. W. (1975). Digital Signal Processing. Prentice-Hall.
[2]. Brigham, E. O. (1988). The Fast Fourier Transform and Its Applications. Prentice-Hall.
[3]. Cooley, J. W., & Tukey, J. W. (1965). An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19(90), 297-301.
[4]. Hassanieh, H., Indyk, P., Katabi, D., & Price, E. (2012). Nearly Optimal Sparse Fourier Transform. Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 563-578.
[5]. Markovsky, I., & Van Huffel, S. (2007). Overview of Total Least-Squares Methods. Signal Processing, 87(10), 2283-2302.
[6]. Lin, S., Liu, N., Nazemi, M., Li, H., Ding, C., Wang, Y., & Pedram, M. (2017). FFT-Based Deep Learning Deployment in Embedded Systems. ResearchGate.
[7]. Tropp, J. A., & Gilbert, A. C. (2007). Signal Recovery from Random Measurements via Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 53(12), 4655-4666.
[8]. Press, W. H., & Rybicki, G. B. (1989). Fast Algorithm for Spectral Analysis of Unevenly Sampled Data. The Astrophysical Journal, 338, 277-280.
[9]. Candès, E. J., Romberg, J., & Tao, T. (2006). Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52(2), 489-509.
[10]. Frigo, M., & Johnson, S. G. (2005). The Design and Implementation of FFTW3. Proceedings of the IEEE, 93(2), 216-231.
[11]. Mitra, S. K. (2006). Digital Signal Processing: A Computer-Based Approach. McGraw-Hill.
[12]. Kumar, G. G., Sahoo, S. K., & Meher, P. K. (2019). 50 years of FFT algorithms and applications. Circuits, Systems, and Signal Processing, 38(12), 5665–5698.
[13]. Hsieh, S.-H., Lu, C.-S., & Pei, S.-C. (2015). Sparse Fast Fourier Transform for exactly and generally K-sparse signals by downsampling and sparse recovery.
[14]. Gilbert, A. C., Indyk, P., Iwen, M. A., & Strauss, M. J. (2013). Recent developments in the sparse Fourier transform: A compressed Fourier transform for big data. In S. H. Teng (Ed.), Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 954–971.
[15]. Iwen, M. A. (2010). Combinatorial sublinear-time Fourier algorithms. Foundations of Computational Mathematics, 10(3), 303–338.
[16]. Gilbert, A., Iwen, M. A., & Strauss, M. (2007). Empirical evaluation of a sub-linear time sparse DFT algorithm. Communications in Mathematical Sciences, 5(4), 981–998.
[17]. Jiang, Z., Chen, J., & Li, B. (2021). Empirical evaluation of typical sparse fast Fourier transform algorithms. IEEE Access, 9, 97100-97119.
[18]. Li, B., Jiang, Z., & Chen, J. (2021). On performance of sparse fast Fourier transform algorithms using the aliasing filter. Electronics, 10(9), 1117.
[19]. López-Parrado, A., & Velasco Medina, J. (2015). Efficient software implementation of the nearly optimal sparse fast Fourier transforms for the noisy case. Ingeniería y Ciencia, 11(22), 73–94.
[20]. Iwen, M. A. (2013). Improved approximation guarantees for sublinear-time Fourier algorithms. Applied and Computational Harmonic Analysis, 34(1), 57-82.
Cite this article
Shen,A. (2024). From FFT to sparse FFT: Innovations in efficient signal processing for large sparse data. Theoretical and Natural Science,52,58-65.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of CONF-MPCS 2024 Workshop: Quantum Machine Learning: Bridging Quantum Physics and Computational Simulations
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. 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
Open access policy for details).