Type of Talk:  UTCS Colloquium

Speaker/Affiliati

on: Piotr Indyk/MIT

Date/Time:  Friday, March 6, 2009 2:00 p.

m.

Location: TAY 3.128

Host: David Zuckerman

Talk Title:

"Sparse Recovery Using Sparse Random Matrices" 

Ta

lk Abstract:

Over the recent years, a new *linear* method for compre

ssing high-dimensional data (e.g., images) has been discovered. For any hi

gh-dimensional vector x, its *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 enou

gh information to recover an *approximation* to x. At the same time, the l

inearity of the sketching method is very convenient for many applications,
such as data stream computing and compressed sensing.

The major
sketching approaches can be classified as either combinatorial (using spar

se sketching matrices) or geometric (using dense sketching matrices). They

achieve different trade-offs, notably between the compression rate and the
running time. Thus, it is desirable to understand the connections between
them, with the goal of obtaining the "best of both worlds" so

lution.

In this talk we show that, in a sense, the combinatori

al and geometric approaches are based on different manifestations of the sa

me phenomenon.  This connection will enable us to obtain several nove

l algorithms and constructions, which inherit the advantages of sparse mat

rices, such as lower sketching and recovery times.

Joint work w

ith: Radu Berinde, Anna Gilbert, Howard Karloff, Milan Ruzic and Martin

Strauss.