Eric Price, "Fast RIP Matrices with Fewer Measurements"

Room: 
Room: GDC 4.516
Contact Name: 
Judie Daniel
Date: 
Apr 5, 2013 10:30am - 12:30pm

Speaker: Eric Price

Talk title: Fast RIP Matrices with Fewer Measurements

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 .