Name
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 Theta(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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s11075-020-00962-1 | NUMERICAL ALGORITHMS |
Keywords | DocType | Volume |
Higher dimensional sparse EFT, Partial unwrapping, Fast Fourier algorithms, Fourier analysis | Journal | 87 |
Issue | ISSN | Citations |
1 | 1017-1398 | 1 |
PageRank | References | Authors |
0.36 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bosu Choi | 1 | 1 | 0.36 |
| Andrew J. Christlieb | 2 | 184 | 19.03 |
| Yang Wang | 3 | 59 | 10.33 |