We analyze a sublinear RA\( \ell \)SFA (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 \( \operatorname{poly}(B \), \( \log(N)) \), following the approach given in [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost \( \operatorname{poly}(B \), \( \log(N)) \) should be compared with the superlinear \( \Omega(N\log N) \) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RA\( \ell \)SFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal 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\( \ell \)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\( \ell \)SFA constructs, with probability at least \( 1-\delta \), a near-optimal \( B \)-term representation \( R \) in time
\[ \operatorname{poly}(B)\log(N)\log(1/\delta)/\epsilon^2 \log(M) \]
such that
\[ \|S-R\|_2^2 \leq (1+\epsilon)\|S-R_{\mathrm{opt}}\|_2^2 .\]
Furthermore, this RA\( \ell \)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\simeq \) \( 70{,}000 \) in one dimension, and at \( N\simeq \) 900 for data on a \( N{\times}N \) grid in two dimensions for small \( B \) signals where there is noise.
