---
abstract: 'In this note, we study the $n \times n$ random Euclidean matrix whose entry $(i,j)$ is equal to $f ( \| X_i - X_j \|  )$ for some function $f$ and the $X_i$’s are i.i.d. isotropic vectors in ${\mathbb{R}}^p$. In the regime where $n$ and $p$ both grow to infinity and are proportional, we give some sufficient conditions for the empirical distribution of the eigenvalues to converge weakly. We illustrate our result on log-concave random vectors.'
address: 'CNRS & Université de Toulouse, Institut de Mathématiques de Toulouse, 118 route de Narbonne, 31062 Toulouse, France'
author:
- Charles Bordenave
bibliography:
- 'mat.bib'
title: On Euclidean random matrices in high dimension
---

Introduction
============

Let $Y$ be an *isotropic* random vector in ${\mathbb{R}}^p$, i.e. ${\mathbb{E}}Y = 0$, ${\mathbb{E}}[ Y Y^T ]  = I / p $, where $I$ is the identity matrix. Let $(X_1, \cdots, X_n)$ be independent copies of $Y$. We define the $n \times n$ matrix $A$ by, for all $1 {\leqslant}i , j {\leqslant}n$, $$A_{i j } =f ( \| X_i - X_j \| ^2 ),$$ where $f : [ 0, \infty) \to {\mathbb{R}}$ is a measurable function and $\| \cdot \|$ denotes the Euclidean norm. The matrix $A$ is a random Euclidean matrix. It has already attracted some attention see e.g. Mézard, Parisi and Zhee [@MR1724455], Vershik [@MR2086637] or Bordenave [@MR2462254] and references therein.

If $B$ is a symmetric matrix of size $n$, then its eigenvalues, say $\lambda_1(B), \cdots, \lambda_n(B)$ are real. The empirical spectral distribution (ESD) of $B$ is classically defined as $$\mu_B = \frac 1 n \sum_{i=1} ^ n \delta_{\lambda_i(B)},$$ where $\delta_x$ is the Dirac delta function at $x$. In this note, we are interested in the asymptotic convergence of $\mu_A$ as $p$ and $n$ converge to $+\infty$. This regime has notably been previously considered in El Karoui [@MR2589315] and Do and Vu [@DoVu]. More precisely, we fix a sequence $p(n)$ such that $$\begin{aligned}
\label{eq:povern}
\lim_{n \to \infty} \frac{ p(n) }{ n }  =  y \in (0, \infty).\end{aligned}$$ Throughout this note, we consider, on a common probability space, an array of random variables $(X_k(n))_{ 1 {\leqslant}k {\leqslant}n}$ such that $(X_1(n), \cdots, X_n(n))$ are independent copies of $Y(n)$, an isotropic vector in ${\mathbb{R}}^{p(n)}$. For each $n$, we define the Euclidean matrix $A(n)$ associated. For ease of notation, we will often remove the explicit dependence in $n$: we write $p$, $Y$, $X_k$ or $A$ in place of $p(n)$, $Y(n)$, $X_k (n)$ or $A(n)$.

The Marcenko-Pastur probability distribution with parameter $1/y$ is given by $$\nu_{MP}  (dx) =  (1 - y )^+ \delta_0 (dx) +  \frac{ y } { 2 \pi x } \sqrt { (y_+ - x) ( x - y_-) } {\mathbf{1}}_{ [ y_- , y_+] } (x) dx,$$ where $x^+ = ( x \vee 0)$, $y_ {\pm} = ( 1  \pm \frac 1  {\sqrt y }) ^2$ and $dx$ denotes the Lebesgue measure. Since the celebrated paper of Marcenko and Pastur [@MR0208649], this distribution is known to be closely related to empirical covariance matrices in high-dimension.

We say that $Y$ has a *log-concave distribution*, if $Y$ has a density on ${\mathbb{R}}^p$ which is log-concave. Log-concave random vectors have an increasing importance in convex geometry, probability and statistics (see e.g. Barthe [@MR2648682]). We will prove the following result.

\[th:main\] If $Y$ has a log-concave distribution and $f$ is three times differentiable at $2$, then, almost surely, as $n \to \infty$, $
\mu_{A}$ converges weakly to $\mu$, the law of $f(0 ) - f(2) +2 f'(2) - 2 f'(2) S$, where $S$ has distribution $\nu_{MP}$.

With the weaker assumption that $f$ is differentiable at $2$, Theorem \[th:main\] is conjectured in Do and Vu [@DoVu]. Their conjecture has motivated this note. It would follow from the thin-shell hypothesis which asserts that there exists $c > 0$, such that for any isotropic log-concave vector $Y$ in ${\mathbb{R}}^p$, ${\mathbb{E}}(\| Y\| -1 )^2 {\leqslant}c/p$ (see Anttila, Ball and Perissinaki [@MR1997580] and Bobkov and Koldobsky [@MR2083387]). Klartag [@MR2520120] has proved the thin-shell hypothesis for isotropic unconditional log-concave vectors.

The proof of Theorem \[th:main\] will rely on two recent results on log-concave vectors. Let $X = X(n) $ be the $n \times n$ matrix with columns given by $(X_1(n), \cdots, X_n (n))$. Pajor and Pastur have proved the following :

\[th:PP\] If $Y$ has a log-concave distribution, then, in probability, as $n \to \infty$, $ \mu_{ X  ^T X }$ converges weakly to $ \nu_{MP}$.

We will also rely on a theorem due to Guédon and Millman.

\[th:GM\] There exist positive constants $c_0, c_1$ such that if $Y$ is an isotropic log-concave vector in ${\mathbb{R}}^p$, for any $t {\geqslant}0$, $${\mathbb{P}}{{{\left( {{{\left|   \| Y \| - 1  \right|}}} {\geqslant}t  \right)}}} {\leqslant}c_1 \exp {{{\left(  - c_0 \sqrt p {{{\left( t \wedge t^3 \right)}}} \right)}}}.$$

With Theorems \[th:PP\] and \[th:GM\] in hand, the heuristic behind Theorem \[th:main\] is simple. Theorem \[th:GM\] implies that $\|X_i \|^2 \simeq 1$ with high probability. Hence, since $\| X_i  - X_j \|^2  = \|X_i \|^2 + \|X_j \|^2 - 2 X_i ^T X_j $, a Taylor expansion of $f$ around $2$ gives $$A_{i j } \simeq \left\{ \begin{array}{ll}
f ( 2 ) - 2 f' (  2) X_i ^T X_j  & \hbox{ if }  i \ne j \\
f(0) & \hbox{ if }  i = j.
\end{array} \right.$$ In other words, the matrix $A$ is close to the matrix $$\label{eq:defM}
M  = ( f(0) - f(2) + 2 f'(2)  ) I + f ( 2 ) J  - 2 f'(2) X^T X,$$ where $I$ is the identity matrix and $J$ is the matrix with all entries equal to $1$. From Theorem \[th:PP\], $\mu_{X^TX}$ converges weakly to $\nu_{MP}$. Moreover, since $J $ has rank one, it is negligible for the weak convergence of ESD. It follows that $\mu_{M}$ is close to $\mu$. The actual proof of Theorem \[th:main\] will be elementary and it will follow this heuristic. We shall use some standard perturbation inequalities for the eigenvalues. The idea to perform a Taylor expansion was already central in [@MR2589315; @DoVu].

Beyond Theorems \[th:PP\]-\[th:GM\], the proof of Theorem \[th:main\] is not related to log-concave vectors. In fact, it is nearly always possible to linearize $f$ as soon as the norms of the vectors concentrate around their mean. More precisely, let us say that two sequences of probability measures $(\mu_n)$, $(\nu_n)$, are asymptotically weakly equal, if for any bounded continuous function $f$, $\int f d \mu_n - \int f d \nu_n$ converges to $0$.

\[th:main2\] Assume that there exists an integer $\ell {\geqslant}1$ such that ${\mathbb{E}}{{{\left|  \| Y \| -1  \right|}}}^{2 \ell} = O ( p^{-1} )$, and that for any ${\varepsilon}> 0$, $$\label{eq:boundEE}
\lim_{n \to \infty} {\mathbb{P}}{{{\left( \max_{1 {\leqslant}i , j {\leqslant}n  } {{{\left\{ {{{\left|  \| X_i - X_j \|^2 -  2  \right|}}} \vee {{{\left|  \| X_i\| ^2 - 1 \right|}}} \right\}}}} {\leqslant}{\varepsilon}\right)}}} = 1.$$ Then, if $f$ is $\ell$ times differentiable at $2$, almost surely, $
\mu_{A}$ is asymptotically weakly equal to the law of $f(0 ) - f(2) +2 f'(2) - 2 f'(2) S$, where $S$ has distribution ${\mathbb{E}}\mu_{X^T X}$.

The case $\ell =1$ of the above statement is contained in Do and Vu [@DoVu Theorem 5]. Besides Theorem \[th:PP\], some general conditions on the matrix $X$ guarantee the convergence of $\mu_{X^T X}$, see Yin and Krishnaiah [@MR816299], G[ö]{}tze and Tikhomirov [@MR2092202] or Adamczak [@MR2820070].

Proofs
======

Perturbation inequalities
-------------------------

We first recall some basic perturbation inequalities of eigenvalues and introduce a good notion of distances for ESD. For $\mu$, $\nu$ two real probability measures, the *Kolmogorov-Smirnov distance* can be defined as $$\label{eq:KSdual}
d_{KS} ( \mu , \nu)    = \sup \left\{ \int f d \mu   - \int f d \nu  : \| f \|_{BV} {\leqslant}1 \right\},$$ where, for $f : {\mathbb{R}}\to {\mathbb{R}}$, the bounded variation norm is $
\| f \|_{BV}  = \sup \sum_{ k \in {\mathbb{Z}}} | f ( x_{k+1}) - f (x_k) |,  
$ and the supremum is over all real increasing sequence $(x_k)_{ k \in {\mathbb{Z}}}$. The following inequality is a classical consequence of the interlacing of eigenvalues (see e.g. Bai and Silverstein [@MR2567175 Theorem A.43]).

\[le:rank\] If $B$, $C$ are $n \times n$ Hermitian matrices, then, $$d_{KS} (\mu_B, \mu_C) {\leqslant}\frac{ {\mathrm{rank}}(  B - C )  }n.$$

For $p {\geqslant}1$, let $\mu$, $\nu$ be two real probability measures such that $\int |x|^p d \mu$ and $\int |x|^p d \nu$ are finite. We define the *$L^p$-Wasserstein distance* as $$\label{eq:defWp}
W_p ( \mu, \nu)  = {{{\left( \inf_\pi    \int_{{\mathbb{R}}\times {\mathbb{R}}} | x - y| ^p  d \pi   \right)}}} ^{\frac 1 p}$$ where the infimum is over all coupling $\pi$ of $\mu$ and $\nu$ (i.e. $\pi$ is probability measure on ${\mathbb{R}}\times {\mathbb{R}}$ whose first marginal is equal to $\mu$ and second marginal is equal to $\nu$). Hölder inequality implies that for $1 {\leqslant}p {\leqslant}q$, $W_p {\leqslant}W_{q}$. Moreover, the Kantorovich-Rubinstein duality gives a variational expression for $W_1$: $$\label{eq:KRdual}
W_1 (\mu, \nu) =  \sup \left\{ \int f d \mu   - \int f d \nu  : \| f \|_{L} {\leqslant}1 \right\},$$ where $\| f \|_L = \sup_{ x \ne y } |f(x) - f(y) | / |x- y| $ is the Lipschitz constant of $f$. The next classical inequality is particularly useful (see e.g. Anderson, Guionnet and Zeitouni [@AGZ Lemma 2.1.19]).

\[le:HW\] If $B$, $C$ are $n \times n$ Hermitian matrices, then $$W_2 ( \mu_B, \mu_C) {\leqslant}\sqrt{ \frac 1 n {\mathrm{tr}}( B - C)^2}.$$

We finally introduce the distance $$d ( \mu, \nu) = \sup {{{\left\{ \int f d \mu - \int f d \nu :  \| f \|_L {\leqslant}1  \hbox{ and } \| f \|_{BV} {\leqslant}1\right\}}}}.$$ By Lemmas \[le:rank\] and \[le:HW\], we obtain that for any $n \times n$ Hermitian matrices $B$, $C$, $$\label{eq:hehe}
d ( \mu_B , \mu _C) {\leqslant}\sqrt{ \frac 1 n {\mathrm{tr}}( B - C)^2} \wedge \frac{ {\mathrm{rank}}( B- C )  }n.$$ Notice that $d( \mu_n , \mu) \to 0$ implies that $\mu_n$ converges weakly to $\mu$.

Concentration inequality
------------------------

For $x  = ( x_1, \cdots, x_n  )  \in {\mathcal{M}}_{p , n} ({\mathbb{R}})$, define $a(x)$ as the Euclidean matrix obtained from the columns of $x$ : $a(x) _{ij} = f ( \| x_i - x_j \|^2)$. In particular, we have $A = a (X)$. Let $i \in \{1, \cdots, n\}$, $x' = (x'_1, \cdots, x'_n) \in {\mathcal{M}}_{p , n} ({\mathbb{R}})$ and assume that $x'_j = x_j$ for all $j \ne i$. Then $a(x)$ and $a(x')$ have all entries equal but the entries on the $i$-th row or column. We get $${\mathrm{rank}}( a(x) - a(x') ) {\leqslant}2.$$ It thus follows from Lemma \[le:rank\] that for any function $f$ with $\| f \|_{BV} < \infty$, $$\left| \int f d \mu_{a(x) }  - \int f d \mu_{a(x') } \right| {\leqslant}\frac { 2 \| f \|_{BV} } { n}.$$ Using Azuma-Hoeffding’s inequality, it is then straightforward to check that for any $t {\geqslant}0$, $$\label{eq:concineq}
{\mathbb{P}}{{{\left( \int f d \mu_{A }  - {\mathbb{E}}\int f d \mu_{A }  {\geqslant}t \right)}}} {\leqslant}\exp{{{\left(  - \frac {  n t ^2 }{ 8 \| f \|^2_{BV} } \right)}}}.$$ (For a proof, see [@MR2837123 proof of Lemma C.2] or Guntuboyina and Leeb [@MR2535081]). Using the Borel-Cantelli Lemma, this shows that for any such function $f$, a.s. $$\int f d \mu_{A }  -    \int f d {\mathbb{E}}\mu_{A } \to 0.$$

Now, recall that $M$ was defined by . Since the matrix $J$ has rank one, from Theorem \[th:PP\] and Lemma \[le:rank\], ${\mathbb{E}}\mu_M$ converges weakly to $\mu$. Hence our Theorem \[th:main\] is a corollary of the following proposition.

\[prop:main\] Under the assumptions of Theorem \[th:main\], we have $$\lim_{n \to \infty} d {{{\left( {\mathbb{E}}\mu_{A} , {\mathbb{E}}\mu_{M} \right)}}} = 0.$$

Proof of Proposition \[prop:main\]
----------------------------------

The idea is to perform a multiple Taylor expansion which takes the best out of .

### Step 1 : concentration of norms {#step-1-concentration-of-norms .unnumbered}

By assumption, there exists an open interval $K  = (2 - \delta , 2 + \delta)$ such that $f$ is $C^1$ in $K$ and, for any $x \in K$, $$f( x ) = f(2) + f'(2) (x-2) + \frac{f'' (2)}{2} ( x - 2)^2 + \frac{f''' (2)}{6} ( x - 2)^3 ( 1 + o ( 1) ).$$

For any $i \ne j$, $(X_i- X_j)/\sqrt 2$ is an isotropic log-concave vector. Define the sequence ${\varepsilon}(n) = n ^ { - \kappa } \wedge ( \delta /2)$ with $0 < \kappa < 1/6$. It follows from Theorem \[th:GM\] and the union bound that the event $${\mathcal{E}}= {{{\left\{ \max_{i , j } {{{\left\{ {{{\left|  \| X_i - X_j \|^2 - 2  \right|}}} \vee {{{\left|  \| X_i\|^2  - 1 \right|}}} \right\}}}} {\leqslant}{\varepsilon}(n) \right\}}}}$$ has probability tending to $1$ as $n$ goes to infinity.

### Step 2 : Taylor expansion around $\| X_i \|^2 + \| X_j \|^2$ {#step-2-taylor-expansion-around-x_i-2-x_j-2 .unnumbered}

We consider the matrix $$B_{i j } = \left\{ \begin{array}{ll}
f ( \| X_i \|^2 + \|X_j\|^2 ) - 2 f' (  \| X_i \|^2 + \|X_j\|^2 ) X_i ^T X_j  & \hbox{ if }  i \ne j \\
f(0) & \hbox{ if }  i = j.
\end{array} \right.$$ On the event ${\mathcal{E}}$, $\| X_i \|^2 + \|X_j\|^2 \in K$. Since $f$ is $C^1$ in $K$, we may perform a Taylor expansion of $f ( \| X_i - X_j \|^2)$ around $\|X_i \|^2 + \| X_j \|^2$. It follows that for $i \ne j$, $${{{\left|  A_{ij} - B_{ij}  \right|}}} = o  {{{\left( \| X_i - X_j \|^2 - \|X_i \|^2 - \|X_j \|^2 \right)}}}  {\leqslant}\delta(n) {{{\left|   X_i ^T X_j  \right|}}},$$ where $\delta(n)$ is a sequence going to $0$. From and Jensen’s inequality, we get $$\begin{aligned}
d ( {\mathbb{E}}\mu_A , {\mathbb{E}}\mu_B )  {\leqslant}{\mathbb{E}}d (  \mu_A ,  \mu_B )  & {\leqslant}& {\mathbb{P}}( {\mathcal{E}}^c ) +{{{\left(  \frac 1 n \sum_{ i \ne j } {\mathbb{E}}|A_{ij} - B_{ij} |^2 {\mathbf{1}}_{\mathcal{E}}\right)}}}^{1/2} \\
& {\leqslant}& {\mathbb{P}}( {\mathcal{E}}^c ) +  \delta(n) {{{\left(  n   {\mathbb{E}}{{{\left|   X_1 ^T X_2  \right|}}}^2 \right)}}}^{1/2}.\end{aligned}$$ Now, from the assumption that $X_1$ and $X_2$ are independent and isotropic, we find $$\begin{aligned}
{\mathbb{E}}{{{\left|   X_1 ^T X_2  \right|}}}^2 & = & {\mathbb{E}}{{{\left(  \sum_{k=1} ^ p X_{k 1} X_ {k 2} \right)}}} ^2 
 =     \sum_{k=1} ^ p {{{\left( {\mathbb{E}}X_{k 1}^2  \right)}}} ^2 
 =   \frac 1 p.\end{aligned}$$ By assumption , we deduce that $$\lim_{ n \to \infty} d ( {\mathbb{E}}\mu_A , {\mathbb{E}}\mu_B )  = 0.$$ It thus remains to compare ${\mathbb{E}}\mu_B$ and ${\mathbb{E}}\mu_{M}$.

### Step 3 : Taylor expansion around $2$ {#step-3-taylor-expansion-around-2 .unnumbered}

We define the matrix $$C_{i j } = \left\{ \begin{array}{ll}
f ( \| X_i \|^2 + \|X_j\|^2 ) - 2 f' (  2 ) X_i ^T X_j  & \hbox{ if }  i \ne j \\
f(0) & \hbox{ if }  i = j.
\end{array} \right.$$ We now use the fact that $f'$ is locally Lipschitz at 2. It follows that if ${\mathcal{E}}$ holds, for $i \ne j$, $${{{\left|  B_{ij} - C_{ij}  \right|}}} = O  {{{\left(  X_i^ T X_j (  \|X_i \|^2 + \|X_j \|^2 -2  ) \right)}}}  {\leqslant}c\, {\varepsilon}(n) {{{\left|   X_i ^T X_j  \right|}}}.$$ The argument of step 2 implies that $$\lim_{ n \to \infty} d ( {\mathbb{E}}\mu_B , {\mathbb{E}}\mu_C )  = 0.$$ It thus remains to compare ${\mathbb{E}}\mu_C$ and ${\mathbb{E}}\mu_{M}$.

### Step 4 : Taylor expansion around $2$ again {#step-4-taylor-expansion-around-2-again .unnumbered}

We now consider the matrix $$D_{i j } = \left\{ \begin{array}{ll}
f ( 2 ) + f'(2) ( \| X_i \| ^2 + \| X_j \| ^2  -2 ) + \frac{ f''(2) } {2}  ( \| X_i \| ^2 + \| X_j \| ^2  -2 )^2 & \\ 
\quad \quad +\frac{ f'''(2) } {6}  ( \| X_i \| ^2 + \| X_j \| ^2  -2 )^3 -   2 f' (  2 ) X_i ^T X_j  & \hbox{ if }  i \ne j \\
f(0) & \hbox{ if }  i = j.
\end{array} \right.$$ We are going to prove that $$\label{eq:T3}
\lim_{ n \to \infty} d ( {\mathbb{E}}\mu_C , {\mathbb{E}}\mu_D )  = 0.$$

We perform a Taylor expansion of order $3$ of $f( \| X_i \| ^2+ \| X_j \|^2)$ around $2$. It follows that if ${\mathcal{E}}$ holds, for $i \ne j$, $${{{\left|  C_{ij} - D_{ij}  \right|}}} = o  {{{\left(   \|X_i \|^2 + \|X_j \|^2 -2 \right)}}}^3   {\leqslant}\delta (n) {{{\left|    \|X_i \|^2 + \|X_j \|^2 -2  \right|}}}^3,$$ where $\delta(n)$ is a sequence going to $0$. Using and arguing as in step 2, in order to prove , it thus suffices to show that $$\frac 1 n \sum_{ i \ne j } {\mathbb{E}}| \|X_i \|^2 + \|X_j \|^2 -2  |^6 {\mathbf{1}}_{\mathcal{E}}= O (1).$$ Since, for $\ell {\geqslant}1$, $| x + y | ^\ell {\leqslant}2^{\ell-1} ( |x|^\ell + |y|^\ell)$, it is sufficient to show that $$n {\mathbb{E}}{{{\left(  \| X_1\|^2 - 1 \right)}}}^6  {\mathbf{1}}_{\mathcal{E}}= O (1).$$ To this end, for integer $\ell {\geqslant}1$, we write $$\begin{aligned}
{\mathbb{E}}{{{\left|   \| X_1\|^2 - 1  \right|}}}^{\ell} {\mathbf{1}}_{\mathcal{E}}& =  & {\mathbb{E}}{{{\left|   \| X_1\| - 1  \right|}}}^{\ell} {{{\left|   \| X_1\| + 1  \right|}}}^{\ell} {\mathbf{1}}_{\mathcal{E}}{\leqslant}3^\ell  {\mathbb{E}}{{{\left|   \| X_1\| - 1  \right|}}}^{\ell}.\end{aligned}$$ Then, Theorem \[th:GM\] implies that there exists $c_\ell$ such that $${\mathbb{E}}{{{\left|   \| X_1\| - 1  \right|}}}^{\ell} {\leqslant}c_\ell \, p^{ - \ell/ 6}.$$ It follows that $$\begin{aligned}
\label{eq:var6}
 {\mathbb{E}}{{{\left|   \| X_1\|^2 - 1  \right|}}}^{\ell} {\mathbf{1}}_{\mathcal{E}}= O {{{\left( p^{ - \ell / 6} \right)}}}. \end{aligned}$$ This proves . It finally remains to compare ${\mathbb{E}}\mu_D$ and ${\mathbb{E}}\mu_{M}$.

### Step 5 : End of proof {#step-5-end-of-proof .unnumbered}

We set $$z_i = (  \| X_i \|^ 2  -1 ).$$ We note that for $i \ne j$, $$D_{ij} = M_{ij} + \sum_{1 {\leqslant}k + \ell {\leqslant}3}  c_{k\ell} z_i ^{k} z_j ^{\ell},$$ for some coefficients $c_{k \ell}$ depending on $f'(2),f''(2),f'''(2)$. Note that $c_{10} = c_{01} =  f'(2)$. Similarly, $$D_{ii} = M_{ii} + 2 f'(2) z_i   = M_{ii} + c_{10}  z_i + c_{01}  z_i .$$ Define the matrix $E$, for all $ 1 {\leqslant}i , j {\leqslant}n$, $$E_{ij} = M_{ij} +  \sum_{1 {\leqslant}k + \ell {\leqslant}3}  c_{k\ell} z_i ^{k} z_j ^{\ell}.$$ If ${\mathcal{E}}$ holds, then $\max_i |z_i |{\leqslant}{\varepsilon}(n)$ and we find $${{{\left|  E_{ij} - D_{ij}  \right|}}} = {\mathbf{1}}( i = j ){{{\left|   \sum_{2 {\leqslant}k  + \ell {\leqslant}3}  c_{k\ell} z_i ^{k} z_i ^{\ell}  \right|}}}  {\leqslant}c {\mathbf{1}}( i = j ) {\varepsilon}(n)^2.$$ It follows from that $$\begin{aligned}
d ( {\mathbb{E}}\mu_D , {\mathbb{E}}\mu_E ) {\leqslant}{\mathbb{E}}d (  \mu_D ,  \mu_E ) & {\leqslant}& {\mathbb{P}}( {\mathcal{E}}^c) + {{{\left( \frac 1 n  \sum_{i,j}  {\mathbb{E}}{{{\left|  E_{ij} - D_{ij}  \right|}}}^2 {\mathbf{1}}_{\mathcal{E}}\right)}}}^{1/2} \\
& {\leqslant}&   {\mathbb{P}}( {\mathcal{E}}^c) +  c {\varepsilon}(n)^2. \end{aligned}$$ We deduce that $$\lim_{n \to \infty}  d ( {\mathbb{E}}\mu_D , {\mathbb{E}}\mu_E )  = 0.$$ We notice finally that the matrix $E - M$ is equal to $$\sum_{1 {\leqslant}k + \ell {\leqslant}3}  c_{k\ell} {Z_k} {Z_\ell}^T,$$ where $Z_{k}$ is the vector with coordinates $(z_i ^{k})_{1 {\leqslant}i {\leqslant}n}$. It implies in particular that ${\mathrm{rank}}( E-M ) {\leqslant}9$, indeed the ${\mathrm{rank}}$ is subadditive and ${\mathrm{rank}}( {Z_{k}} {Z_{\ell}}^T) {\leqslant}1$. In particular, it follows from that $$d ( {\mathbb{E}}\mu_E , {\mathbb{E}}\mu_M ) {\leqslant}{\mathbb{E}}d (  \mu_E ,  \mu_M )  {\leqslant}\frac 9 n .$$ This concludes the proof of Proposition \[prop:main\] and of Theorem \[th:main\].

Proof of Theorem \[th:main2\]
-----------------------------

The concentration inequality holds. It is thus sufficient to prove the analog of Proposition \[prop:main\]. If $\ell {\geqslant}2$, the proof is essentially unchanged. In step $1$, the assumption implies the existence of a sequence ${\varepsilon}= {\varepsilon}(n)$ going to $0$ such that ${\mathbb{P}}( {\mathcal{E}}) \to 1$. Then, in step $4$, it suffices to extend the Taylor expansion up to $\ell$.

For the case $\ell =1$ : in step $2$, we perform directly the Taylor expansion around $2$, for $i \ne j$ we write $f(\| X_i - X_j \|^2) = f (2) - 2 f'(2) X_i ^T X_j ( 1 + o(1))$. We then move directly to step $5$. (As already pointed, this case is treated in [@DoVu]).
