  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.
