Unraveling the Veil of Subspace RIP Through Near-Isometry on Subspaces
This extends the applicability of random projections in subspace-based machine learning algorithms, such as subspace clustering, by allowing the use of more hardware-friendly or computationally efficient matrices.
The paper tackled the problem of characterizing the Subspace Restricted Isometry Property (RIP) by showing that matrices acting as near-isometries on low-dimensional subspaces possess subspace RIP, enabling proofs for a wide range of random matrices like subgaussian and partial Fourier matrices.
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+ε$ 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.