UTCS Colloquium: Piotr Indyk/MIT: "Sparse Recovery Using Sparse Random Matrices" TAY 3.128, Friday, March 6, 2009 2:00 p.m.
Type of Talk: UTCS Colloquium
on: Piotr Indyk/MIT
Date/Time: Friday, March 6, 2009 2:00 p.
Location: TAY 3.128
Host: David Zuckerman
"Sparse Recovery Using Sparse Random Matrices"
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.
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
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
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct