Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms

Details Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms

2010-09-30

arxiv.org/abs/1010.0014v1

Mathematics

Numerical Analysis

Scientific paper

In this paper modified variants of the sparse Fourier transform algorithms from [14] 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, $f : [0, 2 pi] -> C, in O(k^2 \cdot D^4)$ time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented.

Affiliated with

Also associated with

No associations

Rating

Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-326954