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.