Let M be a smooth submanifold of $\mathbb{R}^n$ equipped with the Euclidean(chordal) metric. This talk will consider the smallest dimension, m, for which there exists a bi-Lipschitz function f : M → $\mathbb{R}^m$ with biLipschitz constants close to one. We will begin by presenting a bound for the embedding dimension m from below in terms of the bi-Lipschitz constants of f and the reach, volume, diameter, and dimension of M. We will then discuss how this lower bound can be applied to show that prior upper bounds by Eftekhari and Wakin on the minimal low-distortion embedding dimension of such manifolds using random matrices achieve near-optimal dependence on dimension, reach, and volume (even when compared against nonlinear competitors). Next, we will discuss a new class of linear maps for embedding arbitrary (infinite) subsets of $\mathbb{R}^n$ with sufficiently small Gaussian width which can both (i) achieve near-optimal embedding dimensions of submanifolds, and (ii) be multiplied by vectors in faster than FFT-time. When applied to d-dimensional submanifolds of $\mathbb{R}^n$ we will see that these new constructions improve on prior fast embedding matrices in terms of both runtime and embedding dimension when d is sufficiently small.

This is joint work with Benjamin Schmidt (MSU) and Arman Tavakoli (MSU).