On Fast Johnson-Lindenstrauss Embeddings of Compact Submanifolds of ℝ^N with Boundary
share
Let ℳ be a smooth d-dimensional submanifold of ℝ^N with boundary that's equipped with the Euclidean (chordal) metric, and choose m ≤ N. In this paper we consider the probability that a random matrix A ∈ℝ^m × N will serve as a bi-Lipschitz function A: ℳ→ℝ^m with bi-Lipschitz constants close to one for three different types of distributions on the m × N matrices A, including two whose realizations are guaranteed to have fast matrix-vector multiplies. In doing so we generalize prior randomized metric space embedding results of this type for submanifolds of ℝ^N by allowing for the presence of boundary while also retaining, and in some cases improving, prior lower bounds on the achievable embedding dimensions m for which one can expect small distortion with high probability. In particular, motivated by recent modewise embedding constructions for tensor data, herein we present a new class of highly structured distributions on matrices which outperform prior structured matrix distributions for embedding sufficiently low-dimensional submanifolds of ℝ^N (with d ≲√(N)) with respect to both achievable embedding dimension, and computationally efficient realizations. As a consequence we are able to present, for example, a general new class of Johnson-Lindenstrauss embedding matrices for 𝒪(log^c N)-dimensional submanifolds of ℝ^N which enjoy 𝒪(N log (log N))-time matrix vector multiplications.
READ FULL TEXT