The Weizmann Institute of Science Faculty of Mathematics and Computer Science Foundations of Computer Science Seminar Seminar Room, Room 261, Ziskind Building on Monday, December 17, 2012 14:30 - 15:30 Eric Price MIT will speak on Algorithms and Lower Bounds for Adaptive Sparse Recovery Abstract: The goal of stable sparse recovery or compressive sensing is to recover a $K$-sparse approximation $x^*$ of a vector $x$ in $R^N$ from $M$ linear measurements of $x$. This problem has a wide variety of applications, including streaming algorithms, image acquisition, and genetic testing. In this talk, we will give upper and lower bounds for this problem. For the nonadaptive setting, where all the measurements must be chosen independent of x, we use information theory to give a lower bound showing $M = \Theta(K log (N/K))$ is optimal. In the adaptive setting, where each measurement may be based on the results of previous measurements, we show that $M = O(K log log (N/K))$ is possible, an exponential improvement in $N/K$. We further show that, for $K = 1$, $\Theta(log log N)$ measurements is tight in the adaptive setting. These results contain joint work with David Woodruff and Piotr Indyk from FOCS 2011 and SODA 2013. They are available at <http://arxiv.org/abs/1110.3850> and <http://arxiv.org/abs/1205.3518> --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Yaeli Malka <yaeli.malka@weizmann.ac.il>