AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In the Sparse Fourier Transform problem, we are given oracle access to a vector x, and the goal is to compute the k largest in magnitude Fourier coefficients of x. Typically the goal is to minimize the number of samples (oracle accesses) and the running time of the algorithm. Our focus in this talk will be the sample complexity (#oracle acceses) in the d-dimensional case, for which previous work either suffered from an exponential dependence on d, or recovered the k largest Fourier coefficients only in an average sense. What we will show is that obtaining the best of both worlds is possible; the crux of our argument is a novel technique for re-using samples in (a specific form of) iterative procedures.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak

--email hidden

passcode not visible

logged in users only

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.