Theory Seminar
For-all Sparse Recovery in Near-Optimal Time
Add to Google Calendar
A for-all sparse recovery system is a matrix Phi and recovery
algorithm R. An adversary, seeing Phi, produces a vector x; the
recovery system returns R(Phi*x) that is supposed to recover,
approximately, the large components of x. Ideally, the number of rows
in Phi is k*log(N/k), where N is the dimension of x and k << N is,
roughly, the number of large components of x, that are to be returned
in R(Phi*x).
In this talk we give an algorithm that meets the conditions under
modest constraints on the parameters. We first introduce the problem
and place the algorithm in the context of the oft-cited works of
Donoho and Candes-Romberg-Tao.
Joint work with Anna C. Gilbert, Yi Li, and Ely Porat
Martin J. Strauss is Professor of Mathematics and of EECS at the
University of Michigan. He has published in Complexity Theory,
Database, Cryptography, and Algorithms. He is currently interested in
Sustainable Energy.