Math @ Duke

Publications [#287173] of Ingrid Daubechies
Papers Published
 Zou, J; Gilbert, A; Strauss, M; Daubechies, I, Theoretical and experimental analysis of a randomized algorithm for Sparse Fourier transform analysis,
Journal of Computational Physics, vol. 211 no. 2
(January, 2006),
pp. 572595, Elsevier BV [doi]
(last updated on 2019/05/19)
Abstract: We analyze a sublinear RAℓSFA (randomized algorithm for Sparse Fourier analysis) that finds a nearoptimal Bterm 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 [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, NearOptimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost poly (log(N)) should be compared with the superlinear Ω(N log N) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RAℓSFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, NearOptimal Sparse Fourier Representations via Sampling, STOC, 2002], turns out to be very slow in practice. Our main result is a greatly improved and practical RAℓSFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RAℓSFA constructs, with probability at least 1  δ, a nearoptimal Bterm representation R in time poly(B) log(N) log(1/δ)/ε2 log(M) such that ∥S  R∥22 ≤ (1 + ε) ∥S  Ropt∥22. Furthermore, this RAℓSFA 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 ≃ 70, 000 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. © 2005 Elsevier Inc. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

