<div dir="ltr"><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">Hi all,</span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">See below title and abstract for tomorrow's theory-lunch. </span></div>
<div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">** slightly different location/time** </span></div>
<div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><br></span></div><div><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">We will meet at room 302 (CS building). Lunch will be served at noon with the talk starting shortly after.</span></font></div>
<div><font face="arial, sans-serif"><span style="font-size:16.363636016845703px"><br></span></font></div><div><font face="arial, sans-serif"><span style="font-size:16.363636016845703px">-zeev</span></font></div><span style="font-family:arial,sans-serif;font-size:16.363636016845703px"><div>
<br></div><div>------</div>Title: Sample-Optimal Fourier Sampling (in Any Constant Dimension)</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px"><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">Speaker: Michael Kapralov, MIT</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px">
<br style="font-family:arial,sans-serif;font-size:16.363636016845703px"><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">Abstract:</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px">
<span style="font-family:arial,sans-serif;font-size:16.363636016845703px">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</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px">
<span style="font-family:arial,sans-serif;font-size:16.363636016845703px">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.</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px">
<br style="font-family:arial,sans-serif;font-size:16.363636016845703px"><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">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.</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px">
<br style="font-family:arial,sans-serif;font-size:16.363636016845703px"><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">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.</span><br style="font-family:arial,sans-serif;font-size:16.363636016845703px">
<br style="font-family:arial,sans-serif;font-size:16.363636016845703px"><span style="font-family:arial,sans-serif;font-size:16.363636016845703px">(joint work with Piotr Indyk)</span><br></div>