Application of sparse Fourier transform to narrow-band radio signals analysis

Аuthors

Trofimov D. V.^*, Baev A. B.^**

Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia

*e-mail: radiovtuz@bk.ru
**e-mail: baev@mai.ru

Abstract

The discrete Fourier transform (DFT) is a component of numerous computational techniques in signal processing and scientific computing. The most popular means of computing the DFT is the fast Fourier transform (FFT). FFT is one of the most fundamental numerical algorithms. It computes the DFT of an N-dimensional signal. The algorithm plays a central role in several application areas, including signal processing. However, with the emergence of bulk data volumes problems, when the size of the processed data sets can easily exceed terabytes, the «fast» in FFT is often no longer fast enough. In many applications, however, most of the Fourier coefficients of a signal are small or equal to zero, i.e., the output of the DFT is (approximately) sparse. Since most of video, audio, medical images, spectroscopic measurements (e.g., nuclear magnetic resonance), global positioning system (GPS) signals, seismic data, and many more massive data sets are compressible or are sparse, these results promise a significant practical impact in many big data domains. The sparse Fourier transform (SFT) addresses the big data setting by computing a compressed Fourier transform using only a subset of the input data, in time smaller than the data set size.

The first algorithms of this type were developped for the Hadamard transform. Developed SFT algorithms compute an approximation or compressed version of the DFT in time proportional to the sparsity of the spectrum of the signal (i.e., the number of dominant frequencies), as opposed to the length of the signal. The algorithms run in time proportional to the sparsity or desired compression, considerably faster than in time proportional to the signal length. This is made possible by requiring that the algorithms report only the nonzero or large frequencies and their complex amplitudes, rather than a vector containing this information for all frequencies. We focus on explaining the basic components and techniques used in the aforementioned algorithms and present an empirical analysis of the performance of the algorithms. In this paper, the general principles of the sparse Fourier transform are considered as well as the numerical comparison of several simulation algorithms.

Keywords:

sparsity, spectrum, Discrete Fourier transform, sparse Fourier transform, electromagnetic radiation control (monitoring)

References

1. Gilbert A.C., et al., Recent Developments in the Sparse Fourier Transform, Signal Processing Magazine, 2014, vol. 31, no. 5, pp. 91-100.

2. H. Hassanieh, et al., «GHz-Wide Sensing and Decoding Using the Sparse Fourier Transform», IEEE International Conference on Computer Communications (INFOCOM), Toronto Canada, April 2014, pp. 2256-2264.

3. Shengheng Liu, et al., «Sparse Discrete Fractional Fourier Transform and Its Applications», IEEE Transactions on Signal Processing, 2014, vol. 62, no. 24, pp. 6582-6595.

4. Soo-Chang Pei, et al., «A New Discrete Fractional Fourier Transform Based on Constrained Eigendecomposition of DFT Matrix by Largrange Multiplier Method», IEEE Transactions on Circuits and Systems — II: Analog and Digital Signal Processing, September 1999, vol. 46, no. 9, pp. 1240-1245.

Download