Beating the B^2 bottleneck in estimating B-term Fourier representations

Anna Gilbert
University of Michigan

We study the problem of finding a Fourier representation of B terms for a given discrete signal of length N. The Fast Fourier Transform (FFT) can find the optimal N-term representation in O(Nlog N) time, but our goal is to get sublinear algorithms for B < N, typically B << N. This is joint work with S. Muthukrishnan and M. Strauss.

Back to MGA Workshop II: Multiscale Geometry in Scientific Computing