Theory Seminar

For-all Sparse Recovery in Near-Optimal Time

Martin Strauss

University of Michigan
Friday, November 22, 2013
10:30am - 11:30am
BBB 3941

Add to Google Calendar

About the Event

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.

Additional Information

Contact: Grant Schoenebeck

Sponsor(s): CSE

Open to: UM Only