##### Department of Mathematics,

University of California San Diego

****************************

### Department Colloquium

## Mark Iwen

#### MSU

## Low-Distortion Embeddings of Submanifolds of $\mathbb{R}^n$: Lower Bounds and Faster Realizations

##### 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* → $\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).

Host: Rayan Saab

### April 14, 2022

### 4:00 PM

Zoom ID: **964 0147 5112 **

Password: **Colloquium **

****************************