Mark Iwen, Michigan State University
Talk Title: “Low-Distortion Embeddings of Submanifolds of R^n: Lower Bounds, Upper Bounds, and Terminal Embeddings”
Abstract: Let M be a smooth submanifold of 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 →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). Next, we will discuss a new class of linear maps for embedding arbitrary (infinite) subsets of 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 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. Time permitting, we will then conclude with a discussion of non-linear so-called “terminal embeddings” of manifolds which allow for extensions of the famous Johnson-Lindenstrauss Lemma beyond what any linear map can achieve.