Departmental Colloquium

Title

Low-Distortion Embeddings of Submanifolds of $R^n$: Lower Bounds, Faster Realizations, and Terminal Embeddings

Abstract

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 \to \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 $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). Using this as motivation, we will then discuss non-linear so-called “terminal embeddings” of sets which allow for powerful extensions of the famous Johnson-Lindenstrauss Lemma beyond what any linear map can achieve. In addition to nearly preserving all distances within a set, these extensions also nearly preserve all distances from outside the set to elements in the set, all while remaining continuous! If you haven’t seen them before, come and meet them — you won’t regret it.

This talk will draw on joint work with various subsets of Rafael Chiclana Vega, Mark Roach, Benjamin Schmidt, and Arman Tavakoli.