Structure preservation via the Wasserstein distance

Abstract

We show that under minimal assumptions on a random vector $X\in {\mathbb{R}}^d$ and with high probability, given $m$ independent copies of $X$, the coordinate distribution of each vector $(⟨X_i,\hat{I}¸⟩{)}_{i=1}^m$ is dictated by the distribution of the true marginal $⟨X,\hat{I}¸⟩$. Specifically, we show that with high probability, \[\sup_{θ\in S^{d-1}} \left( \frac{1}{m}\sum_{i=1}^m \left|\langle X_i,θ\rangle^\sharp - λ^θ_i \right|^2 \right)^{1/2} \leq c \left( \frac{d}{m} \right)^{1/4},\] where $\hat{I}{»}^{\hat{I}}{¸}_i=m{\int }_{(\frac{i-1}{m},\frac{i}{m}]}{F}_{⟨X,\hat{I}¸⟩}^{-1}(u)du$ and $a^{♯}$ denotes the monotone non-decreasing rearrangement of $a$. Moreover, this estimate is optimal. The proof follows from a sharp estimate on the worst Wasserstein distance between a marginal of $X$ and its empirical counterpart, $\frac{1}{m}{\sum }_{i=1}^m\hat{I}{´}_{⟨X_i,\hat{I}¸⟩}$.

Original paper [v1] was split into two papers. Here is the first part. Second part is now called "Optimal non-gaussian Dvoretzky-Milman embeddings"