Unraveling the Veil of Subspace RIP Through Near-Isometry on Subspaces

Dimensionality reduction is a popular approach to tackle high-dimensional data with low-dimensional nature. Subspace Restricted Isometry Property, a newly-proposed concept, has proved to be a useful tool in analyzing the effect of dimensionality reduction algorithms on subspaces. In this paper, we provide a characterization of subspace Restricted Isometry Property, asserting that matrices which act as a near-isometry on low-dimensional subspaces possess subspace Restricted Isometry Property. This points out a unified approach to discuss subspace Restricted Isometry Property. Its power is further demonstrated by the possibility to prove with this result the subspace RIP for a large variety of random matrices encountered in theory and practice, including subgaussian matrices, partial Fourier matrices, partial Hadamard matrices, partial circulant/Toeplitz matrices, matrices with independent strongly regular rows (for instance, matrices with independent entries having uniformly bounded $4+\epsilon$ moments), and log-concave ensembles. Thus our result could extend the applicability of random projections in subspace-based machine learning algorithms including subspace clustering and allow for the application of some useful random matrices which are easier to implement on hardware or are more efficient to compute.
Comment: 40 pages, 2 figures