Random projections of smooth manifolds (Q1029551)

Consider a compact \(K\)-dimensional Riemannian submanifold \({\mathcal M} \subset\mathbb R^N\) and denote by \(\Phi\) a random orthoprojection operator from \(\mathbb R^N\) onto \(\mathbb R^M\). The main theorem of this article states that with probability at least \(1-\rho\) the distance (or geodesic distance) between any two points \(x\), \(y\in{\mathcal M}\) is roughly preserved by \(\Phi\) provided \[ M = O\biggl(\frac{K \log(NVR\tau^{-1}\varepsilon^{-1})\log(1/\rho)}{\varepsilon^2}\biggr) \leq N. \] In this formula \(V\) is the volume of \({\mathcal M}\), \(R\) its geodesic covering regularity, and \(1/\tau\) its condition number. The positive real \(\varepsilon\) determines the desired accuracy of length preservation. An explicit bound (not just the order of magnitude) for \(M\) can be extracted from the proof. This result is similar to a theorem by Johnson and Lindenstrauss on distance preservation under random orthoprojections of a finite point cloud. The article also contains an introduction to applications of ``dimension reduction techniques'' in general and a discussion of ideas for the application of the above result in the context of compressed sensing and manifold learning.