Treffer: Theoretical and experimental analysis of a randomized algorithm for Sparse Fourier transform analysis: Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis

Title:
Theoretical and experimental analysis of a randomized algorithm for Sparse Fourier transform analysis: Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
Authors:
Ingrid Daubechies, Anna C. Gilbert, Jing Zou, Martin J. Strauss
Source:
Journal of Computational Physics. 211:572-595
Publication Status:
Preprint
Publisher Information:
Elsevier BV, 2006.
Publication Year:
2006
Subject Terms:
numerical examples, sublinear algorithm, 65T50 (Primary), 68W20 (Secondary), Trigonometric approximation, Randomized algorithms, sparse Fourier representation, Numerical methods for trigonometric approximation and interpolation, Numerical Analysis (math.NA), 02 engineering and technology, 01 natural sciences, randomized algorithm, Fast Fourier transform, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Numerical Analysis, 0101 mathematics, complexity, Numerical methods for discrete and fast Fourier transforms
Document Type:
Fachzeitschrift Article
File Description:
application/xml
Language:
English
ISSN:
0021-9991
DOI:
10.1016/j.jcp.2005.06.005
DOI:
10.48550/arxiv.math/0411102
Access URL:
http://arxiv.org/pdf/math/0411102v1.pdf
http://arxiv.org/abs/math/0411102
http://www.math.lsa.umich.edu/~annacg/papers/ZGSD06.fourier.pdf
https://ui.adsabs.harvard.edu/abs/2006JCoPh.211..572Z/abstract
https://core.ac.uk/display/24668122
https://web.eecs.umich.edu/~martinjs/papers/zgsd.pdf
https://www.sciencedirect.com/science/article/pii/S0021999105002883
https://dl.acm.org/doi/10.1016/j.jcp.2005.06.005
Rights:
Elsevier TDM
arXiv Non-Exclusive Distribution
Accession Number:
edsair.doi.dedup.....03436ccfb30f203cf955b4528bd2d2d3
Database:
OpenAIRE

Weitere Informationen

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}
21 pages, 8 figures, submitted to Journal of Computational Physics