We give an algorithm for finding, with high probability, a Fourier

representation R of B terms for a given discrete signal A of length N,

such that

||A-R||
<= (1+epsilon)||A-Ropt||,

where Ropt is the best such representation, under L2 norm ||*||.

Previous randomized algorithms solved this problem in time

polynomial in (B*log(N)/epsilon), which is exponentially

faster than the exact, deterministic FFT algorithm for a

full Fourier decomposition. (In particular, these

algorithms cannot read the entire signal; they sample the

signal.) Our new algorithm improves the time cost

dependence on B from quartic or so to linear.

Joint work with Anna Gilbert and S. Muthukrishnan.