×
Merhi, Sami; Zhang, Ruochuan; Iwen, Mark A.; Christlieb, Andrew

A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees. (English) Zbl 1431.65253

J. Fourier Anal. Appl. 25, No. 3, 751-784 (2019).
Summary: In this paper we consider sparse Fourier transform (SFT) algorithms for approximately computing the best \(s\)-term approximation of the discrete Fourier transform (DFT) \({\hat{\mathbf {f}}}\in {{\mathbb {C}}}^N\) of any given input vector \(\mathbf{f}\in {{\mathbb {C}}}^N\) in just \((s \log N) ^{{{\mathcal {O}}}(1)}\)-time using only a similarly small number of entries of \(\mathbf {f}\). In particular, we present a deterministic SFT algorithm which is guaranteed to always recover a near best \(s\)-term approximation of the DFT of any given input vector \(\mathbf {f}\in {{\mathbb {C}}}^N\) in \({{\mathcal {O}}} (s^2 \log ^{\frac{11}{2}} (N)) \)-time. Unlike previous deterministic results of this kind, our deterministic result holds for both arbitrary vectors \(\mathbf {f}\in {{\mathbb {C}}}^N\) and vector lengths \(N\). In addition to these deterministic SFT results, we also develop several new publicly available randomized SFT implementations for approximately computing \({\hat{\mathbf {f}}}\) from \(\mathbf {f}\) using the same general techniques. The best of these new implementations is shown to outperform existing discrete sparse Fourier transform methods with respect to both runtime and noise robustness for large vector lengths \(N\).

Cited in 10 Documents

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
65T40 Numerical methods for trigonometric approximation and interpolation
68W25 Approximation algorithms

Keywords:

fast Fourier transforms; discrete Fourier transforms; sparse Fourier transforms; nonequispaced Fourier transforms; compressive sensing; sparse approximation

Software:

Sparse FFT small support; NFFT3; NFFT
PDF BibTeX XML Cite
\textit{S. Merhi} et al., J. Fourier Anal. Appl. 25, No. 3, 751--784 (2019; Zbl 1431.65253)
Full Text: DOI arXiv

References:

[1] Bailey, J., Iwen, M.A., Spencer, C.V.: On the design of deterministic matrices for fast recovery of Fourier compressible functions. SIAM J. Matrix Anal. Appl. 33(1), 263-289 (2012) · Zbl 1286.68495
[2] Beylkin, G.: On the fast Fourier transform of functions with singularities. Appl. Comput. Harmon. Anal. 2(4), 363-381 (1995) · Zbl 0838.65142
[3] Bittens, S.: Sparse FFT for Functions with Short Frequency Support. University of Göttingen, Göttingen (2016) · Zbl 1372.65359
[4] Bittens, S., Zhang, R., Iwen, M.A.: A deterministic sparse FFT for functions with structured Fourier sparsity. arXiv:1705.05256 (2017) · Zbl 1458.42002
[5] Bluestein, L.: A linear filtering approach to the computation of discrete Fourier transform. IEEE Trans. Audio Electroacoust. 18(4), 451-455 (1970)
[6] Christlieb, A., Lawlor, D., Wang, Y.: A multiscale sub-linear time Fourier algorithm for noisy data. Appl. Comput. Harmon. Anal. 40, 553-574 (2016) · Zbl 1403.42006
[7] Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22(1), 211-231 (2009) · Zbl 1206.94008
[8] Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297-301 (1965) · Zbl 0127.09002
[9] Dutt, A., Rokhlin, V.: Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14(6), 1368-1393 (1993) · Zbl 0791.65108
[10] Dutt, A., Rokhlin, V.: Fast Fourier transforms for nonequispaced data. ii. Appl. Comput. Harmon. Anal. 2(1), 85-100 (1995) · Zbl 0822.65130
[11] Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkhäuser, Basel (2013) · Zbl 1315.94002
[12] Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: Proceedings of the Optics & Photonics 2005, pp. 59141A-59141A. International Society for Optics and Photonics (2005)
[13] Gilbert, A.C., Strauss, M.J., Tropp, J.A.: A tutorial on fast Fourier sampling. IEEE Signal Process. Mag. 25(2), 57-66 (2008)
[14] Gilbert, A.C., Indyk, P., Iwen, M., Schmidt, L.: Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data. IEEE Signal Process. Mag. 31(5), 91-100 (2014)
[15] Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of the SODA (2012) · Zbl 1286.94046
[16] Hu, X., Iwen, M., Kim, H.: Rapidly computing sparse Legendre expansions via sparse Fourier transforms. Numer. Algorithms 74(4), 1029-1059 (2017) · Zbl 1365.65034
[17] Iwen, M.A.: A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 20-29. Society for Industrial and Applied Mathematics (2008) · Zbl 1192.94047
[18] Iwen, M.A.: Simple deterministically constructible rip matrices with sublinear Fourier sampling requirements. In: Proceedings of the CISS, pp. 870-875 (2009)
[19] Iwen, M.A.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10, 303-338 (2010) · Zbl 1230.65145
[20] Iwen, M.A.: Notes on lemma 6. Preprint at www.math.msu.edu/ markiwen/Papers/Lemma6_FOCM_10.pdf (2012)
[21] Iwen, M.A.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmon. Anal. 34, 57-82 (2013) · Zbl 1260.65115
[22] Iwen, M., Gilbert, A., Strauss, M., et al.: Empirical evaluation of a sub-linear time sparse DFT algorithm. Commun. Math. Sci. 5(4), 981-998 (2007) · Zbl 1134.65093
[23] Keiner, J., Kunis, S., Potts, D.: Using NFFT 3-a software library for various nonequispaced fast Fourier transforms. ACM Trans. Math. Softw. 36(4), 19:1-19:30 (2009) · Zbl 1364.65303
[24] Laska, J., Kirolos, S., Massoud, Y., Baraniuk, R., Gilbert, A., Iwen, M., Strauss, M.: Random sampling for analog-to-information conversion of wideband signals. In: Proceedings of the 2006 IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software, pp. 119-122. IEEE (2006)
[25] Lawlor, D., Wang, Y., Christlieb, A.: Adaptive sub-linear time Fourier algorithms. Adv. Adapt. Data Anal. 5(01), 1350003 (2013)
[26] Morotti, L.: Explicit universal sampling sets in finite vector spaces. Appl. Comput. Harmonic Anal. (2016) https://doi.org/10.1016/j.acha.2016.06.001 · Zbl 1380.94060
[27] Plonka, G., Wannenwetsch, K.: A deterministic sparse FFT algorithm for vectors with small support. Numer. Algorithms 71(4), 889-905 (2016) · Zbl 1341.65056
[28] Rabiner, L., Schafer, R., Rader, C.: The chirp z-transform algorithm. IEEE Trans. Audio Electroacoust. 17(2), 86-92 (1969)
[29] Segal, I., Iwen, M.: Improved sparse Fourier approximation results: Faster implementations and stronger guarantees. Numer. Algorithms 63, 239-263 (2013) · Zbl 1276.65097
[30] Steidl, G.: A note on fast Fourier transforms for nonequispaced grids. Adv. Comput. Math. 9, 337-353 (1998) · Zbl 0917.65123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.