Isometric sketching of any set via the Restricted Isometry Property
This provides an efficient method for dimensionality reduction of any set, which is incremental as it builds on existing techniques but improves computational efficiency.
The paper tackles the problem of dimensionality reduction for general sets by showing that structured random matrices with fast matrix-vector multiplication can embed high-dimensional sets into lower dimensions with near-optimal distortion, similar to random Gaussian matrices.
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.