UTCS Colloquia - Algorithms and Computation Theory seminar - Eric Price, MIT, "Fast RIP Matrices with Fewer Measurements" GDC 4.516

Contact Name: 
Greg Plaxton
GDC 4.516
Apr 5, 2013 11:00am - 12:00pm


Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Host: Greg Plaxton

Talk Abstract: The goal of compressive sensing is to recover a K-sparse approximation of a vector x in R^N from the linear projection Ax, where A is an M x N matrix for M << N.  This problem has a wide variety of applications, including streaming algorithms, image acquisition, and genetic testing.

The Restricted Isometry Property (RIP) is a well studied condition on A that allows for sparse recovery via a variety of recovery algorithms, including L1 minimization and various iterative methods. The time required for these recovery algorithms is dominated by the time required to multiply A with a vector this motivates the search for RIP matrices with small M and nearly linear multiplication time.

We give two constructions of such "fast RIP matrices" with M = O(K log^3 N) rows.  This is the first improvement since [Rudelson-Vershynin '06] achieved M = O(K log^4 N), and our bound is log^2 N away from the optimal "slow" RIP matrix.  Due to a connection between RIP matrices and the Johnson-Lindenstrauss lemma [Krahmer-Ward '11], our constructions also give fast Johnson-Lindenstrauss embeddings with fewer rows than previously known.

This talk will focus on the techniques used to get our result.  We rely on some powerful theorems in Gaussian process theory, especially a recent result on the suprema of subgaussian chaos processes [Krahmer-Mendelson-Rauhut '12].

Joint work with Jelani Nelson and Mary Wootters.  Available at http://arxiv.org/abs/1211.0986 .

Speaker Bio: Eric Price is currently finishing his PhD at MIT under the supervision of Piotr Indyk.  He received Bachelor's degrees in Computer Science and Mathematics from MIT.  His research interests include sparse recovery, data structures, and information theory. Eric received a 2009 NSF Graduate Research Fellowship and a 2012 Simons Graduate Fellowship.