Random projections of smooth manifolds.(English)Zbl 1172.53005

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.

MSC:

 53A07 Higher-dimensional and -codimensional surfaces in Euclidean and related $$n$$-spaces 62H99 Multivariate analysis 65C99 Probabilistic methods, stochastic differential equations 68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) 68T05 Learning and adaptive systems in artificial intelligence 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 94A29 Source coding
Full Text: