nach oben

Numerical Algorithms

Erschienen in:

15.07.2020 | Original Paper

High-dimensional sparse Fourier algorithms

verfasst von: Bosu Choi, Andrew Christlieb, Yang Wang

Erschienen in: Numerical Algorithms | Ausgabe 1/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we discuss the development of a sublinear sparse Fourier algorithm for high-dimensional data. In 11Adaptive Sublinear Time Fourier Algorithm” by Lawlor et al. (Adv. Adapt. Data Anal. 5(01):1350003, 2013), an efficient algorithm with \({\Theta }(k\log k)\) average-case runtime and Θ(k) average-case sampling complexity for the one-dimensional sparse FFT was developed for signals of bandwidth N, where k is the number of significant modes such that k ≪ N. In this work we develop an efficient algorithm for sparse FFT for higher dimensional signals, extending some of the ideas in Lawlor et al. (Adv. Adapt. Data Anal. 5(01):1350003, 2013). Note a higher dimensional signal can always be unwrapped into a one-dimensional signal, but when the dimension gets large, unwrapping a higher dimensional signal into a one-dimensional array is far too expensive to be realistic. Our approach here introduces two new concepts: “partial unwrapping” and “tilting.” These two ideas allow us to efficiently compute the sparse FFT of higher dimensional signals.

Vorheriger Artikel A central-line coarse preconditioner for Stokes flows in artery-like domains

Nächster Artikel Generalizing the trapezoidal rule in the complex plane

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bittens, S., Zhang, R., Iwen, M.A.: A deterministic sparse FFT for functions with structured Fourier sparsity. Adv. Comput. Math. 45(2), 519–561 (2019)MathSciNetCrossRef

Choi, B., Christlieb, A., Wang, Y.: Multiscale high-dimensional sparse Fourier algorithms for noisy data. arXiv:1907.03692 (2019)

Choi, B., Iwen, M., Krahmer, F.: Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables (2018)

Christlieb, A., Lawlor, D., Wang, Y.: A multiscale sub-linear time Fourier algorithm for noisy data. Appl. Comput. Harmon. Anal. 40(3), 553–574 (2016)MathSciNetCrossRef

Ghazi, B., Hassanieh, H., Indyk, P., Katabi, D., Price, E., Shi, L.: Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions. In: 2013 51St Annual Allerton Conference On Communication, Control, and Computing (Allerton), pp. 1258–1265. IEEE (2013)

Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representations via sampling. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 152–161. ACM (2002)

Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved Time Bounds for Near-Optimal Sparse Fourier Representations. In: Optics & Photonics 2005, pp. 59141A–59141A. International Society for Optics and Photonics (2005)

Greene, C.S., Krishnan, A., Wong, A.K., Ricciotti, E., Zelaya, R.A., Himmelstein, D.S., Zhang, R., Hartmann, B.M., Zaslavsky, E., Sealfon, S.C., et al.: Understanding multicellular function and disease with human tissue-specific networks. Nat. Gen. 47(6), 569–576 (2015)CrossRef

Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse Fourier transform. In: Proceedings of the forty-fourth annual ACM symposium on theory of computing, pp. 563–578. ACM (2012)

10.

Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pp. 1183–1194. Society for Industrial and Applied Mathematics (2012)

11.

Iwen, M.A.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10(3), 303–338 (2010)MathSciNetCrossRef

12.

Iwen, M.A.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmon. Anal. 34(1), 57–82 (2013)MathSciNetCrossRef

13.

Kämmerer, L., Potts, D., Volkmer, T.: Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling. J. Complex. 31(4), 543–576 (2015). https://doi.org/10.1016/j.jco.2015.02.004. http://www.sciencedirect.com/science/article/pii/S0885064X15000217MathSciNetCrossRef

14.

Kämmerer, L., Potts, D., Volkmer, T.: High-dimensional sparse fft based on sampling along multiple rank-1 lattices. arXiv:1711.05152 (2017)

15.

Lawlor, D., Wang, Y., Christlieb, A.: Adaptive sub-linear time Fourier algorithms. Adv. Adapt. Data Anal. 5(01), 1350003 (2013)MathSciNetCrossRef

16.

LSST: large synoptic survey telescope. http://www.lsst.org/

17.

Merhi, S., Zhang, R., Iwen, M.A., Christlieb, A.: A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees. J. Fourier Anal. Appl. 25(3), 751–784 (2019)MathSciNetCrossRef

18.

Plonka, G., Wannenwetsch, K.: A deterministic sparse FFT algorithm for vectors with small support. Numer. Algorithm. 71(4), 889–905 (2016). https://doi.org/10.1007/s11075-015-0028-0MathSciNetCrossRef

19.

Plonka, G., Wannenwetsch, K., Cuyt, A., Lee, W.S.: Deterministic sparse FFT for m-sparse vectors. Numer. Algorithm. 78(1), 133–159 (2018). https://doi.org/10.1007/s11075-017-0370-5MathSciNetCrossRef

20.

Plonka, G., Wischerhoff, M.: How many Fourier samples are needed for real function reconstruction? J. Appl. Math. Comput. 42(1), 117–137 (2013). https://doi.org/10.1007/s12190-012-0624-2MathSciNetCrossRef

21.

Potts, D., Tasche, M.: Parameter estimation for multivariate exponential sums. Electron. Trans. Numer. Anal. 40, 204–224 (2013)MathSciNetMATH

22.

Potts, D., Tasche, M., Volkmer, T.: Efficient spectral estimation by MUSIC and ESPRIT with application to sparse FFT. Front. Appl. Math. Stat. 2, 1 (2016). https://doi.org/10.3389/fams.2016.00001CrossRef

23.

Potts, D., Volkmer, T.: Sparse high-dimensional FFT based on rank-1 lattice sampling. Appl. Comput. Harmon. Anal. 41(3), 713–748 (2016)MathSciNetCrossRef

Titel: High-dimensional sparse Fourier algorithms
verfasst von: Bosu Choi
Andrew Christlieb
Yang Wang
Publikationsdatum: 15.07.2020
Verlag: Springer US
Erschienen in: Numerical Algorithms / Ausgabe 1/2021
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-020-00962-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2021

Generalizing the trapezoidal rule in the complex plane

Solving interval linear least squares problems by PPS-methods

A fast linearized numerical method for nonlinear time-fractional diffusion equations

Derivation and analysis of computational methods for fractional Laplacian equations with absorbing layers

Alternatives to the EM algorithm for ML estimation of location, scatter matrix, and degree of freedom of the Student t distribution

Correction to: On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes