Random Projection for Manifold Learning

by Chinmay Hedge and Michael B. Wakin and Richard G. Baraniuk

This paper tells us that we may project the data from a higher dimensional space (n dimensions) into a random subspace (m dimensions) and we will not lose much information of the intrinsic structural information. Therefore we may apply one of the manifold learning algorithms to the randomly-projected data and still recover their structure in a proper space (d dimensions). And d < m << n and m = O(d log n).

The first theorem comes from RIP satisfaction, when

m \geq O\left( \frac{d \log (n V \tau^{-1}) \log(\rho^{-1})}{\epsilon^2}\right)

with probability no less than 1-ρ, for any x, z, we have

(1 - \epsilon) \sqrt{\frac{m}{n}} \leq \frac{d_i( \Phi x, \Phi z)}{d_i( x, z )} \leq (1 - \epsilon) \sqrt{\frac{m}{n}},

where Φ is the random orthogonal projection, V is the volume and 1/τ is the condition number of the latent manifold. To estimate the intrinsic dimensions, the author propose to employ Grassberger-Procaccia algorithm (based on correlation). They found bounds for the estimated dimensions: when

m \geq O\left( \frac{d \log( n V \tau^{-1}) \log (\rho^{-1})}{\beta^2 \delta^2} \right),

then the estmated correlation dimension satisfies

(1 - \delta) \hat{d} \leq \hat{d}_\Phi \leq (1 + \delta) \hat{d},

with probability exceeding 1-ρ. And the residual variance of the ISOMAP embedding is also bounded

R_\Phi \leq R + C \Gamma^2 \epsilon,

where Γ is the diameter of the point cloud.

Since in practice we are not sure about the intrinsic dimensionality, we usually try to add more orthogonal vectors and see whether the residual variance is small enough.

Well it is atypical way of applying CS in machine learning. Put all data in a random projection subspace and prove there are bounds for later learning algorithms. It is not the way I'd like to use CS.