Theoretical and Experimental Analysis of a Randomized Algorithm for Sparse Fourier Transfor.pdfVIP

THEORETICAL AND EXPERIMENTAL ANALYSIS OF A RANDOMIZED ALGORITHM FOR SPARSE FOURIER TRANSFORM ANALYSIS ∗ JING ZOU† , ANNA GILBERT ‡ , MARTIN STRAUSS § , AND INGRID DAUBECHIES ¶ Abstract. We analyze a sublinear RAℓ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 poly (B, log(N )), following the approach given in [3]. 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 [3], turns out to be very slow in practice. Our main result 5 is a greatly improved and practical RAℓSFA. We introduce several new ideas and techniques that speed up the 0 algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RAℓSFA constructs, 0 with probability at least 1 − δ, a near-optimal B-term representation R in time poly (B) log(N ) log(1/δ)/ǫ2 log(M ) 2 2 2 such that S − R ≤ (1 + ǫ)S − Ropt . Furthermore, this RAℓSFA implementation already beats the FFTW for 2 2 n not unreasonably large N . We extend the algorithm to higher dimensional cases both theoretically and numerically. u The crossover point lies at N ≃ 70000 in one dimension, and at N ≃ 900 for data on a N ×N grid in two dimensions J for small B signals where there is n