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 |
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