Mathematics – Numerical Analysis
Scientific paper
2004-11-04
Mathematics
Numerical Analysis
21 pages, 8 figures, submitted to Journal of Computational Physics
Scientific paper
We analyze a sublinear RAlSFA (Randomized Algorithm for Sparse Fourier Analysis) that finds a near-optimal B-term Sparse Representation R for a given discrete signal S of length N, in time and space poly(B,log(N)), following the approach given in \cite{GGIMS}. Its time cost poly(log(N)) should be compared with the superlinear O(N log N) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RAlSFA, as presented in the theoretical paper \cite{GGIMS}, turns out to be very slow in practice. Our main result is a greatly improved and practical RAlSFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RAlSFA constructs, with probability at least 1-delta, a near-optimal B-term representation R in time poly(B)log(N)log(1/delta)/ epsilon^{2} log(M) such that ||S-R||^{2}<=(1+epsilon)||S-R_{opt}||^{2}. Furthermore, this RAlSFA implementation already beats the FFTW for not unreasonably large N. We extend the algorithm to higher dimensional cases both theoretically and numerically. The crossover point lies at N=70000 in one dimension, and at N=900 for data on a N*N grid in two dimensions for small B signals where there is noise.
Daubechies Ingrid
Gilbert Anna
Strauss Martin
Zou Jing
No associations
LandOfFree
Theoretical and Experimental Analysis of a Randomized Algorithm for Sparse Fourier Transform Analysis 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 Theoretical and Experimental Analysis of a Randomized Algorithm for Sparse Fourier Transform Analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theoretical and Experimental Analysis of a Randomized Algorithm for Sparse Fourier Transform Analysis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-498459