•We study the problem of finding a Fourier representation R of m terms for a given discrete signal A of length N. The Fast Fourier Transform (FFT) can find the optimal N-term representation in time O(N log N) time, but our goal is to get sublinear time algorithms when m << N. Suppose ||A||₂ ≤M||A-R_opt||₂, where R_opt is the optimal output. The previously best known algorithms output R such that ||A-R||²₂≤(1+ε))||A-R_opt||²₂ with probability at least 1-δ in time* poly(m,log(1/δ),log N,log M,1/ε). Although this is sublinear in the input size, the dominating expression is the polynomial factor in m which, for published algorithms, is greater than or equal to the bottleneck at m² that we identify below. Our experience with these algorithms shows that this is serious limitation in theory and in practice. Our algorithm beats this m² bottleneck. Our main result is a significantly improved algorithm for this problem and the d-dimensional analog. Our algorithm outputs an R with the same approximation guarantees but it runs in time m•poly(log(1/δ),log N,log M,1/ε). A version of the algorithm holds for all N, though the details differ slightly according to the factorization of N. For the d-dimensional problem of size N₁ × N₂ × •• × N_d, the linear-in-m algorithm extends efficiently to higher dimensions for certain factorizations of the N_i's; we give a quadratic-in-m algorithm that works for any values of N_i's. This article replaces several earlier, unpublished drafts.

Date Published: 21 September 2005
PDF: 15 pages
Proc. SPIE 5914, Wavelets XI, 59141A (21 September 2005); doi: 10.1117/12.615931

Published in SPIE Proceedings Vol. 5914:
Wavelets XI
Manos Papadakis; Andrew F. Laine; Michael A. Unser, Editor(s)