Time and Location:   March 24, 2004, 2-3:00pm, Room 1314.

Title:     Improved time bounds for near-optimal sparse Fourier representations

Speaker:     Martin J. Strauss, AT&T Labs and University of Michigan


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.