Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For a high-dimensional vector x, its compressed version (a.k.a. "sketch") is equal to Ax, where A is an m x n matrix (possibly chosen at random). Although typically the sketch length m is much smaller than the number of dimensions n, the sketch contains enough information to recover a good "sparse approximation" to x. At the same time, the linearity of the sketching method is very convenient for many areas, such as data stream computing and compressive sensing.

 

In this talk we survey sparse recovery results that utilize *sparse* matrices A. Such matrices have several attractive properties: they support algorithms with low computational complexity, and make it easy to perform incremental updates to vectors x.

 

The talk is based on a survey (with Anna Gilbert), available at http://people.csail.mit.edu/indyk/survey-10.pdf.

 

 

Piotr Indyk received the M.S. degree from Uniwersytet Warszawski, Warsaw, Poland, in 1995 and the Ph.D. degree from Stanford University, Stanford, CA, in 2000, both in computer science. Currently, he is an Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology (MIT), Cambridge. His research interests include high-dimensional (computational) geometry, sketching and streaming algorithms, sparse recovery

and compressive sensing.