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
Abstract:
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.