Return to Colloquia & Seminar listing
Improved Time Bounds for Near-Optimal Sparse Fourier Representations
Applied Math| Speaker: | Martin Strauss, University of Michigan |
| Location: | 1147 MSB |
| Start time: | Fri, Mar 3 2006, 4:10PM |
Description
We give a randomized algorithm that, given a discrete signal
of length N and parameters t and epsilon, finds a t-term
Fourier representation whose L2 error is at most 1+epsilon
times worse than optimal.
Previous randomized algorithms solved this problem in time
polynomial in (t*log(N)/epsilon), which, for small t, is
exponentially faster than the exact, deterministic FFT
algorithm for a full Fourier decomposition. (In particular,
these randomized algorithms cannot read the entire signal;
they sample the signal.) Our new algorithm improves the
time cost dependence on t from quartic or so to linear.
Joint work with Anna Gilbert and S. Muthukrishnan. Some of
this work was done while the speaker was at ATT Labs.
Biography:
Martin J. Strauss is an assistant professor in the math and EECS
departments of the University of Michigan. He holds an A.B. degree
from Columbia University and a PhD from Rutgers University, both in
mathematics, and spent a year at Iowa