[CSDM] [pvsnp-all] Jelani Nelson at theory lunch Friday 4/26

[Mark Braverman]

Usual time (lunch @11:45, talk @12:05) and place (Computer Science building 402). 

Title: New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows

Abstract:

Many off-the-shelf algorithms for compressed sensing, like linear
programming, rely on the compressed sensing matrix satisfying a
sufficient condition called the "Restricted Isometry Property" (RIP).
These algorithms also run faster if the compressed sensing matrix
supports fast matrix-vector multiplication---for example, if it
consists of random rows of a DFT. However, showing that the Fourier
ensemble has the RIP with an optimal number of measurements appears to
be a very difficult problem. In this talk, I will present some
progress: we show that a matrix whose rows are sparse linear
combinations of Fourier measurements has the RIP with fewer rows than
previous constructions. Our results give RIP matrices supporting fast
multiplication with fewer rows than previously known, and also imply
improved fast Johnson-Lindenstrauss transforms.

This is joint work with Eric Price (MIT) and Mary Wootters (UMich).
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all