Back to Search
Start Over
Improved approximation guarantees for sublinear-time Fourier algorithms
- Source :
-
Applied & Computational Harmonic Analysis . Jan2013, Vol. 34 Issue 1, p57-82. 26p. - Publication Year :
- 2013
-
Abstract
- Abstract: In this paper modified variants of the sparse Fourier transform algorithms from Iwen (2010) [32] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, , in time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 10635203
- Volume :
- 34
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Applied & Computational Harmonic Analysis
- Publication Type :
- Academic Journal
- Accession number :
- 82437216
- Full Text :
- https://doi.org/10.1016/j.acha.2012.03.007