# Almost sharp covariance and Wishart-type matrix estimation

Patrick Oliveira Santos1

###### Abstract.

Let $X_{1},...,X_{n}\in\mathbb{R}^{d}$ be independent Gaussian random vectors
with independent entries and variance profile $(b_{ij})_{i\in[d],j\in[n]}$. A
major question in the study of covariance estimation is to give precise
control on the deviation of
$\sum_{j\in[n]}X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{j}X_{j}^{T}$. In
this paper, we improve the results in [4, 2] and we show that under mild
conditions, we have

$\displaystyle\operatorname{\mathbb{E}}\left\|\sum_{j\in[n]}X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{j}X_{j}^{T}\right\|\lesssim\max_{i\in[d]}\left(\sum_{j\in[n]}\sum_{l\in[d]}b_{ij}^{2}b_{lj}^{2}\right)^{1/2}+\max_{j\in[n]}\sum_{i\in[d]}b_{ij}^{2}+\text{error}.$

The error is quantifiable, and we often capture the $4$th-moment dependency
already presented in [4] for some examples. The proofs are based on the moment
method and a careful analysis of the structure of the shapes that matter. We
also provide examples showing improvement over the past works and matching
lower bounds.

1 LAMA, Université Gustave Eiffel, Paris, France. Email:
<EMAIL_ADDRESS>
##  1\. Introduction

The study of the norm of random matrices has increased significantly over the
years, and bounding the operator norm has been proved one central topic in the
field [1, 6, 3]. Particularly, several applications coming from statistics
require a precise sharp control on the deviations of the empirical covariance
problem [7, 9, 13]. For instance, it is well-known [11] that an i.i.d sample
$X_{1},...,X_{n}\in\mathbb{R}^{d}$ of isotropic Gaussian random vectors
satisfies the following deviation

$\displaystyle\operatorname{\mathbb{E}}\left\|\frac{1}{n}\sum_{j\in[n]}X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{1}X_{1}^{T}\right\|\lesssim\frac{d}{n}\vee\sqrt{\frac{d}{n}}.$
(1)

Much less is known, however, when the identically distributed condition is
removed and we only require independence. Our contribution comes precisely in
this direction. In particular, we improve the results in [4] and we shed light
on the $4$th-moment parameter and its graph interpretation that was before
unclear.

Let $X$ be a random $d\times n$ Gaussian matrix with independent entries
$X_{ij}=b_{ij}g_{ij}$, where $b_{ij}\geq 0$ and $\\{g_{ij}:i\in[d],j\in[n]\\}$
are independent standard Gaussian random variables $N(0,1)$. Our goal is to
bound the quantity

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|=\operatorname{\mathbb{E}}\left\|\sum_{j\in[n]}X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{j}X_{j}^{T}\right\|,$

where $X_{j}=Xe_{j}$ is the $j$th column of $X$. One of the first dimension-
free results improving bound (1) was given in the i.i.d setting in [7]. Their
result states that whenever $Y_{1},...,Y_{n}$ are i.i.d Gaussian random
vectors in $\mathbb{R}^{d}$, we have

$\displaystyle\operatorname{\mathbb{E}}\|YY^{T}-\operatorname{\mathbb{E}}YY^{T}\|\asymp\|\Sigma\|\left(\sqrt{n\text{rk}(\Sigma)},\text{rk}(\Sigma)\right),$

where

$\displaystyle\text{rk}(\Sigma)=\frac{\text{tr}(\Sigma)}{\|\Sigma\|}$

is the effective rank of the covariance matrix
$\Sigma=\operatorname{\mathbb{E}}Y_{1}Y_{1}^{T}$. The dependency on the sample
size $n$ is sharp in all i.i.d cases, but much less is evident when the
vectors are not identically distributed.

In an orthogonal direction, Bandeira and van Handel [3] proved that

$\displaystyle\operatorname{\mathbb{E}}\|X\|\lesssim\sigma_{C}+\sigma_{R}+C\sigma_{*}\sqrt{\log(n\wedge
d)},$

where $\sigma_{C}$ is the maximum Euclidean norm of columns of $B=(b_{ij})$,
$\sigma_{R}$ is the maximum Euclidean norm of rows of $B$ and $\sigma_{*}$ is
the maximum entry of $B$, that is,

$\displaystyle\sigma_{C}^{2}=\max_{j\in[n]}\sum_{i\in[d]}b_{ij}^{2};$
$\displaystyle\sigma_{R}^{2}=\max_{i\in[d]}\sum_{j\in[n]}b_{ij}^{2};$
$\displaystyle\sigma_{*}=\max_{(i,j)\in[d]\times[n]}|b_{ij}|.$

To prove such a result, they compared the moments
$\operatorname{\mathbb{E}}\text{tr}(XX^{T})^{p}$ to the moments of a standard
Gaussian matrix $\operatorname{\mathbb{E}}\text{tr}(GG^{T})^{p}$ with reduced
dimensions. This comparison method turned out to be also efficient to prove
the estimations for the covariance problem as well. In [4], T. Cai, Han and
Zhang applied these techniques to $XX^{T}-\operatorname{\mathbb{E}}XX^{T}$ and
they proved that

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim\sigma_{C}\sigma_{R}+\sigma_{C}^{2}+C(\sigma_{C}\sigma_{*}+\sigma_{R}\sigma_{*})\sqrt{\log(n\wedge
d)}+C^{\prime}\sigma_{*}^{2}\log(n\wedge d).$

The leading term $\sigma_{C}\sigma_{R}+\sigma_{C}^{2}$ is not always sharp.
Indeed, studying the case $b_{ij}=b_{j}$, that is, the rows are i.i.d, the
authors of [4] proved that

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\asymp\sqrt{d\sum_{j}b_{j}^{4}}+d\max_{j}b_{j}^{2}=\sqrt{d\sum_{j}b_{j}^{4}}+\sigma_{C}^{2}.$

Our main contribution shed light on this $4$th-moment parameter and how it
appears from the moment method.

We begin our results for the operator norm. Define the parameters:

$\displaystyle\bullet\tilde{\sigma}_{\infty}^{2}=\max_{i,l:i\neq
l}\sum_{j\in[n]}b_{ij}^{2}b_{lj}^{2};$
$\displaystyle\bullet\bar{\sigma}_{\infty}^{2}=\max_{i\in[d]}\sum_{j\in[n]}b_{ij}^{4};$
$\displaystyle\bullet\sigma_{\infty}^{2}=\max_{i\in[d]}\sum_{j\in[n]}\sum_{l:l\neq
i}b_{ij}^{2}b_{lj}^{2};$
$\displaystyle\bullet\beta_{\infty}=\frac{\tilde{\sigma}_{\infty}\sigma_{C}}{\sigma_{\infty}\sigma_{*}}.$

Notice in particular that $\tilde{\sigma}_{\infty}\leq\bar{\sigma}_{\infty}$,
by Cauchy-Schwarz inequality.

######  Theorem 1.1.

Let $X$ be a $d\times n$ Gaussian matrix with independent entries such that
$X_{ij}=b_{ij}g_{ij}$ where $\\{g_{ij}:(i,j)\in[d]\times[n]\\}$ are i.i.d
standard Gaussian r.v. Then, if $\beta_{\infty}\leq 1$, we have

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|=\operatorname{\mathbb{E}}\left\|\sum_{j\in[n]}X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{j}X_{j}^{T}\right\|$
$\displaystyle\leq(1+\varepsilon)\left\\{2\sigma_{\infty}+\sigma_{C}^{2}+C(\varepsilon)\sigma_{*}\left(\sigma_{C}+\frac{\sigma_{\infty}}{\sigma_{C}}\right)\sqrt{\log(n\wedge
d)}+C^{2}(\varepsilon)\sigma_{*}^{2}\log(n\wedge d)\right\\},$

for any $0<\varepsilon\leq 1/2$. Otherwise, $\beta_{\infty}>1$ and we have

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|$
$\displaystyle\leq(1+\varepsilon)\left\\{\frac{2\tilde{\sigma}_{\infty}\sigma_{C}}{\sigma_{*}}+\sigma_{C}^{2}+C(\varepsilon)\left(\sigma_{C}\sigma_{*}+\bar{\sigma}_{\infty}\right)\sqrt{\log(n\wedge
d)}+C^{2}(\varepsilon)\sigma_{*}^{2}\log(n\wedge d)\right\\}.$

The constant $C(\varepsilon)$ is

$\displaystyle
C(\varepsilon)=\frac{C(1+\varepsilon)}{\sqrt{\log(1+\varepsilon)}},$

where $C$ is a universal constant.

Theorem 1.1 improves Theorem 2.1 from [4]. When $\beta_{\infty}\leq 1$, we get
the sharp constant $2\sigma_{\infty}$ on the right-hand side. Moreover, if
$\beta_{\infty}=O(1)$, our result still gives the correct order of magnitude.

Since the method of proof uses the moment method, we can extend Theorem 1.1 to
estimate Schatten norms. Recall that the $p$-Schatten norm is defined by

$\displaystyle\|A\|_{S_{p}}^{p}=\text{Tr}(A)^{p},$

for a positive matrix $A$. It is also the same as the $p$-norm of the singular
values of $A$. This time, we define the more involved parameters

$\displaystyle\bullet\sigma_{p}=\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}\sum_{l\in[d]}b_{ij}^{2}b_{lj}^{2}\right]^{p/2}\right\\}^{1/p};$
$\displaystyle\bullet\overline{\sigma}_{p}=\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{4}\right]^{p/2}\right\\}^{1/p};$
$\displaystyle\bullet
b_{p}=\left\\{\sum_{i\in[d]}\max_{j\in[n]}b_{ij}^{2p}\right\\}^{1/(2p)};$
$\displaystyle\bullet\beta_{p}=\frac{\bar{\sigma}_{p}\sigma_{C}}{\sigma_{p}b_{p}}.$

Our second main theorem is the following.

######  Theorem 1.2.

Let $X$ be a $d\times n$ Gaussian matrix with independent entries such that
$X_{ij}=b_{ij}g_{ij}$ where $\\{g_{ij}:(i,j)\in[d]\times[n]\\}$ are i.i.d
standard Gaussian r.v. Then, if $\beta_{p}\leq 1$, we have

$\displaystyle(\operatorname{\mathbb{E}}\emph{Tr}[XX^{T}-\operatorname{\mathbb{E}}XX^{T}]^{p})^{1/p}\leq
d^{1/p}\left\\{2\sigma_{p}+\sigma_{C}^{2}+C\sqrt{p}\left(\sigma_{C}\sigma_{*}+\frac{\sigma_{p}\sigma_{*}}{\sigma_{C}}\right)+C^{\prime}pb_{p}^{2}\right\\}.$

Otherwise, $\beta_{p}>1$ and

$\displaystyle(\operatorname{\mathbb{E}}\emph{Tr}[XX^{T}-\operatorname{\mathbb{E}}XX^{T}]^{p})^{1/p}\leq
d^{1/p}\left\\{\frac{2\overline{\sigma}_{p}\sigma_{C}}{\sigma_{*}}+\sigma_{C}^{2}+C\sqrt{p}\left(\sigma_{C}\sigma_{*}+\overline{\sigma}_{p}\right)+C^{\prime}pb_{p}^{2}\right\\}.$

###  1.1. Main ideas of the proof

The proof relies on the moment method and a careful analysis of paths. We will
first remove the diagonal $\text{Diag}(XX^{T})$, so that

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\leq\operatorname{\mathbb{E}}\|\Delta
XX^{T}\|+\operatorname{\mathbb{E}}\|\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T}\|,$

where $\Delta XX^{T}$ is the matrix of off-diagonal elements of $XX^{T}$. It
turns out that the contribution of the diagonal is sufficiently small and can
be added as an error factor (see Theorem 2.5). On the other hand, the
combinatorics of $\Delta XX^{T}$ are much easier to deal with. In particular,
all paths in the complete bipartite graph over $[d]\sqcup[n]$ have all right
vertices with at least two neighbors.

We then proceed with the moment method. Note that

$\displaystyle\operatorname{\mathbb{E}}\|Y\|\leq\operatorname{\mathbb{E}}\|Y\|_{S_{p}}\leq
d^{1/p}\operatorname{\mathbb{E}}\|Y\|,$

for any symmetric $d\times d$ matrix. Hence,

$\displaystyle\operatorname{\mathbb{E}}\|Y\|\leq(\operatorname{\mathbb{E}}\|Y\|_{S_{p}}^{p})^{1/p},$

by Jensen’s Inequality. We apply this for $Y=\Delta XX^{T}$ and our goal is to
obtain a comparison lemma such as

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\Delta
XX^{T})^{p}\leq\kappa\operatorname{\mathbb{E}}\text{Tr}(\Delta GG^{T})^{p},$

where $\kappa>0$ and $G$ is a Gaussian matrix with reduced dimensions as in
[3].

###  1.2. Outline of the paper

The paper is organized as follows. In section 2, we will provide the main
proofs of theorems 1.1 and 1.2. In section 3, we will give examples to
illustrate the improvement from the previous results. Finally, in section 4,
we will prove almost sharp matching lower bounds for our main theorems.

Notation. Let us clarify some notation used throughout the paper. We denote
$a\lesssim b$ or $a=O(b)$ if there exists an absolute constant $C$ such that
$a\leq Cb$. We also denote it as $b\gtrsim a$. If $a\lesssim b$ and $b\lesssim
a$ hold, we denote $a\asymp b$. We write $a\wedge b=\min(a,b)$ and $a\vee
b=\max(a,b)$. We denote $[n]=\\{1,\ldots,n\\}$ and $A\sqcup B$ is the disjoint
union of two sets $A$ and $B$. Finally, we use $C,c,C^{\prime},\ldots$ for
universal numerical constants.

#### Acknowledgments.

We thank Olivier Guédon for pointing out this problem and helpful discussions.

##  2\. Proofs

###  2.1. Preliminaries

We begin by recalling the Gaussian integration by parts lemma.

######  Lemma 2.1.

Let $g\sim N(0,1)$ be a standard Gaussian r.v. and $f\in C^{1}(\mathbb{R})$,
then

$\displaystyle\operatorname{\mathbb{E}}gf(g)=\operatorname{\mathbb{E}}f^{\prime}(g).$

The authors of [4] deduced from this lemma a simple property of the joint
moments of $g$ and $g^{2}-1$.

######  Lemma 2.2.

Let $a_{n,m}=\operatorname{\mathbb{E}}g^{n}(g^{2}-1)^{m}$, where $g\sim
N(0,1)$. Then $a_{n,m}\geq 0$ and $a_{n,m}=0$ if and only if $n$ is odd or
$(n,m)=(0,1)$.

We also recall the sharp bound on the operator norm for a standard Gaussian
matrix shown in [4].

######  Proposition 2.3.

Let $G$ be a $d\times n$ Gaussian matrix with i.i.d standard Gaussian r.v.
entries. Then, for any $p\geq 2$ we have

$\displaystyle(\operatorname{\mathbb{E}}\|GG^{T}-\operatorname{\mathbb{E}}GG^{T}\|^{p})^{1/p}\leq
2\sqrt{dn}+d+4\sqrt{p}(\sqrt{d}+\sqrt{n})+2p.$

Note that

$\displaystyle\operatorname{\mathbb{E}}\|\text{Diag}(GG^{T})-\operatorname{\mathbb{E}}GG^{T}\|^{p}=\operatorname{\mathbb{E}}\max_{i\in[d]}\left(\sum_{j\in[n]}(g^{2}_{ij}-1)\right)^{p}.$

Bernstein’s Inequality [5] implies then that

$\displaystyle(\operatorname{\mathbb{E}}\|\text{Diag}(GG^{T})-\operatorname{\mathbb{E}}GG^{T}\|^{p})^{1/p}\lesssim\sqrt{pn}+p.$

Consequently, we end this subsection with a corollary for the off-diagonal
part.

######  Corollary 2.4.

Let $G$ be a $d\times n$ Gaussian matrix with i.i.d standard Gaussian entries.
Then, for any $p\geq 2$ we have

$\displaystyle(\operatorname{\mathbb{E}}\|\Delta(GG^{T})\|^{p})^{1/p}\leq
2\sqrt{dn}+d+C\sqrt{p}(\sqrt{d}+\sqrt{n})+C^{\prime}p.$

###  2.2. The diagonal part

In this section, the main result is the following.

######  Theorem 2.5.

For any $p\geq 2$, we have

$\displaystyle\left(\operatorname{\mathbb{E}}\emph{Tr}[\emph{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T}]^{p}\right)^{1/p}\asymp\sqrt{p}\overline{\sigma}_{p}+pb_{p}^{2}.$

###### Proof.

For the upper bound, note that

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T})^{p}=\sum_{i\in[d]}\operatorname{\mathbb{E}}\left(\sum_{j\in[n]}b_{ij}^{2}(g_{ij}^{2}-1)\right)^{p}.$

Since $g_{ij}^{2}-1$ are independent, centered, and subexponential, we can use
Bernstein’s Inequality to deduce that

$\displaystyle\mathbb{P}\left(\left|\sum_{j\in[n]}b_{ij}^{2}(g_{ij}^{2}-1)\right|\geq
t\right)\leq
2\exp\left(-c\min\left\\{\frac{t^{2}}{a^{2}},\frac{t}{b}\right\\}\right),$

where

$\displaystyle a=\sum_{j\in[n]}b_{ij}^{4};$ $\displaystyle
b=\max_{j\in[n]}b_{ij}^{2},$

hence

$\displaystyle\left[\operatorname{\mathbb{E}}\left(\sum_{j\in[n]}b_{ij}^{2}(g_{ij}^{2}-1)\right)^{p}\right]^{1/p}\lesssim\sqrt{p}\left(\sum_{j\in[n]}b_{ij}^{4}\right)^{1/2}+p\max_{j\in[n]}b_{ij}^{2}.$

We then have

$\displaystyle\left[\operatorname{\mathbb{E}}\text{Tr}(\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T})^{p}\right]^{1/p}$
$\displaystyle\lesssim\left[\sum_{i\in[d]}\left(\sqrt{p}\left(\sum_{j\in[n]}b_{ij}^{4}\right)^{1/2}+p\max_{j\in[n]}b_{ij}^{2}.\right)^{p}\right]^{1/p}$
$\displaystyle\lesssim\sqrt{p}\overline{\sigma}_{p}+pb_{p}^{2},$

where the last inequality follows by the triangle inequality.

For the lower bound, let $j_{i}$ be the index such that

$\displaystyle\max_{j\in[n]}b_{ij}=b_{ij_{i}}.$

Since the joint moments of $g$ and $g^{2}-1$ are always positive, we deduce
that

$\displaystyle\left[\operatorname{\mathbb{E}}\text{Tr}(\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T})^{p}\right]^{1/p}\geq\left[\sum_{i\in[d]}\operatorname{\mathbb{E}}b_{ij_{i}}^{2p}(g_{ij_{i}}^{2}-1)^{p}\right]^{1/p}.$

Now, the estimate

$\displaystyle\left(\operatorname{\mathbb{E}}(g^{2}-1)^{p}\right)^{1/p}\gtrsim
p,$

that follows the lower bound on the double factorial (see Lemma 5.2 in [4])
implies that

$\displaystyle\left[\operatorname{\mathbb{E}}\text{Tr}(\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T})^{p}\right]^{1/p}\gtrsim
p\left(\sum_{i\in[d]}\max_{j\in[n]}b_{ij}^{2p}\right)^{1/p}=pb_{p}^{2}.$

On the other hand, Theorem 6 in [12] yields that
$Z=\sum_{j\in[n]}b_{ij}^{2}(g_{ij}^{2}-1)$ satisfies

$\displaystyle\exp(-Ct^{2}/a)\lesssim\mathbb{P}(Z\geq t);$
$\displaystyle\exp(-Ct^{2}/a)\lesssim\mathbb{P}(Z\leq-t),$

for all $t\geq 0$. Therefore, its moments are lower bounded by the ones of the
Gaussian $h\sim N(0,a)$, hence

$\displaystyle(\operatorname{\mathbb{E}}|Z|^{p})^{1/p}\gtrsim\sqrt{ap},$

so we conclude that

$\displaystyle\left[\operatorname{\mathbb{E}}\text{Tr}(\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T})^{p}\right]^{1/p}\gtrsim\sqrt{p}\overline{\sigma}_{p}.$

∎

###  2.3. The off-diagonal part

The proof of the bounds for the off-diagonal part follows the moment method.
First, we open the trace so that

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\Delta XX^{T})^{p}$
$\displaystyle=\sum_{u\in[d]^{p}}\operatorname{\mathbb{E}}\prod_{k=1}^{p}(XX^{T})_{u_{k}u_{k+1}}\mathbf{1}_{u_{k}\neq
u_{k+1}}$
$\displaystyle=\sum_{u\in[d]^{p}}\sum_{v\in[n]^{p}}\operatorname{\mathbb{E}}\prod_{k=1}^{p}X_{u_{k}v_{k}}X_{u_{k+1}v_{k}}\mathbf{1}_{u_{k}\neq
u_{k+1}},$

where $u_{p+1}:=u_{1}$. We view the path $u_{1}\to v_{1}\to u_{2}\to\cdots\to
u_{p}\to v_{p}\to u_{1}$ as a cycle in the complete bipartite graph over
$[d]^{(l)}\sqcup[n]^{(r)}$, where $(l)$ and $(r)$ indicate left and right
vertices (we will remove the indexes if the context is clear). For a path
$(u,v)$, we define its shape $s(u,v)$ as relabelling its vertices in order of
appearance. For instance, the path

$\displaystyle 3\to 2^{\prime}\to 4\to 1^{\prime}\to 3\to 1^{\prime}\to 4\to
5^{\prime}\to 3$

has shape

$\displaystyle 1\to 1^{\prime}\to 2\to 2^{\prime}\to 1\to 2^{\prime}\to 2\to
3^{\prime}\to 1.$

Note that each edge $u_{k}v_{k}$ and $u_{k+1}v_{k}$ must appear at least twice
in the path $(u,v)$, by the independence of the Gaussian r.v. and symmetry.
Call the shapes that satisfy this even. Let then $\mathcal{S}$ be the set of
even shapes $s=(u,v)$ such that $u_{k}\neq u_{k+1}$ for all $k=1,...,p$.
Moreover, the product

$\displaystyle
L(s):=\operatorname{\mathbb{E}}\prod_{k=1}^{p}g_{u_{k}v_{k}}g_{u_{k+1}v_{k}}$
(2)

only depends on the shape of $(u,v)$, therefore we have

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\Delta
XX^{T})^{p}=\sum_{s\in\mathcal{S}}L(s)\sum_{\begin{subarray}{c}(u,v)\in[d]^{p}\times[n]^{p}\\\
s(u,v)=s\end{subarray}}\prod_{k=1}^{p}b_{u_{k}v_{k}}b_{u_{k+1}v_{k}}.$

Let $(m_{1},m_{2})=(m_{1}(s),m_{2}(s))$ be the quantity of right and left
vertices that appear in the shape $s$. The key proposition to prove Theorem
1.1 is to bound

$\displaystyle W(s):=\sum_{\begin{subarray}{c}(u,v)\in[d]^{p}\times[n]^{p}\\\
s(u,v)=s\end{subarray}}\prod_{k=1}^{p}b_{u_{k}v_{k}}b_{u_{k+1}v_{k}}$ (3)

according to the number of vertices visited by the path.

######  Proposition 2.6.

Assume $\sigma_{*}=1$. If $\beta_{\infty}\leq 1$, we have

$\displaystyle
W(s)\leq\left[d\left(\frac{\sigma_{\infty}}{\sigma_{C}}\right)^{2m_{1}}\sigma_{C}^{2(m_{2}-1)}\right]\wedge\left[n\left(\frac{\sigma_{\infty}}{\sigma_{C}}\right)^{2(m_{1}-1)}\sigma_{C}^{2m_{2}}\right].$

Otherwise, $\beta_{\infty}>1$ and we have

$\displaystyle
W(s)\leq\left[d\tilde{\sigma}_{\infty}^{2m_{1}}\sigma_{C}^{2(m_{2}-1)}\right]\wedge\left[n\tilde{\sigma}_{\infty}^{2(m_{1}-1)}\sigma_{C}^{2m_{2}}\right].$

Let us prove Theorem 1.1 given Proposition 2.6.

###### Proof of Theorem 1.1..

Assume $\sigma_{*}=1$ (by homogeneity) and $\beta_{\infty}\leq 1$. Let

$\displaystyle a:=\frac{\sigma_{\infty}}{\sigma_{C}};$ $\displaystyle
b:=\sigma_{C}.$

Then, using the first bound on Proposition 2.6, we have

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\Delta XX^{T})^{p}\leq
d\sum_{s\in\mathcal{S}}L(s)\left(\frac{\sigma_{\infty}}{\sigma_{C}}\right)^{2m_{1}}\sigma_{C}^{2(m_{2}-1)}.$

On the other hand, for a standard Gaussian $r_{2}\times r_{1}$ matrix $G$, we
have

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\Delta
GG^{T})^{p}=\sum_{s\in\mathcal{S}}L(s)\frac{r_{1}!}{(r_{1}-m_{1})!}\frac{r_{2}!}{(r_{2}-m_{2})!},$

for any $r_{1},r_{2}>p/2$ (see [4]). In particular, if $r_{1}=\lceil
a^{2}\rceil+p/2$ and $r_{2}=\lceil b^{2}\rceil+p/2$, we have

$\displaystyle\frac{r_{1}!}{(r_{1}-m_{1})!}\geq
r_{1}\cdots(r_{1}-m_{1}+1)^{m_{1}}\geq a^{2m_{1}},$

and

$\displaystyle\frac{r_{2}!}{(r_{2}-m_{2})!}\geq r_{2}b^{2(m_{2}-1)}.$

Hence

$\displaystyle\operatorname{\mathbb{E}}\text{Tr}(\Delta
XX^{T})^{p}\leq\frac{d}{r_{2}}\operatorname{\mathbb{E}}\text{Tr}(\Delta
GG^{T})^{p}\leq d\operatorname{\mathbb{E}}\|\Delta GG^{T}\|^{p}.$

Now we estimate the latter by Corollary 2.4 so that

$\displaystyle(\operatorname{\mathbb{E}}\|\Delta GG^{T}\|^{p})^{1/p}\leq
2\sqrt{r_{1}r_{2}}+r_{2}+C\sqrt{p}(\sqrt{r_{1}}+\sqrt{r_{2}})+C^{\prime}p.$

Together with Theorem 2.5, we deduce that

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\leq
d^{\frac{1}{p}}\left\\{2\sigma_{\infty}+\sigma_{C}^{2}+C\sqrt{p}\left(\sigma_{C}+\frac{\sigma_{\infty}}{\sigma_{C}}+\bar{\sigma}_{p}\right)+Cpb_{p}^{2}\right\\}.$

Choose $p=\lceil\alpha\log d\rceil$. Since $\beta_{\infty}\leq 1$, we have
that

$\displaystyle\bar{\sigma}_{p}\leq d^{\frac{1}{p}}\bar{\sigma}_{\infty}\leq
d^{\frac{1}{p}}\frac{\sigma_{\infty}}{\sigma_{C}}.$

Moreover, $b_{p}\leq d^{\frac{1}{2p}}b_{\infty}$, thus

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\leq
e^{\frac{1}{\alpha}}\left\\{2\sigma_{\infty}+\sigma_{C}^{2}+Ce^{\frac{1}{\alpha}}\sqrt{\alpha\log
d}\left(\sigma_{C}+\frac{\sigma_{\infty}}{\sigma_{C}}\right)+C\alpha
e^{\frac{1}{2\alpha}}\log d\right\\}.$

Finally, set $1+\varepsilon=e^{\frac{1}{\alpha}}$, hence

$\displaystyle\alpha=\frac{1}{\log(1+\varepsilon)},$

and we get

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\leq(1+\varepsilon)\left\\{2\sigma_{\infty}+\sigma_{C}^{2}+C(\varepsilon)\sqrt{\log
d}\left(\sigma_{C}+\frac{\sigma_{\infty}}{\sigma_{C}}\right)+C^{2}(\varepsilon)\log
d\right\\}.$

This gives the upper bound with $\log d$. The second bound in Proposition 2.6
yields the general bound for $\beta_{\infty}\leq 1$. The case
$\beta_{\infty}>1$ follows similarly. Indeed, we now set $(a,b)$ to be

$\displaystyle a=\tilde{\sigma}_{\infty};$ $\displaystyle b=\sigma_{C},$

and then the previous proof follows straightforwardly.

∎

Now we prove Proposition 2.6.

###### Proof of Proposition 2.6.

To simplify the notation, for a graph $G$, we will denote $e\in G$ if an edge
$e$ belongs to $E(G)$, $v\in G$ if $v\in V(G)$ and
$G^{\prime}=G\setminus\\{v\\}$ is the subgraph of $G$ induced by the vertices
$V(G)\setminus\\{v\\}$. We use a similar notation to $G\setminus\\{e\\}$ and
an edge $e\in E(G)$.

Given a shape $s\in\mathcal{S}$, we define a bipartite graph $G$ over
$[m_{2}]\sqcup[m_{1}]$ so that $E(G)=\\{(u_{k}v_{k}):k\in[p]\\}$. Here,
$[m_{2}]$ denotes the left vertices and $[m_{1}]$ denotes the right vertices.
Let $k_{e}$ be the number of times each edge $e\in E(G)$ is traversed by the
shape $s$, then $\sum_{e}k_{e}=2p=|k|$. According to (3), we get an
alternative expression for $W(s)$:

$\displaystyle W(s)=\sum_{w_{1}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq t_{m_{1}}}\prod_{e=ij\in
E(G)}b_{w_{i}t_{j}}^{k_{e}}=:W^{k}(G),$

where the notation $w_{1}\neq\cdots\neq w_{m_{2}}$ means that all $w_{k}$ are
different, similarly for $t_{k}$. Note that, by the assumption on
$s\in\mathcal{S}$, every right vertex has at least 2 neighbors. Now, fix
$u_{1}=w_{1}=z\in[d]$ and define the following first-time arrivals:

$\displaystyle i_{1}(k):=\inf\\{l:u_{l}=k\\};\ k=2,...,m_{2};$ $\displaystyle
i_{2}(k):=\inf\\{l:v_{l}=k\\};\ k=1,...,m_{1}.$

Let also $e^{(1)}_{k}=u_{i_{1}(k)}v_{i_{1}(k)-1}$ and
$e^{(2)}_{k}=u_{i_{2}(k)}v_{i_{2}(k)}$. Then all these $m_{1}+m_{2}-1$ edges
are distinct, and the subgraph $H$ generated by them is a spanning tree of
$G$.

The crucial distinction to [4] is that we want to preserve the property that
every right vertex has at least two neighbors. Call this property
$\mathcal{P}$. Let us divide in two cases whether this is true.

Case I. Suppose the tree $H$ satisfies property $\mathcal{P}$. Assume
$v,v^{\prime}$ are extreme right vertices, that is,

$\displaystyle d(v,v^{\prime})=\max_{r,r^{\prime}\in[m_{1}]}d(r,r^{\prime}).$

(In case $m_{1}=1$, the result is trivial). Then $v$ has exactly one neighbor
$u\in[m_{2}]$ such that $|N(u)|\geq 2$ and it satisfies

$\displaystyle d(v^{\prime},u)=d(v^{\prime},v)-1,$

that is, the unique path from $v^{\prime}$ to $v$ passes through $u$. Indeed,
if there are two of such vertices $u,u^{\prime}$ and $u^{\prime}$ is connected
to both $v$ and a different $v^{\prime\prime}$, we would have that

$\displaystyle
d(v^{\prime},v^{\prime\prime})=d(v^{\prime},v)+d(v,v^{\prime\prime})=d(v^{\prime},v)+2,$

which contradicts the maximal distance of $v$ and $v^{\prime}$. Therefore, if
$L(v)=\\{u\in N(v):|N(u)|=1\\}\cup\\{v\\}$ we have that the graph
$H^{\prime}=H\setminus L(v)$ is still a tree with the property $\mathcal{P}$.
Without loss of generality, we can assume that $v=m_{1}$. Since $\sigma_{*}=1$
and $k_{e}\geq 2$ for all $e\in G$, we have

$\displaystyle W^{k}(G)$ $\displaystyle\leq d\sum_{w_{2}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq t_{m_{1}}}\prod_{e=ij\in
E(H)}b_{w_{i}t_{j}}^{2}$ $\displaystyle\leq d\left(\sum_{w_{2}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq t_{m_{1}-1}}\prod_{e=ij\in
E(H^{\prime})}b_{w_{i}t_{j}}^{2}\right)\max_{w\in[d]}\sum_{j\in[n]}b_{wj}^{2}\left(\sum_{l\in[d]:l\neq
w}b_{lj}^{2}\right)^{|N(m_{1})|-1}.$

For the second term, we further estimate

$\displaystyle\max_{w\in[d]}\sum_{j\in[n]}b_{wj}^{2}\left(\sum_{l\in[d]:l\neq
w}b_{lj}^{2}\right)^{|N(m_{1})|-1}\leq\sigma_{\infty}^{2}\sigma_{C}^{2(|N(m_{1})|-2)}.$

We then proceed by induction over the right vertices as we did for $H$. Here,
induction is justified as $H^{\prime}$ is still in case I. In particular, that
yields

$\displaystyle W^{k}(G)\leq
d\sigma_{\infty}^{2m_{1}}\sigma_{C}^{2\sum_{v\in[m_{1}]}(|N(v)|-2)}.$

Since $|E(H)|=\sum_{v\in[m_{1}]}|N(v)|=m_{1}+m_{2}-1$, we get that

$\displaystyle W^{k}(G)\leq
d\left(\frac{\sigma_{\infty}}{\sigma_{C}}\right)^{2m_{1}}\sigma_{C}^{2(m_{2}-1)}.$

Case II. In case the tree $H$ does not satisfy property $\mathcal{P}$, we then
add for each $v\in H\cap[m_{1}]$ with $|N(v)|=1$ in $H$ one extra edge $uv\in
E(G)$ from $G$. This creates a graph $H^{\prime}$ that is not a tree, but it
satisfies property $\mathcal{P}$.

Let

$\displaystyle V=\\{v\in H\cap[m_{1}]:|N(v)|=1\text{ in }H\\}.$

Then for each $v\in V$ we have $|N(v)|=2$ in $H^{\prime}$ and $v$ belongs to a
cycle in $H^{\prime}$. In particular, we can remove $v$ from $H^{\prime}$ and
$H^{\prime\prime}=H^{\prime}\setminus\\{v\\}$ is still connected. Assume
$v=m_{1}$, then we have

$\displaystyle W^{k}(G)\leq d\left(\sum_{w_{2}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq t_{m_{1}-1}}\prod_{e=ij\in
E(H^{\prime\prime})}b_{w_{i}t_{j}}^{2}\right)\max_{i\neq
l\in[d]}\sum_{j\in[d]}b_{ij}^{2}b_{lj}^{2}.$

We deduce that

$\displaystyle W^{k}(G)\leq
d\tilde{\sigma}_{\infty}^{2}\sum_{w_{2}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq t_{m_{1}-1}}\prod_{e=ij\in
E(H^{\prime\prime})}b_{w_{i}t_{j}}^{2}.$

By induction, we have

$\displaystyle W^{k}(G)\leq
d\tilde{\sigma}_{\infty}^{2|V|}\sum_{w_{2}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq t_{m_{1}-|V|}}\prod_{e=ij\in E(H\setminus
V)}b_{w_{i}t_{j}}^{2}.$

By assumption, $H\setminus V=H^{\prime}\setminus V$ is a tree satisfying
property $\mathcal{P}$. Therefore, case $I$ implies that

$\displaystyle W^{k}(G)\leq
d\tilde{\sigma}_{\infty}^{2|V|}\left(\frac{\sigma_{\infty}}{\sigma_{C}}\right)^{2(m_{1}-|V|)}\sigma_{C}^{2(m_{2}-1)}.$

By definition of $\beta_{\infty}$, we have

$\displaystyle W^{k}(G)\leq
d\beta_{\infty}^{2|V|}\left(\frac{\sigma_{\infty}}{\sigma_{C}}\right)^{2m_{1}}\sigma_{C}^{2(m_{2}-1)}.$

If $\beta_{\infty}\leq 1$, we choose $|V|=0$, otherwise we choose $|V|=m_{1}$.
A straightforward computation yields the bounds of Proposition 2.6 with factor
$d$.

For the second bound, instead of fixing $u_{1}=w_{1}=z$, we fix
$v_{1}=t_{1}=z$. Define the following first-time arrivals:

$\displaystyle i_{1}(k):=\inf\\{l:u_{l}=k\\};\ k=1,...,m_{2};$ $\displaystyle
i_{2}(k):=\inf\\{l:v_{l}=k\\};\ k=2,...,m_{1},$

and let also $e^{(1)}_{k}=u_{i_{1}(k)}v_{i_{1}(k)-1}$ and
$e^{(2)}_{k}=u_{i_{2}(k)}v_{i_{2}(k)}$. The same argument done before implies
that these $m_{1}+m_{2}-1$ edges are distinct, and the subgraph $H$ generated
by them is a spanning tree of $G$. We then repeat the proof as in the first
bound, but now the first choice of vertex $v_{1}$ will contribute with a
factor of $n$. ∎

###  2.4. Proof of Theorem 1.2

To get the correct parameters for the Schatten norm, we must improve
Proposition 2.6 and the bound on $W(s)$. The main proposition of this
subsection is the following.

######  Proposition 2.7.

For any shape $s\in\mathcal{S}$, if $\beta_{p}\leq 1$, we have

$\displaystyle W(s)\leq
d\sigma_{*}^{2p}\left\\{\frac{\sigma_{p}}{\sigma_{*}\sigma_{C}}\right\\}^{2m_{1}(s)}\left\\{\frac{\sigma_{C}}{\sigma_{*}}\right\\}^{2(m_{2}(s)-1)}.$

Otherwise $\beta_{p}>1$ and

$\displaystyle W(s)\leq
d\sigma_{*}^{2p}\left\\{\frac{\overline{\sigma}_{p}}{\sigma_{*}^{2}}\right\\}^{2m_{1}(s)}\left\\{\frac{\sigma_{C}}{\sigma_{*}}\right\\}^{2(m_{2}(s)-1)}.$

As soon as Proposition 2.7 is available, the proof of Theorem 1.2 follows
similarly as the proof of Theorem 1.1 and the bound for the diagonal in
Theorem 2.5.

Proposition 2.7 follows the same argument shown in [8]. On the other hand, we
did not try to optimize the argument to our setting, instead, we prefer to
prove it directly.

We start by the reduction to tree argument done in [8] for $W^{k}(G)$. In this
case, however, we want to keep track of the exponents for each right leaf that
appears in the final reduction. We hence present the proof for completeness.

######  Lemma 2.8.

Let $G$ be a graph generated by a shape $s\in\mathcal{S}$ and $k_{e}\geq 2$
for each $e\in E(G)$. Then, there exist
$k_{2}^{\prime},...,k_{m_{1}+m_{2}-1}^{\prime}\geq 2$ such that
$\sum_{i}k_{i}^{\prime}=\sum_{e}k_{e}$ and

$\displaystyle W^{k}(G)\leq\max_{T\in\emph{span}(G)}W^{k^{\prime}}(T),$

where $\emph{span}(G)$ is the set of spanning trees of $G$. Moreover, the
maximum can be taken such that whenever $T$ has a right leaf $v\in[m_{1}]$
with unique edge $e=uv\in T$ we have $k_{e}\geq 4$.

###### Proof.

If $G$ is a tree, the equality is rather trivial, so suppose $G$ is not a
tree. In this case, let $r\in[m_{1}]$ be a right vertex in a cycle in $G$. In
particular, there exist two distinct edges $e_{1}=l_{1}r$ and $e_{2}=l_{2}r$
such that $G_{s}=(V(G),E(G)\setminus\\{e_{s}\\})$ is still connected for
$s=1,2$. Let $\bar{k}=k_{e_{1}}+k_{e_{2}}$. Then

$\displaystyle W^{k}(G)=\sum_{w_{1}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq
t_{m_{1}}}\prod_{s=1,2}\left(b_{w_{l_{s}}t_{r}}^{\bar{k}}\prod_{e=ij\neq
e_{1},e_{2}}b_{w_{i}t_{j}}^{k_{e}}\right)^{k_{e_{s}}/\bar{k}}.$

Holder’s Inequality implies that

$\displaystyle W^{k}(G)\leq\max_{s=1,2}\sum_{w_{1}\neq\cdots\neq
w_{m_{2}}}\sum_{t_{1}\neq\cdots\neq
t_{m_{1}}}b_{w_{l_{s}}t_{r}}^{\bar{k}}\prod_{e=ij\neq
e_{1},e_{2}}b_{w_{i}t_{j}}^{k_{e}}=\max_{s=1,2}W^{k^{\prime}_{s}}(G_{s}).$

Notice that $G_{s}$ runs over all vertices of $G$, $|E(G_{s})|=|E(G)|-1$ and
$G_{i}$ is still connected. Moreover, the neighborhood of $v\neq r$ is
preserved and so are the weights for all $v\in[m_{1}]$, namely,

$\displaystyle(k^{\prime}_{s})_{v}:=\sum_{u\in
N(v,G_{s})}(k^{\prime}_{s})_{(uv)}=\sum_{u\in N(v,G)}k_{(uv)}=k_{v}\geq 4,$

where $N(v,G)$ denotes the neighborhood of $v$ in $G$, and the last inequality
follows as $v$ has at least two neighbors in $G$. The result follows by
induction (see [8, Lemma 2.9]). ∎

Let $\mathcal{T}_{m_{1},m_{2}}$ be the set of bipartite trees over
$[m_{2}]\sqcup[m_{1}]$. By Lemma 2.8, we can assume that
$G\in\mathcal{T}_{m_{1},m_{2}}$. In [8], the authors developed a method to
prune leaves of $G$ iteratively. In our case, however, we will prune the right
vertices. To keep the notation clean, let

$\displaystyle
W(G)=\sum_{w\in[d]^{m_{2}}_{\neq}}\sum_{t\in[n]^{m_{1}}_{\neq}}\prod_{e=ij\in
E(G)}b_{w_{i}t_{j}}^{(e)},$

where $(b^{(e)})_{e\in E(G)}$ is a family of $d\times n$ matrices and

$\displaystyle[m]^{I}_{\neq}:=\\{w\in[m]^{I}:w_{k}\neq w_{l}\,,\forall k\neq
l\in I\\}.$

We can easily recover $W^{k}(G)$ by setting $b^{(e)}_{wt}=b^{k_{e}}_{wt}$.

We have the analog of Lemma 2.10 in [8]. Let $\mathcal{L}(G)$ be the set of
leaves of $G$ and for each $v\in\mathcal{L}(G)\cap[m_{1}]$, let $u_{v}$ be its
only neighbor.

######  Lemma 2.9.

For any $G\in\mathcal{T}_{m_{1},m_{2}}$ and $p_{v}\geq 1$ such that

$\displaystyle\sum_{v\in[m_{1}]}\frac{1}{p_{v}}=1,$

we have

$\displaystyle W(G)\leq$
$\displaystyle\prod_{v\in\mathcal{L}(G)\cap[m_{1}]}\left\\{\sum_{i\in[d]}\left(\sum_{j\in[n]}b_{ij}^{(u_{v}v)}\right)^{p_{v}}\right\\}^{\frac{1}{p_{v}}}\times$
$\displaystyle\prod_{\begin{subarray}{c}v\in\mathcal{L}(G)^{c}\cap[m_{1}]\\\
u\in
N(v)\cap\mathcal{L}(G)^{c}\end{subarray}}\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{(uv)}\prod_{a\in
N(v)\setminus\\{u\\}}\left(\sum_{l\neq
i}b_{lj}^{(av)}\right)\right]^{p_{v}}\right\\}^{\frac{1}{p_{v}}\frac{1}{\alpha_{uv}}},$

where $\alpha_{uv}$ satisfies

$\displaystyle\sum_{u\in N(v)\cap\mathcal{L}(G)^{c}}\frac{1}{\alpha_{uv}}=1,$

for all $v\in\mathcal{L}(G)^{c}\cap[m_{1}]$.

Before proving this result, we will use the following easier version. Let
$u=u(v)$ be the choice $u\in N(v)\cap\mathcal{L}(G)^{c}$ that maximizes the
second term in the bound, then the following holds.

######  Corollary 2.10.

For any $G\in\mathcal{T}_{m_{1},m_{2}}$ and $p_{v}\geq 1$ such that

$\displaystyle\sum_{v\in[m_{1}]}\frac{1}{p_{v}}=1,$

we have

$\displaystyle W(G)\leq$
$\displaystyle\prod_{v\in\mathcal{L}(G)\cap[m_{1}]}\left\\{\sum_{i\in[d]}\left(\sum_{j\in[n]}b_{ij}^{(u_{v}v)}\right)^{p_{v}}\right\\}^{\frac{1}{p_{v}}}\times$
$\displaystyle\prod_{v\in\mathcal{L}(G)^{c}\cap[m_{1}]}\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{(uv)}\prod_{a\in
N(v)\setminus\\{u\\}}\left(\sum_{l\neq
i}b_{lj}^{(av)}\right)\right]^{p_{v}}\right\\}^{\frac{1}{p_{v}}}.$

###### Proof of Lemma 2.9.

The proof follows by induction. If $m_{1}=1$, then it is easy to check that
$p_{v}=1$ and

$\displaystyle W(G)\leq\sum_{i\in[d]}\sum_{j\in[n]}\prod_{a\in
N(1^{\prime})\setminus\\{1\\}}b_{ij}^{(11^{\prime})}\left(\sum_{l\neq
i}b_{lj}^{(a1^{\prime})}\right).$

Therefore, if $|N(1^{\prime})|>1$, $W(G)$ has the second form on the bound
shown in the lemma. Otherwise, $|N(v)|=1$ and the bound has the first form.
Hence, we can assume that $m_{1}>1$.

Let $\mathcal{L}=\mathcal{L}(G)$ and $v_{1},v_{2}\in[m_{1}]$ be such that

$\displaystyle d(v_{1},v_{2})=\max_{r,r^{\prime}\in[m_{1}]}d(r,r^{\prime}),$

where the distance is the graph distance. Therefore, both $v_{1}$ and $v_{2}$
have only one neighbor $u_{1}\in N(v_{1})\cap\mathcal{L}^{c}$ and $u_{2}\in
N(v_{2})\cap\mathcal{L}^{c}$. This follows the argument shown in Proposition
2.6. Let then $H$ be the subgraph generated by removing $v_{1}$, $v_{2}$ and
all leaves $(N(v_{1})\cup N(v_{2}))\cap\mathcal{L}$. Denote $H=(I\sqcup
J,E(H))$. Then we have

$\displaystyle
W(G)\leq\sum_{\begin{subarray}{c}w\in[d]^{I}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J}_{\neq}\end{subarray}}$
$\displaystyle\left[\sum_{j\in[n]}b_{w_{u_{1}}j}^{(u_{1}v_{1})}\prod_{a\in
N(v_{1})\setminus\\{u_{1}\\}}\left(\sum_{l\neq
w_{u_{1}}}b_{lj}^{(av_{1})}\right)\right]\times$
$\displaystyle\left[\sum_{j\in[n]}b_{w_{u_{2}}j}^{(u_{2}v_{2})}\prod_{a\in
N(v_{2})\setminus\\{u_{2}\\}}\left(\sum_{l\neq
w_{u_{2}}}b_{lj}^{(av_{2})}\right)\right]\prod_{e=ab\in
E(H)}b_{w_{a}t_{b}}^{(ab)},$

where we define

$\displaystyle\prod_{a\in N(v)\setminus\\{u\\}}\left(\sum_{l\neq
w_{u}}b_{lj}^{(av)}\right)=1,$

if $N(v)\setminus\\{u\\}=\varnothing$. Using Holder’s Inequality, we can
estimate

$\displaystyle W(G)\leq$
$\displaystyle\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{u_{1}}j}^{(u_{1}v_{1})}\prod_{a\in
N(v_{1})\setminus\\{u_{1}\\}}\left(\sum_{l\neq
w_{u_{1}}}b_{lj}^{(av_{1})}\right)\right]^{1+\frac{p_{v_{1}}}{p_{v_{2}}}}\prod_{e=ab\in
E(H)}b_{w_{a}t_{b}}^{(ab)}\right\\}^{\frac{p_{v_{2}}}{p_{v_{1}}+p_{v_{2}}}}\times$
$\displaystyle\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{u_{2}}j}^{(u_{2}v_{2})}\prod_{a\in
N(v_{2})\setminus\\{u_{2}\\}}\left(\sum_{l\neq
w_{u_{2}}}b_{lj}^{(av_{2})}\right)\right]^{1+\frac{p_{v_{2}}}{p_{v_{1}}}}\prod_{e=ab\in
E(H)}b_{w_{a}t_{b}}^{(ab)}\right\\}^{\frac{p_{v_{1}}}{p_{v_{1}}+p_{v_{2}}}}.$
(4)

Note that this inequality preserves the number of summations of right and left
vertices, and also the homogeneity. Note also that if $v\in J$, the neighbors
of $v$ in $H$ and $G$ are the same.

The induction will be based on inequality (2.4). Suppose, for some $r>1$ that

$\displaystyle
W(G)\leq\prod_{h=1}^{H}\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I_{h}}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J_{h}}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{u_{h}}j}^{(u_{h}v_{h})}\prod_{a\in
N(v_{h})\setminus\\{u_{h}\\}}\left(\sum_{l\neq
w_{u_{h}}}b_{lj}^{(av_{h})}\right)\right]^{q_{h}}\prod_{e=ab\in
E(G_{h})}b_{w_{a}t_{b}}^{(ab)}\right\\}^{\frac{1}{\alpha_{h}}},$

where $H<\infty$, $N(v)$ is the neighbor of $v$ in $G$,

  1. (1)

For every $h$, $u_{h}\in I_{h}$, $v_{h}\notin J_{h}$ and $av_{h}\notin
E(G_{h})$ for every $a\in N(v_{h})\setminus\\{u_{h}\\}$;

  2. (2)

For every $h$, $G_{h}$ is a tree over $I_{h}\sqcup J_{h}$ and $|J_{h}|=r$;

  3. (3)

The inequality is $1$-homogeneous in all the variables $b^{(e)}$ and it
preserves the number of left and right summations;

  4. (4)

The exponents $q_{h}$ satisfies

$\displaystyle q_{h}=\sum_{v\in[m_{1}]\setminus
J_{h}}\frac{p_{v_{h}}}{p_{v}},$

and $\alpha_{h}\geq 1$.

We aim to show that if this holds for $r>1$, so does it for $r-1$. Indeed, fix
one of the terms

$\displaystyle
T_{h}:=\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I_{h}}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J_{h}}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{u_{h}}j}^{(u_{h}v_{h})}\prod_{a\in
N(v_{h})\setminus\\{u_{h}\\}}\left(\sum_{l\neq
w_{u_{h}}}b_{lj}^{(av_{h})}\right)\right]^{q_{h}}\prod_{e=ab\in
E(G_{h})}b_{w_{a}t_{b}}^{(ab)}\right\\}.$

Since $G_{h}$ is a tree and $r>1$, there exists $r_{h}$ such that $u_{h}$ is
not a leaf of $r_{h}$ and $r_{h}$ has only one neighbor $l_{h}$ such that
$N(l_{h})>1$ in $G_{h}$. Let then $H_{h}$ be the subgraph (a tree) of $G_{h}$
where we remove $r_{h}$ and all of its leaves and let
$H_{h}=(I_{h^{\prime}}\sqcup J_{h^{\prime}},E(H_{h}))$, then

$\displaystyle
T_{h}\leq\sum_{\begin{subarray}{c}w\in[d]^{I_{h^{\prime}}}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J_{h^{\prime}}}_{\neq}\end{subarray}}$
$\displaystyle\left[\sum_{j\in[n]}b_{w_{u_{h}}j}^{(u_{h}v_{h})}\prod_{a\in
N(v_{h})\setminus\\{u_{h}\\}}\left(\sum_{l\neq
w_{u_{h}}}b_{lj}^{(av_{h})}\right)\right]^{q_{h}}\times$
$\displaystyle\left[\sum_{j\in[n]}b_{w_{l_{h}}j}^{(l_{h}r_{h})}\prod_{a\in
N(r_{h})\setminus\\{l_{h}\\}}\left(\sum_{l\neq
w_{l_{h}}}b_{lj}^{(ar_{h})}\right)\right]\prod_{e=ab\in
E(G_{h})}b_{w_{a}t_{b}}^{(ab)}.$

We can thus estimate by Holder’s Inequality that

$\displaystyle T_{h}\leq$
$\displaystyle\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I_{h^{\prime}}}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J_{h^{\prime}}}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{u_{h}}j}^{(u_{h}v_{h})}\prod_{a\in
N(v_{h})\setminus\\{u_{h}\\}}\left(\sum_{l\neq
w_{u_{h}}}b_{lj}^{(av_{h})}\right)\right]^{q_{h}^{\prime}}\prod_{e=ab\in
E(G_{h})}b_{w_{a}t_{b}}^{(ab)}\right\\}^{1/\alpha_{h}}\times$
$\displaystyle\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I_{h^{\prime}}}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J_{h^{\prime}}}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{l_{h}}j}^{(l_{h}r_{h})}\prod_{a\in
N(r_{h})\setminus\\{l_{h}\\}}\left(\sum_{l\neq
w_{l_{h}}}b_{lj}^{(ar_{h})}\right)\right]^{q}\prod_{e=ab\in
E(G_{h})}b_{w_{a}t_{b}}^{(ab)}\right\\}^{1/q},$

where $q_{h}^{\prime}/q_{h}$ and $q$ are conjugate exponents. Again, the
inequality is $1$-homogeneous in all the variables it involves, and it
preserves the number of summations. Moreover, we can set

$\displaystyle q_{h}^{\prime}=\sum_{v\in[m_{1}]\setminus
J_{h^{\prime}}}\frac{p_{v_{h}}}{p_{v}}$ $\displaystyle
q=\sum_{v\in[m_{1}]\setminus J_{h^{\prime}}}\frac{p_{l_{h}}}{p_{v}},$

and it is easy to check that indeed $q_{h}^{\prime}/q_{h}$ and $q$ are
conjugate exponents. Note that each new term has the same form as in the
induction step with $|J_{h^{\prime}}|=r-1$, therefore the induction is proved.

The previous argument also shows that the induction holds for $r=0$. Since the
choice of $u\in\mathcal{L}^{c}\cap N(v)$ is arbitrary for each $v$, we deduce

$\displaystyle W(G)$
$\displaystyle\leq\prod_{h=1}^{H}\left\\{\sum_{\begin{subarray}{c}w\in[d]^{I_{h}}_{\neq}\end{subarray}}\sum_{\begin{subarray}{c}t\in[n]^{J_{h}}_{\neq}\end{subarray}}\left[\sum_{j\in[n]}b_{w_{u_{h}}j}^{(u_{h}v_{h})}\prod_{a\in
N(v_{h})\setminus\\{u_{h}\\}}\left(\sum_{l\neq
w_{u_{h}}}b_{lj}^{(av_{h})}\right)\right]^{q_{h}}\prod_{e=ab\in
E(G_{h})}b_{w_{a}t_{b}}^{(ab)}\right\\}^{\frac{1}{\alpha_{h}}}$
$\displaystyle\leq\prod_{e=uv\in
E(G):u\in\mathcal{L}^{c}}\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{(e)}\prod_{a\in
N(v)\setminus\\{u\\}}\left(\sum_{l\neq
i}b_{lj}^{(av)}\right)\right]^{p_{v}}\right\\}^{\frac{1}{\alpha_{e}}}.$

The conclusion of the lemma follows by the renormalization
$\alpha_{uv}\leftarrow p_{v}\alpha_{uv}$ and splitting the product over
$v\in\mathcal{L}$ and $v\notin\mathcal{L}$. ∎

Now we can prove Proposition 2.7.

###### Proof of Proposition 2.7.

Let $|k|=\sum_{v}k_{v}=2p$ and $\mathcal{L}=\mathcal{L}(G)\cap[m_{1}]$. By
Lemma 2.8 and Corollary 2.10 with $p_{v}=|k|/k_{v}$, we get

$\displaystyle W^{k}(G)\leq W^{k^{\prime}}(T)\leq$
$\displaystyle\prod_{v\in\mathcal{L}}\left\\{\sum_{i\in[d]}\left(\sum_{j\in[n]}b_{ij}^{k_{v}}\right)^{\frac{|k|}{k_{v}}}\right\\}^{\frac{k_{v}}{|k|}}\times$
$\displaystyle\prod_{v\in\mathcal{L}^{c}}\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{k_{uv}}\prod_{a\in
N(v)\setminus\\{u\\}}\left(\sum_{l\neq
i}b_{lj}^{k_{av}}\right)\right]^{\frac{|k|}{k_{v}}}\right\\}^{\frac{k_{v}}{|k|}},$

where $T$ is the spanning tree of $G$ that maximizes
$W^{k^{\prime}}(T^{\prime})$ in Lemma 2.8. Since $k_{v}\geq 4$ and
$b_{ij}^{k_{uv}}\leq b_{ij}^{2}\sigma_{*}^{k_{uv}-2}$, we get

$\displaystyle W^{k}(G)\leq$
$\displaystyle\sigma_{*}^{|k|-4|\mathcal{L}|-2\sum_{v\in\mathcal{L}^{c}}|N(v)|}\prod_{v\in\mathcal{L}}\left\\{\sum_{i\in[d]}\left(\sum_{j\in[n]}b_{ij}^{4}\right)^{\frac{|k|}{k_{v}}}\right\\}^{\frac{k_{v}}{|k|}}\times$
$\displaystyle\prod_{v\in\mathcal{L}^{c}}\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{2}\prod_{a\in
N(v)\setminus\\{u\\}}\left(\sum_{l\neq
i}b_{lj}^{2}\right)\right]^{\frac{|k|}{k_{v}}}\right\\}^{\frac{k_{v}}{|k|}}.$

As $T$ is a spanning tree, we have

$\displaystyle\sum_{v\in\mathcal{L}^{c}}|N(v)|+|\mathcal{L}|=m_{2}+m_{1}-1;$
$\displaystyle\sum_{v\in\mathcal{L}^{c}}|N(v)|-2|\mathcal{L}^{c}|=m_{2}-m_{1}-1+|\mathcal{L}|.$

Moreover, we can remove $\sigma_{C}$ from each term in the second product to
get that

$\displaystyle W^{k}(G)\leq$
$\displaystyle\sigma_{*}^{|k|-2(m_{1}+m_{2}-1)-2|\mathcal{L}|}\sigma_{C}^{2(m_{1}+m_{2}-1)+2|\mathcal{L}|}\prod_{v\in\mathcal{L}}\left\\{\sum_{i\in[d]}\left(\sum_{j\in[n]}b_{ij}^{4}\right)^{\frac{|k|}{k_{v}}}\right\\}^{\frac{k_{v}}{|k|}}\times$
$\displaystyle\prod_{v\in\mathcal{L}^{c}}\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}b_{ij}^{2}\left(\sum_{l\neq
i}b_{lj}^{2}\right)\right]^{\frac{|k|}{k_{v}}}\right\\}^{\frac{k_{v}}{|k|}}.$

Finally, the inequality of the norms in $\mathbb{R}^{d}$ implies that

$\displaystyle\|\cdot\|_{\frac{|k|}{k_{v}}}\leq
d^{\frac{k_{v}-4}{|k|}}\|\cdot\|_{\frac{|k|}{4}},$

so we deduce

$\displaystyle W^{k}(G)\leq
d\sigma_{*}^{|k|-2(m_{1}+m_{2}-1)-2|\mathcal{L}|}\sigma_{C}^{2(m_{1}+m_{2}-1)+2|\mathcal{L}|}\sigma_{p}^{2|\mathcal{L}|}\bar{\sigma}_{p}^{2|\mathcal{L}^{c}|}.$

The proof of Proposition 2.7 follows by a straightforward computation and the
fact that $0\leq|\mathcal{L}|\leq m_{1}$. ∎

######  Remark 2.11.

Note that we rather proved Theorem 1.2 with a parameter $\sigma_{p}^{\prime}$
instead of $\sigma_{p}$, where $\sigma_{p}^{\prime}$ only takes $l\neq i$,
that is,

$\displaystyle\sigma_{p}^{\prime}=\left\\{\sum_{i\in[d]}\left[\sum_{j\in[n]}\sum_{l\neq
i}b_{ij}^{2}b_{lj}^{2}\right]^{p/2}\right\\}^{1/p}.$

This minor change is only important for cases where the contribution of a
column $X_{j}$ appears only in the diagonal part, that is, when
$X_{j}=b_{ij}e_{i}$ for some $i$.

##  3\. Examples

Let us start by recalling the previous known results in [4, 2].

######  Theorem 3.1 (Theorem 2.1 in [4]).

In the setting of Theorem 1.1, we have

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|$
$\displaystyle\leq(1+\varepsilon)\left\\{2\sigma_{R}\sigma_{C}+\sigma_{C}^{2}+C(\varepsilon)(\sigma_{C}\sigma_{*}+\sigma_{R}\sigma_{*})\sqrt{\log(n\wedge
d)}+C^{2}(\varepsilon)\sigma_{*}^{2}\log(n\wedge d)\right\\}.$

######  Theorem 3.2 (Theorem 3.12 in [2]).

Let $X$ be a $d\times n$ Gaussian matrix with independent entries and
$X_{ij}=b_{ij}g_{ij}$, for $b_{ij}\geq 0$. Then

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|$
$\displaystyle\leq\|X_{\emph{free}}X_{\emph{free}}^{T}-\operatorname{\mathbb{E}}XX^{T}\otimes
1\|+C\left\\{\sigma(X)\tilde{v}(X)\log^{3/4}(nd)+\tilde{v}^{2}(X)\log^{3/2}(nd)\right\\}.$

######  Corollary 3.3.

In the setting of Theorem 3.2, we have

$\displaystyle\|X_{\emph{free}}X_{\emph{free}}^{T}-\operatorname{\mathbb{E}}XX^{T}\otimes
1\|$ $\displaystyle\leq
2\max_{i\in[d]}\left(\sum_{j\in[n]}\sum_{l\in[d]}b_{ij}^{2}b_{lj}^{2}\right)^{1/2}+\sigma_{C}^{2}$
$\displaystyle=2\sigma_{\infty}+\sigma_{C}^{2}$

and

$\displaystyle\sigma(X)=\max(\sigma_{C},\sigma_{R});$
$\displaystyle\tilde{v}(X)^{2}\asymp\sigma_{*}\sigma(X).$

Therefore, we have

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|$
$\displaystyle\leq
2\sigma_{\infty}+\sigma_{C}^{2}+C\left[\sigma_{*}^{1/2}\sigma_{C}^{3/2}+\sigma_{*}^{1/2}\sigma_{R}^{3/2}\right]\log^{3/4}(nd)+C\left[\sigma_{*}\sigma_{C}+\sigma_{*}\sigma_{R}\right]\log^{3/2}(nd).$
(5)

###### Proof.

Let $X_{j}$ be the $j$th column of $X$. Then

$\displaystyle\Sigma_{j}=\operatorname{\mathbb{E}}X_{j}X_{j}^{T}=\text{diag}(b_{ij}^{2}).$

Hence

$\displaystyle\left\|\sum_{j\in[n]}\Sigma_{j}\right\|=\max_{i\in[d]}\sum_{j\in[n]}b_{ij}^{2}=\sigma_{R}^{2};$
$\displaystyle\max_{j\in[n]}\text{Tr}(\Sigma_{j})=\max_{j\in[n]}\sum_{i\in[d]}b_{ij}^{2}=\sigma_{C}^{2}.$

The computation for the parameters $\tilde{v}(X)$ and $\sigma(X)$ then follows
by Lemma 3.8 in [2].

On the other hand, denote

$\displaystyle X=\sum_{i,j}g_{ij}b_{ij}E_{ij}=\sum_{k}g_{k}A_{k},$

where $E_{ij}$ is the canonical basis of the space of $d\times n$ matrices.
Then the authors of [2] computed that $X_{\text{free}}=U+V$, where

$\displaystyle U=\sum_{k}A_{k}\otimes l(e_{k});$ $\displaystyle
V=\sum_{k}A_{k}\otimes l^{*}(e_{k}),$

and $l$ is the creation operator of the free Fock space over
$\mathbb{C}^{nd}$. In particular, we have $l^{*}(e_{k})l(e_{j})=\delta_{kj}1$.
Therefore,

$\displaystyle VV^{*}=\sum_{k}A_{k}A_{k}^{*}\otimes
1=\operatorname{\mathbb{E}}XX^{T}\otimes 1;$ $\displaystyle
U^{*}U=\sum_{k}A_{k}^{*}A_{k}\otimes 1=\operatorname{\mathbb{E}}X^{T}X\otimes
1.$

Hence they deduced that

$\displaystyle\|X_{\text{free}}X_{\text{free}}^{T}-\operatorname{\mathbb{E}}XX^{T}\otimes
1\|\leq\|UV^{*}+VU^{*}+UU^{*}\|\leq 2\|UV^{*}\|+\|UU^{*}\|.$

The second one follows easily as

$\displaystyle\|UU^{*}\|=\|\operatorname{\mathbb{E}}X^{T}X\|=\sigma_{C}^{2}.$

On the other hand, in [2], they used
$\|UV^{*}\|\leq\|U\|\|V\|=\sigma_{R}\sigma_{C}$ to bound the first term.
However, in the case of independent entries, it is a straightforward
computation to check that

$\displaystyle\|UV^{*}\|=\sigma_{\infty},$

and the result follows. ∎

Now we discuss various examples and present how Theorem 1.1 improves upon
Theorems 3.1 and 3.2.

######  Example 3.4.

Assume the columns of $X$ are i.i.d, namely, $b_{ij}=b_{i}$. In this case, we
have

$\displaystyle\bullet\sigma_{C}=\|b\|_{2};$
$\displaystyle\bullet\sigma_{R}=\sqrt{n}\|b\|_{\infty};$
$\displaystyle\bullet\sigma_{*}=\|b\|_{\infty};$
$\displaystyle\bullet\tilde{\sigma}_{\infty}\leq\sqrt{n}\|b\|_{\infty}^{2};$
$\displaystyle\bullet\bar{\sigma}_{\infty}=\sqrt{n}\|b\|_{\infty}^{2};$
$\displaystyle\bullet\sigma_{\infty}\leq\sqrt{n}\|b\|_{\infty}\|b\|_{2}.$

In particular,

$\displaystyle\frac{\tilde{\sigma}_{\infty}\sigma_{C}}{\sigma_{*}}\leq\sqrt{n}\|b\|_{\infty}\|b\|_{2}.$

Hence, both bounds shown in Theorem 1.1 yield

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\sqrt{n}\|b\|_{2}\|b\|_{\infty}+\|b\|_{2}^{2}+$ $\displaystyle
C\left[\|b\|_{2}\|b\|_{\infty}+\sqrt{n}\|b\|_{\infty}^{2}\right]\sqrt{\log(n\wedge
d)}+$ $\displaystyle C\|b\|_{\infty}^{2}\log(n\wedge d).$

The leading term agrees with the sharp bound derived in [4, 7].

######  Example 3.5.

Let $X$ be a Gaussian matrix with i.i.d rows, that is, $b_{ij}=b_{j}$. In this
case, we have

$\displaystyle\bullet\sigma_{C}=\sqrt{d}\|b\|_{\infty};$
$\displaystyle\bullet\sigma_{R}=\|b\|_{2};$
$\displaystyle\bullet\sigma_{*}=\|b\|_{\infty};$
$\displaystyle\bullet\sigma_{\infty}=\sqrt{d-1}\|b\|_{4}^{2};$
$\displaystyle\bullet\tilde{\sigma}_{\infty}=\bar{\sigma}_{\infty}=\|b\|_{4}^{2}.$

In particular,

$\displaystyle\frac{\tilde{\sigma}_{\infty}\sigma_{C}}{\sigma_{*}}=\sqrt{d}\|b\|_{4}^{2}.$

Hence, Theorem 1.1 implies that

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\sqrt{d}\|b\|_{4}^{2}+d\|b\|_{\infty}^{2}+$ $\displaystyle
C\left[\sqrt{d}\|b\|_{\infty}^{2}+\|b\|_{4}^{2}\right]\sqrt{\log(n\wedge d)}+$
$\displaystyle C\|b\|_{\infty}^{2}\log(n\wedge d).$

In this case, the error factor is smaller than the leading one, hence

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\sqrt{d}\|b\|_{4}^{2}+d\|b\|_{\infty}^{2}.$

This agrees with the sharp result in [4]. However, they had to derive a
different method to prove this case, whereas we deduce directly from our main
result that covers all cases.

Moreover, (3.3) gives

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\sqrt{d}\|b\|_{4}^{2}+d\|b\|_{\infty}^{2}+$ $\displaystyle
C\left[\|b\|_{2}^{3/2}\|b\|_{\infty}^{1/2}+d^{3/4}\|b\|_{\infty}^{2}\right]\log^{3/4}(nd)+$
$\displaystyle
C\left[\sqrt{d}\|b\|_{\infty}+\|b\|_{2}\right]\|b\|_{\infty}\log^{3/2}(nd).$

Here, we observe that the error factor is not necessarily smaller than the
leading one.

######  Example 3.6.

Consider $b_{ij}=a_{i}b_{j}$. Then

$\displaystyle\bullet\sigma_{C}=\|a\|_{2}\|b\|_{\infty};$
$\displaystyle\bullet\sigma_{R}=\|a\|_{\infty}\|b\|_{2};$
$\displaystyle\bullet\sigma_{*}=\|a\|_{\infty}\|b\|_{\infty};$
$\displaystyle\bullet\tilde{\sigma}_{\infty}\leq\|b\|_{4}^{2}\|a\|_{\infty}^{2};$
$\displaystyle\bullet\bar{\sigma}_{\infty}=\|b\|_{4}^{2}\|a\|_{\infty}^{2};$
$\displaystyle\bullet\sigma_{\infty}\leq\|b\|_{4}^{2}\|a\|_{2}\|a\|_{\infty}.$

We observe that

$\displaystyle\frac{\tilde{\sigma}_{\infty}\sigma_{C}}{\sigma_{*}}\leq\|b\|_{4}^{2}\|a\|_{2}\|a\|_{\infty}.$

Therefore, Theorem 1.1 implies that

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\|b\|_{4}^{2}\|a\|_{2}\|a\|_{\infty}+\|a\|_{2}^{2}\|b\|_{\infty}^{2}+$
$\displaystyle
C\left[\|a\|_{2}\|a\|_{\infty}\|b\|_{\infty}^{2}+\|b\|_{4}^{2}\|a\|_{\infty}^{2}\right]\sqrt{\log(n\wedge
d)}+$ $\displaystyle C\|a\|_{\infty}^{2}\|b\|_{\infty}^{2}\log(n\wedge d).$

The result in [4] yields

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\|b\|_{2}\|b\|_{\infty}\|a\|_{2}\|a\|_{\infty}+\|a\|_{2}^{2}\|b\|_{\infty}^{2}+$
$\displaystyle
C\left[\|a\|_{2}\|a\|_{\infty}\|b\|_{\infty}^{2}+\|b\|_{2}\|b\|_{\infty}\|a\|_{\infty}^{2}\right]\sqrt{\log(n\wedge
d)}+$ $\displaystyle C\|a\|_{\infty}^{2}\|b\|_{\infty}^{2}\log(n\wedge d).$

And finally, (3.3) gives

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|\lesssim$
$\displaystyle\|b\|_{4}^{2}\|a\|_{2}\|a\|_{\infty}+\|a\|_{2}^{2}\|b\|_{\infty}^{2}+$
$\displaystyle
C\left[\|a\|_{2}^{3/2}\|a\|_{\infty}^{1/2}\|b\|_{\infty}^{2}+\|b\|_{2}^{3/2}\|b\|_{\infty}^{1/2}\|a\|_{\infty}^{2}\right]\log^{3/4}(nd)+$
$\displaystyle
C\left[\|a\|_{2}\|b\|_{\infty}+\|b\|_{2}\|a\|_{\infty}\right]\|a\|_{\infty}\|b\|_{\infty}\log^{3/2}(nd).$

In this case, Theorem 1.1 strictly improves both and sheds light on the 4th-
moment appearing for $b_{j}$.

Our final example is where all columns have approximately the same norm.

######  Example 3.7.

Suppose there exists $K\geq 1$ such that

$\displaystyle\frac{1}{K}\|b_{k}\|_{2}\leq\|b_{j}\|_{2}\leq K\|b_{k}\|_{2},$

for all $k,l\in[n]$. Then it is easy to compute

$\displaystyle\beta_{\infty}\leq K.$

By Theorem 1.1, we have

$\displaystyle\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|$
$\displaystyle\leq(1+\varepsilon)\left\\{2K\sigma_{\infty}+\sigma_{C}^{2}+C(\varepsilon)\sigma_{*}\left(\sigma_{C}+\sigma_{R}\right)\sqrt{\log(n\wedge
d)}+C^{2}(\varepsilon)\sigma_{*}^{2}\log(n\wedge d)\right\\}.$

Here, we do not require any additional structure on $B$ and the previous known
results only show the leading term with $\sigma_{C}\sigma_{R}$ in [4] and a
large error factor in [2].

##  4\. Lower bounds

We first begin the lower bounds for the $p$-moment of the Schatten norm.

######  Proposition 4.1.

For any even $p\geq 2$ and $X$ satisfying the assumptions in Theorem 1.1, we
have

$\displaystyle\left(\operatorname{\mathbb{E}}\emph{Tr}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})^{p}\right)^{1/p}\gtrsim\sigma_{p}+\sigma_{C}^{2}+\sqrt{p}\bar{\sigma}_{p}+pb_{p}^{2}.$

###### Proof.

By Lemma 2.2, the joint moments of $g$ and $g^{2}-1$ are always positive, thus
it follows that

$\displaystyle\left(\operatorname{\mathbb{E}}\text{Tr}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})^{p}\right)^{1/p}\geq\left(\operatorname{\mathbb{E}}\text{Tr}(\text{Diag}(XX^{T})-\operatorname{\mathbb{E}}XX^{T})^{p}\right)^{1/p}\gtrsim\sqrt{p}\bar{\sigma}_{p}+pb_{p}^{2}.$

For the leading factor, note that the Schatten norm is always lower bounded by
the mixed $l_{2}(l_{p})$ norm (see Lemma 2.12 in [8]), then Jensen’s
Inequality implies that

$\displaystyle\left(\operatorname{\mathbb{E}}\text{Tr}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})^{p}\right)^{1/p}$
$\displaystyle\geq\left[\sum_{i\in[d]}\left(\sum_{l\in[d]}\operatorname{\mathbb{E}}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})^{2}_{il}\right)^{p/2}\right]^{1/p}.$

The latter can be estimated as

$\displaystyle\operatorname{\mathbb{E}}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})_{il}^{2}$
$\displaystyle=\sum_{j\in[n]}\operatorname{\mathbb{E}}(X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{j}X_{j})^{2}_{il}$
$\displaystyle=\sum_{j\in[n]}\operatorname{\mathbb{E}}\left(b_{ij}b_{lj}(g_{ij}g_{lj}-\mathbf{1}_{i=l})\right)^{2}$
$\displaystyle\geq\sum_{j\in[n]}b_{ij}^{2}b_{lj}^{2}.$

Hence

$\displaystyle\left(\operatorname{\mathbb{E}}\text{Tr}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})^{p}\right)^{1/p}$
$\displaystyle\geq\left[\sum_{i\in[d]}\left(\sum_{j\in[n]}\sum_{l\in[d]}b_{ij}^{2}b_{lj}^{2}\right)^{p/2}\right]^{1/p}$
$\displaystyle\geq\sigma_{p}.$

Finally, let $j^{*}$ be the column with the largest Euclidean norm, that is,
$\|b_{j^{*}}\|_{2}=\sigma_{C}$, then

$\displaystyle\left(\operatorname{\mathbb{E}}\text{Tr}(XX^{T}-\operatorname{\mathbb{E}}XX^{T})^{p}\right)^{1/p}\geq\left(\operatorname{\mathbb{E}}\text{Tr}(X_{j^{*}}X_{j^{*}}^{T}-\operatorname{\mathbb{E}}X_{j^{*}}X_{j^{*}}^{T})^{p}\right)^{1/p}.$

The sharp result for the i.i.d case proved by Koltchinskii and Lounici in [7]
implies that

$\displaystyle\left(\operatorname{\mathbb{E}}\text{Tr}(X_{j^{*}}X_{j^{*}}^{T}-\operatorname{\mathbb{E}}X_{j^{*}}X_{j^{*}}^{T})^{p}\right)^{1/p}$
$\displaystyle\geq\operatorname{\mathbb{E}}\|X_{j^{*}}X_{j^{*}}^{T}-\operatorname{\mathbb{E}}X_{j^{*}}X_{j^{*}}^{T}\|$
$\displaystyle\gtrsim\sigma_{C}^{2},$

where we assume $p$ is even for the first inequality. ∎

For the operator norm, we have the following result.

######  Lemma 4.2.

Let $X$ be a random matrix satisfying the assumptions of Theorem 1.1. Then

$\displaystyle\left(\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|^{2}\right)^{1/2}\gtrsim\sigma_{\infty}+\sigma_{C}^{2}.$

###### Proof.

Let $S_{j}=X_{j}X_{j}^{T}-\operatorname{\mathbb{E}}X_{i}X_{i}^{T}$, then
Tropp’s result in [10] implies that

$\displaystyle(\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|^{2})^{1/2}\gtrsim\left\|\sum_{j\in[n]}\operatorname{\mathbb{E}}S_{j}S_{j}^{T}\right\|^{1/2}+(\operatorname{\mathbb{E}}\max_{j\in[n]}\|S_{j}\|^{2})^{1/2}.$

The matrix in the first bound can then be computed as

$\displaystyle\sum_{j\in[n]}\operatorname{\mathbb{E}}X_{j}X_{j}^{T}X_{j}X_{j}^{T}-(\operatorname{\mathbb{E}}X_{j}X_{j}^{T})^{2}.$

This can easily be seen as a diagonal matrix (a similar argument was proved in
[4]) and lower bounded by

$\displaystyle\left\|\sum_{j\in[n]}\operatorname{\mathbb{E}}X_{j}X_{j}^{T}X_{j}X_{j}^{T}-(\operatorname{\mathbb{E}}X_{j}X_{j}^{T})^{2}\right\|\geq\sigma_{\infty}^{2},$

hence

$\displaystyle(\operatorname{\mathbb{E}}\|XX^{T}-\operatorname{\mathbb{E}}XX^{T}\|^{2})^{1/2}\gtrsim\sigma_{\infty}.$

On the other hand, the second term can be bounded as

$\displaystyle(\operatorname{\mathbb{E}}\max_{j\in[n]}\|S_{j}\|^{2})^{1/2}\geq\max_{j\in[n]}(\operatorname{\mathbb{E}}\|S_{j}\|^{2})^{1/2}\gtrsim\sigma_{C}^{2},$

where we again use the lower bound of [7].

∎

## References

  * [1] Z. D. Bai and Y. Q. Yin  “Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix”  In _Ann. Probab._ 16.4, 1988, pp. 1729–1741  URL: http://links.jstor.org/sici?sici=0091-1798(198810)16:4<1729:NASCFA>2.0.CO;2-C&origin=MSN
  * [2] Afonso S Bandeira, March T Boedihardjo and Ramon Handel  “Matrix concentration inequalities and free probability”  In _arXiv preprint arXiv:2108.06312_ , 2021
  * [3] Afonso S. Bandeira and Ramon Handel  “Sharp nonasymptotic bounds on the norm of random matrices with independent entries”  In _Ann. Probab._ 44.4, 2016, pp. 2479–2506  DOI: 10.1214/15-AOP1025
  * [4] T. Tony Cai, Rungang Han and Anru R. Zhang  “On the non-asymptotic concentration of heteroskedastic Wishart-type matrix”  In _Electron. J. Probab._ 27, 2022, pp. Paper No. 29, 40  DOI: 10.1214/22-ejp758
  * [5] Djalil Chafaï, Olivier Guédon, Guillaume Lecué and Alain Pajor  “Interactions between compressed sensing random matrices and high dimensional geometry” 37, Panoramas et Synthèses [Panoramas and Syntheses]  Société Mathématique de France, Paris, 2012, pp. 181
  * [6] Ramon Handel  “On the spectral norm of Gaussian random matrices”  In _Trans. Amer. Math. Soc._ 369.11, 2017, pp. 8161–8178  DOI: 10.1090/tran/6922
  * [7] Vladimir Koltchinskii and Karim Lounici  “Concentration inequalities and moment bounds for sample covariance operators”  In _Bernoulli_ 23.1, 2017, pp. 110–133  DOI: 10.3150/15-BEJ730
  * [8] Rafał Latała, Ramon Handel and Pierre Youssef  “The dimension-free structure of nonhomogeneous random matrices”  In _Invent. Math._ 214.3, 2018, pp. 1031–1080  DOI: 10.1007/s00222-018-0817-x
  * [9] Arshak Minasyan and Nikita Zhivotovskiy  “Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians”  In _arXiv preprint arXiv:2301.09024_ , 2023
  * [10] Joel A. Tropp  “The expected norm of a sum of independent random matrices: an elementary approach”  In _High dimensional probability VII_ 71, Progr. Probab.  Springer, [Cham], 2016, pp. 173–202  DOI: 10.1007/978-3-319-40519-3\\_8
  * [11] Roman Vershynin  “High-dimensional probability: An introduction with applications in data science”  Cambridge university press, 2018
  * [12] Anru R. Zhang and Yuchen Zhou  “On the non-asymptotic and sharp lower tail bounds of random variables”  In _Stat_ 9, 2020, pp. e314, 11  DOI: 10.1002/sta4.314
  * [13] Nikita Zhivotovskiy  “Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle”  In _arXiv preprint arXiv:2108.08198_ , 2021