[CSDM] Michael Kapralov at theory lunch tomorrow. (room 302 !, lunch starting at noon)

[Zeev Dvir]

Hi all,

See below title and abstract for tomorrow's theory-lunch.

** slightly different location/time**

We will meet at room 302 (CS building). Lunch will be served at noon with
the talk starting shortly after.

-zeev

------
Title: Sample-Optimal Fourier Sampling (in Any Constant Dimension)
Speaker: Michael Kapralov, MIT

Abstract:
We present an algorithm that computes a k-sparse approximation to any
signal from O(k\log N) Fourier measurements of the signal. This matches the
known lower
bound of O(k \log(N/k)) up to constant factors for any k\leq N^{1-\delta}.
The algorithm runs in near-linear time, and provides the so-called
\ell_2/\ell_2 guarantee. Our algorithm extends to higher dimensions,
leading to sample complexity of O_d(k\log N), which is again optimal up to
constant factors for any constant d.  This is the first sample optimal
algorithm for these problems.

Using similar techniques, we also obtain an algorithm with slightly
suboptimal sample complexity O(k\log N (\log\log N)^2) and a sub-linear
time O(k \log^{O(1)} N) for any constant d. This generalizes the result of
[IKP] to higher dimensions.

We also present preliminary experimental evaluation of our sample-optimal
near-linear time algorithm, indicating that the empirical sampling
complexity of the algorithm is comparable to that of other recovery methods
known in the literature, while providing strong provable guarantees on the
recovery quality.

(joint work with Piotr Indyk)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20140220/8b4b8b9e/attachment-0001.html>