For-all Sparse Recovery in Near-Optimal Time

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.