Eric Price, "Fast RIP Matrices with Fewer Measurements"
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 .
- 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