Let $\mathcal{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: \mathcal{M} → \mathbb{R}^m$ with bi-Lipschitz 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 $\mathcal{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 $n$-dimensional vectors in $o(n \log n)$-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 talk will draw on joint work with Benjamin Schmidt (MSU) and Arman Tavakoli (MSU).