Martin Strauss

!!!! Change of Location !!!!
!!!! This talk will be in Room FINE 214 (second floor of Fine Hall) !!!!

Near-Optimal Sparse Fourier Representations via Sampling

Abstract:   We give an algorithm for finding 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.  Our algorithm can access A by reading
its values on a sample set T, chosen randomly from a (non-product)
distribution of our choice, independent of A.  That is, we sample
non-adaptively.  Ignoring precision issues, the total time cost of the
algorithm is polynomial in (B log(N) / epsilon), which implies a similar
bound for the number of samples.

Joint work with Anna Gilbert, Sudipto Guha, Piotr Indyk, and
S.Muthukrishnan.