Isometric sketching of any set via the Restricted Isometry Property
Abstract
In this paper we show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class includes several matrices for which matrix-vector multiply can be computed in log-linear time, providing efficient dimensionality reduction of general sets. In particular, we show that using such matrices any set from high dimensions can be embedded into lower dimensions with near optimal distortion. We obtain our results by connecting dimensionality reduction of any set to dimensionality reduction of sparse vectors via a chaining argument.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 07, 2018
- Source ID
- 10.1093/imaiai/iax019
Entities
People
- Benjamin Recht
- Mahdi Soltanolkotabi
- Samet Oymak
Organizations
- Air Force Office of Scientific Research
- Defense Advanced Research Projects Agency
- National Science Foundation Office of the Director
- Office of Naval Research
- University of California, Berkeley
- University of Southern California