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>