\section{Proof of $\ell_{2}$ estimation guarantees (Theorem~\ref{thm:optimality-L2-rank-r})}

\label{sec:proof-l2-loss}As before, we assume that $\bm{\Pi}=\bm{I}_{r}$
for simplicity of notation throughout this section.

\subsection{$\ell_{2}$ risk for tensor factor estimation}

\label{subsec:proof-l2-loss-Tensor-factors}

Fix an arbitrary $1\leq l\leq r$. Recalling the decomposition in
(\ref{eq:U-loss-decomp}), (\ref{def:W1-W4}) and (\ref{def:W}),
we can write $\bm{u}_{l}-\bm{u}_{l}^{\star}=\bm{Z}_{:,l}+\bm{W}_{:,l}.$
In what follows, we will first prove that $\bm{Z}_{:,l}$ converges
to a Gaussian random vector in distribution. Then we can use the standard
Gaussian concentration inequality to show that the $\ell_{2}$ norm
of the Gaussian random vector concentrates around its expectation.
Combined with the observation that the $\ell_{2}$ norm of $\bm{W}_{:,l}$
is negligible as shown in (\ref{eq:W-2inf-norm-UB}) (established
in Lemmas~\ref{lemma:U-loss-dist-W1}-\ref{lemma:U-loss-dist-W4}),
this implies the advertised bound on the $\ell_{2}$ norm of $\bm{u}_{l}-\bm{u}_{l}^{\star}$.

Now we begin the proof. For convenience of presentation, we adopt
the notation in (\ref{def:V-true}) that $\bm{V}^{\star}:=\widetilde{\bm{U}}^{\star}(\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}$.
Then we can express
\[
\bm{Z}_{:,l}=\sqrt{2}\sum_{1\leq i,k\leq d}p^{-1}E_{i,i,k}\chi_{i,i,k}V_{(i,i),l}^{\star}\bm{e}_{k}+\sum_{1\leq i,j,k\leq d}p^{-1}E_{i,j,k}\chi_{i,j,k}V_{(i,j),l}^{\star}\bm{e}_{k}
\]
as a sum of independent zero-mean random vectors in $\mathbb{R}^{d}$.
Let us first compute the covariance matrix $\bm{S}_{l}^{\star}:=\mathbb{E}\big[\bm{Z}_{:,l}(\bm{Z}_{:,l})^{\top}\big]$.
Straightforward computation yields that for each $1\leq i\leq d$,
\begin{align}
\left(\bm{S}_{l}^{\star}\right)_{i,i} & =2\sum_{1\leq k_{1},k_{2}\leq d}p^{-1}\sigma_{i,k_{1},k_{2}}^{2}V_{(k_{1},k_{2}),l}^{\star2};\label{eq:cov-u-diag-entry}
\end{align}
and for each $1\leq i\neq j\leq d$,
\begin{align}
\left(\bm{S}_{l}^{\star}\right)_{i,j} & =2\sqrt{2}\,p^{-1}\sigma_{i,i,j}^{2}V_{(i,i),l}^{\star}V_{(i,j),l}^{\star}+2\sqrt{2}\,p^{-1}\sigma_{i,j,j}^{2}V_{(j,j),l}^{\star}V_{(i,j),l}^{\star}+\sum_{k:k\neq i,j}4\,p^{-1}\sigma_{i,j,k}^{2}V_{(i,k),l}^{\star}V_{(j,k),l}^{\star}\nonumber \\
 & =4\sum_{1\leq k\leq d}p^{-1}\sigma_{i,j,k}^{2}V_{(i,k),l}^{\star}V_{(j,k),l}^{\star}-\big(4-2\sqrt{2}\big)p^{-1}\sigma_{i,i,j}^{2}V_{(i,i),l}^{\star}V_{(i,j),l}^{\star}-\big(4-2\sqrt{2}\big)p^{-1}\sigma_{i,j,j}^{2}V_{(j,j),l}^{\star}V_{(i,j),l}^{\star}.\label{eq:cov-u-off-diag-entry}
\end{align}
Lemma~\ref{lemma:u-l2-loss-cov-matrix} below collects several properties
of $\bm{S}_{l}^{\star}$ and the proof is deferred to the end of this
section.

\begin{lemma}\label{lemma:u-l2-loss-cov-matrix}Instate the assumptions
of Theorem~\ref{thm:optimality-L2}. One has
\begin{align*}
 & \lambda_{\max}(\bm{S}_{l}^{\star})\lesssim\frac{\sigma_{\max}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}},\qquad\lambda_{\min}(\bm{S}_{l}^{\star})\gtrsim\frac{\sigma_{\min}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}};\\
 & \mathsf{tr}(\bm{S}_{l}^{\star})=\frac{\left(2+o\left(1\right)\right)\sigma_{\max}^{2}d}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}\text{,\ensuremath{\qquad\left\Vert \bm{S}_{l}^{\star}\right\Vert _{\mathrm{F}}\lesssim\frac{\sigma_{\max}^{2}\sqrt{d}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.}}
\end{align*}
\end{lemma}

Recall that we want to show $\bm{Z}_{:,l}$ converges to a Gaussian
random vector $\bm{g}_{l}\sim\mathcal{N}(\bm{0},\bm{S}_{l}^{\star})$
in distribution. By the Cram\'er--Wold theorem, it suffices to prove
that for any $\bm{a}=(a_{1},\cdots,a_{d})^{\top}\in\mathbb{R}^{d}$,
$\bm{a}^{\top}\bm{Z}_{:,l}$ converges to $\bm{a}^{\top}\bm{g}_{l}$
in distribution. Towards this, we apply the Berry-Esseen theorem \cite[Theorem 1.1]{bentkus2005lyapunov}
(cf.~Appendix~\ref{subsec:Berry-Esseen-theorem}) again and upper
bound $\rho$ defined in (\ref{def:Berry-Esseen-rho}). Without loss
of generality, we assume $\|\bm{a}\|_{2}=1$. We can compute
\begin{align*}
\sum_{1\leq i,j,k\leq d}\mathbb{E}\Big[\big|a_{k}p^{-1}E_{i,j,k}\chi_{i,j,k}V_{(i,j),l}^{\star}\big|^{3}\Big] & \leq\frac{1}{p^{3}}\left\Vert \bm{a}\right\Vert _{\infty}\left\Vert \bm{V}_{:,l}^{\star}\right\Vert _{\infty}\sum_{1\leq i,j,k\leq d}a_{k}^{2}\,\mathbb{E}\big[\left|E_{i,j,k}\right|^{3}\chi_{i,j,k}\big]V_{(i,j),l}^{\star2}\\
 & \overset{(\mathrm{i})}{\lesssim}\frac{\sigma_{\max}^{3}}{p^{2}}\left\Vert \bm{a}\right\Vert _{\infty}\left\Vert \bm{a}\right\Vert _{2}^{2}\left\Vert \bm{V}_{:,l}^{\star}\right\Vert _{\infty}\left\Vert \bm{V}_{:,l}^{\star}\right\Vert _{2}^{2}\overset{(\mathrm{ii})}{\lesssim}\frac{\sigma_{\max}^{3}}{p^{2}}\cdot\frac{\mu\sqrt{r}}{d}\frac{1}{\lambda_{\min}^{\star2/3}}\cdot\frac{1}{\lambda_{\min}^{\star4/3}},
\end{align*}
where we use the property of sub-gaussian random variables in (i),
and (ii) follows from (\ref{eq:V-true-col-norm}) and $\left\Vert \bm{a}\right\Vert _{\infty}\leq\left\Vert \bm{a}\right\Vert _{2}=1$
. Moreover, from Lemma~\ref{lemma:u-l2-loss-cov-matrix}, it is easy
to see that
\[
\mathsf{Var}\big(\bm{a}^{\top}\bm{Z}_{:,l}\big)=\bm{a}^{\top}\bm{S}_{l}^{\star}\bm{a}\geq\lambda_{\min}(\bm{S}_{l}^{\star})\left\Vert \bm{a}\right\Vert _{2}^{2}\gtrsim\frac{\sigma_{\min}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}\gtrsim\frac{\sigma_{\min}^{2}}{p\lambda_{\max}^{\star4/3}}.
\]
One can then bound $\rho$
\[
\rho=\big(\mathsf{Var}(\bm{a}^{\top}\bm{Z}_{:,l})\big)^{-3/2}\sum_{1\leq i,j,k\leq d}\mathbb{E}\Big[\big|a_{k}p^{-1}E_{i,j,k}\chi_{i,j,k}V_{(i,j),l}^{\star}\big|^{3}\Big]\lesssim\frac{p^{3/2}\lambda_{\max}^{\star2}}{\sigma_{\min}^{3}}\cdot\frac{\sigma_{\max}^{3}}{\lambda_{\min}^{\star2}}\frac{\mu\sqrt{r}}{dp^{2}}\lesssim\frac{\mu\sqrt{r}}{d\sqrt{p}}=o\left(1\right)
\]
where we use the condition that $\sigma_{\max}/\sigma_{\min},\kappa\asymp1$
and $p\gg\mu^{2}rd^{-3/2}$. Therefore, we justify the claimed distributional
convergence of $\bm{a}^{\top}\bm{Z}_{:,l}$, which further implies
the convergence of $\bm{Z}_{:,l}$ by the Cram\'er--Wold theorem.

Given that $\bm{Z}_{:,l}$ converges to $\bm{g}_{l}$ in distribution,
we now apply the Gaussian concentration inequality \cite[Proposition 1]{hsu2012tail}
to demonstrate the squared $\ell_{2}$ norm of $\bm{g}_{l}$ is tightly
concentrated around its mean with high probability. By Lemma~\ref{lemma:u-l2-loss-cov-matrix},
we can use the Gaussian concentration inequality \cite[Proposition 1]{hsu2012tail}
to find that with probability at least $1-O\left(d^{-11}\right)$,
\begin{align*}
\left\Vert \bm{g}_{l}\right\Vert _{2}^{2}-\mathsf{tr}(\bm{S}_{l}^{\star}) & \lesssim\left\Vert \bm{S}_{l}^{\star}\right\Vert _{\mathrm{F}}\sqrt{\log d}+\left\Vert \bm{S}_{l}^{\star}\right\Vert \log d\lesssim\frac{\sigma_{\max}^{2}(\sqrt{d\log d}+\log d)}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}=o\left(1\right)\frac{\sigma_{\max}^{2}d}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}},
\end{align*}
and consequently,
\[
\left\Vert \bm{g}_{l}\right\Vert _{2}^{2}\leq\frac{2\left(1+o\left(1\right)\right)\sigma_{\max}^{2}d}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.
\]
Moreover, we know from the continuous mapping theorem that $\left\Vert \bm{Z}_{:,l}\right\Vert _{2}^{2}$
converges to $\left\Vert \bm{g}_{l}\right\Vert _{2}^{2}$ in distribution
because $\|\cdot\|_{2}^{2}$ is a continuous function. Therefore,
we find that with probability at least $1-o\left(1\right)$,
\begin{equation}
\left\Vert \bm{Z}_{:,l}\right\Vert _{2}^{2}\leq\frac{2\left(1+o\left(1\right)\right)\sigma_{\max}^{2}d}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.\label{eq:Z-col-2norm-UB}
\end{equation}

It remains to upper bound $\left\Vert \bm{W}_{:,l}\right\Vert _{2}$,
which is easily accomplished with the help of (\ref{eq:W-2inf-norm-UB}).
Indeed, it is straightforward to find that with probability at least
$1-O\left(d^{-11}\right)$,
\[
\left\Vert \bm{W}_{:,l}\right\Vert _{2}^{2}\leq\sum_{1\leq k\leq d}\left\Vert \bm{W}_{k,:}\right\Vert _{2,\infty}^{2}\leq d\cdot\frac{o\left(1\right)\sigma_{\max}^{2}}{\lambda_{\min}^{\star4/3}p}=\frac{o\left(1\right)\sigma_{\max}^{2}d}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}},
\]
where we use the assumption that $\kappa\asymp1$ in the last step.
Taken collectively with (\ref{eq:Z-col-2norm-UB}) finishes the proof.

\subsubsection{Proof of Lemma \ref{lemma:u-l2-loss-cov-matrix}}

To begin with, let us consider the trace of $\bm{S}_{l}^{\star}$.
From (\ref{eq:cov-u-diag-entry}) and (\ref{eq:V-true-col-norm}),
it is straightforward to calculate
\begin{align*}
\mathsf{tr}(\bm{S}_{l}^{\star}) & =\sum_{1\leq i\leq d}\left(\bm{S}_{l}^{\star}\right)_{i,i}\leq2\sum_{1\leq i,j,k\leq d}p^{-1}\sigma_{i,j,k}^{2}V_{(j,k),l}^{\star2}\\
 & =\frac{2\,\sigma_{\max}^{2}d}{p}\left\Vert \bm{V}_{:,l}^{\star}\right\Vert _{2}^{2}=\frac{2\left(1+o\left(1\right)\right)\sigma_{\max}^{2}d}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.
\end{align*}

As for the Frobenius norm of $\bm{S}_{l}^{\star}$, we note that it
is an immediate consequence of the claim for the spectrum of $\bm{S}_{l}^{\star}$.
Indeed, since $\bm{S}_{l}^{\star}$ is a positive semidefinite matrix,
we know that 
\[
\left\Vert \bm{S}_{l}^{\star}\right\Vert _{\mathrm{F}}^{2}=\mathsf{tr}(\bm{S}_{l}^{\star2})=\sum_{1\leq i\leq d}\lambda_{i}(\bm{S}_{l}^{\star2})=\sum_{1\leq i\leq d}\lambda_{i}^{2}(\bm{S}_{l}^{\star})\leq d\cdot\lambda_{\max}^{2}(\bm{S}_{l}^{\star})\lesssim\frac{\sigma_{\max}^{4}d}{p^{2}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{8}}
\]
as claimed.

Hence, the remainder of the proof amounts to controlling the eigenvalues
of $\bm{S}_{l}^{\star}$. Let us decompose $\bm{S}_{l}^{\star}=:2\widehat{\bm{S}}_{l}^{\star}-\breve{\bm{S}}_{l}^{\star}\in\mathbb{R}^{d\times d}$,
where the entries of $\widehat{\bm{S}}_{l}^{\star}$ and $\breve{\bm{S}}_{l}^{\star}$
are given by
\[
\big(\widehat{\bm{S}}_{l}^{\star}\big)_{i,j}=\begin{cases}
\sum_{1\leq k_{1},k_{2}\leq d}p^{-1}\sigma_{i,k_{1},k_{2}}^{2}V_{(k_{1},k_{2}),l}^{\star2}, & \text{if}\quad i=j,\\
2\sum_{1\leq k\leq d}p^{-1}\sigma_{i,j,k}^{2}V_{(i,k),l}^{\star}V_{(j,k),l}^{\star}, & \text{if}\quad i\neq j,
\end{cases}
\]
and
\[
\big(\breve{\bm{S}}_{l}^{\star}\big)_{i,j}=\begin{cases}
0, & \text{if}\quad i=j,\\
\big(4-2\sqrt{2}\big)p^{-1}\sigma_{i,i,j}^{2}V_{(i,i),l}^{\star}V_{(i,j),l}^{\star}+\big(4-2\sqrt{2}\big)p^{-1}\sigma_{i,j,j}^{2}V_{(j,j),l}^{\star}V_{(i,j),l}^{\star}, & \text{if}\quad i\neq j.
\end{cases}
\]
Our proof strategy is to show that the spectrum of $\bm{S}_{l}^{\star}$
is mainly determined by $\widehat{\bm{S}}_{l}^{\star}$ (since $\|\breve{\bm{S}}_{l}^{\star}\|$
is a negligible term). One can then invoke Weyl's inequality to establish
the conclusion.

Now we start the analysis. Note that by the symmetric sampling pattern,
one equivalently express $\sigma_{i,j,k}^{2}=s_{i}^{2}s_{j}^{2}s_{k}^{2}$
for each $1\leq i,j,k\leq d$ with $\max_{1\leq i\leq d}s_{i}\leq\sigma_{\max}^{1/3}$.
We then can decompose
\[
\widehat{\bm{S}}_{l}^{\star}=2\bm{A}\bm{A}^{\top}+\mathcal{P}_{\mathsf{diag}}\big(\widehat{\bm{S}}_{l}^{\star}-2\bm{A}\bm{A}^{\top}\big),
\]
where $\mathcal{P}_{\mathsf{diag}}(\bm{Z})$ extracts out the diagonal
entries of a matrix $\bm{Z}$, and $\bm{A}\in\mathbb{R}^{d\times d}$
is a matrix with entries $A_{i,k}=\sqrt{1/p}\,s_{i}^{2}s_{k}V_{(i,k),l}^{\star}$.
Let us first control the spectral norm of $\mathcal{P}_{\mathsf{diag}}\big(\widehat{\bm{S}}_{l}^{\star}-2\bm{A}\bm{A}^{\top}\big)$.
From (\ref{eq:V-true-col-norm}), it is easy to see that for all $1\leq i\leq d$,
\begin{align}
\left|\big(\widehat{\bm{S}}_{l}^{\star}-2\bm{A}\bm{A}^{\top}\big)_{i,i}\right| & \leq\frac{\sigma_{\min}^{2}}{p}\left\Vert \bm{V}_{:,l}^{\star}\right\Vert _{2}^{2}+\frac{2\sigma_{\max}^{2}}{p}\sum_{1\leq k\leq d}V_{(i,k),l}^{\star2}\nonumber \\
 & \leq\frac{\left(1+o\left(1\right)\right)\sigma_{\min}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}+\frac{2\sigma_{\max}^{2}}{p}\frac{\mu r}{d}\frac{1}{\lambda_{\min}^{\star4/3}}=\frac{\left(1+o\left(1\right)\right)\sigma_{\max}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}},\label{eq:cov-hat-diag-UB}\\
\big(\widehat{\bm{S}}_{l}^{\star}-2\bm{A}\bm{A}^{\top}\big)_{i,i} & \geq\frac{\sigma_{\min}^{2}}{p}\left\Vert \bm{V}_{:,l}^{\star}\right\Vert _{2}^{2}-\frac{2\sigma_{\max}^{2}}{p}\sum_{1\leq k\leq d}V_{(i,k),l}^{\star2}=\frac{\left(1-o\left(1\right)\right)\sigma_{\min}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}},\label{eq:cov-hat-diag-LB}
\end{align}
where we have used the condition that $\sigma_{\min}/\sigma_{\max}\asymp1$,
$\kappa\asymp1$, and $r=o\left(d/\mu\right)$. It then suffices to
focus on the spectrum of $\bm{A}\bm{A}^{\top}$, whose entries are
given by
\[
\left(\bm{A}\bm{A}^{\top}\right)_{i,j}=p^{-1}s_{i}^{2}s_{j}^{2}\sum_{1\leq k\leq d}s_{k}^{2}V_{(i,k),l}^{\star}V_{(j,k),l}^{\star},\qquad1\leq i,j\leq d.
\]
Recalling the definitions $\bm{V}^{\star}:=\widetilde{\bm{U}}^{\star}(\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}$
and $u_{l,i}^{\star}:=\left(\bm{u}_{l}^{\star}\right)_{i}$ for each
$1\leq l\leq r,1\leq i\leq d$, we can decompose
\begin{align}
V_{(i,k),l}^{\star} & =\widetilde{\bm{U}}_{(i,k),:}^{\star}(\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})_{:,l}^{-1}=\widetilde{\bm{U}}_{(i,k),:}^{\star}\bm{\Lambda}_{:,l}^{\star-4/3}+\widetilde{\bm{U}}_{(i,k),:}^{\star}\big((\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}-\bm{\Lambda}^{\star-4/3}\big)_{:,l}\nonumber \\
 & =\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{-4}\widetilde{U}_{(i,k),l}^{\star}+\widetilde{\bm{U}}_{(i,k),:}^{\star}\big((\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}-\bm{\Lambda}^{\star-4/3}\big)_{:,l}\nonumber \\
 & =\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{-4}u_{l,i}^{\star}u_{l,k}^{\star}+\underbrace{\widetilde{\bm{U}}_{(i,k),:}^{\star}\big((\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}-\bm{\Lambda}^{\star-4/3}\big)_{:,l}}_{=:\,\delta_{i,k}}.\label{eq:V-ikl-decomp}
\end{align}
We will show shortly that $V_{(i,k),l}^{\star}$ is extremely close
to $\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{-4}u_{l,i}^{\star}u_{l,k}^{\star}$.
Then we obtain that for each $1\leq i,j\leq d$,
\begin{align*}
p\left(\bm{A}\bm{A}^{\top}\right)_{i,j} & =\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{-8}\Big(\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star2}\Big)\left(s_{i}^{2}u_{l,i}^{\star}\right)\left(s_{j}^{2}u_{l,j}^{\star}\right)+\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{-4}\left(s_{i}^{2}u_{l,i}^{\star}\right)\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star}\left(s_{j}^{2}\delta_{j,k}\right)\\
 & \quad+\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{-4}\left(s_{j}^{2}u_{l,j}^{\star}\right)\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star}\left(s_{i}^{2}\delta_{i,k}\right)+\underbrace{\sum_{1\leq k\leq d}s_{k}^{2}\left(s_{i}^{2}\delta_{i,k}\right)\left(s_{j}^{2}\delta_{j,k}\right)}_{=:\,\Upsilon_{i,j}},
\end{align*}
or equivalently,
\[
p\bm{A}\bm{A}^{\top}=\bm{a}\bm{a}^{\top}\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star2}+\bm{a}\bm{b}^{\top}+\bm{b}\bm{a}^{\top}+\bm{\Upsilon},
\]
where $\bm{a},\bm{b}\in\mathbb{R}^{d}$ with entries $a_{i}=s_{i}^{2}u_{l,i}^{\star}/\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}$,
$b_{i}=\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star}\left(s_{i}^{2}\delta_{i,k}\right)$
and $\bm{\Upsilon}=[\Upsilon_{i,j}]_{1\leq i,j\leq d}\in\mathbb{R}^{d\times d}$.
It is straightforward to see that $\bm{a}\bm{a}^{\top}\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star2}$
is a rank-$1$ matrix with the non-zero eigenvalue 
\begin{align}
 & \frac{\sigma_{\min}^{2}}{\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}\leq\lambda_{\max}\Big(\bm{a}\bm{a}^{\top}\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star2}\Big)\leq\frac{\sigma_{\max}^{2}}{\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.\label{eq:cov-hat-rank1-eigval}
\end{align}
In addition, the remaining three terms are all small with respect
to the spectral norm. Indeed, recalling the decomposition in (\ref{eq:V-ikl-decomp}),
we can use (\ref{eq:U-true-tilde-Gram-Ind-diff}), $\kappa\asymp1$
and the condition $r=o(\sqrt{d/\mu})$ to show $\delta_{i,k}$ is
sufficiently small, i.e.
\begin{align}
\sum_{1\leq i,k\leq d}\delta_{i,k}^{2} & \leq\big\|\widetilde{\bm{U}}^{\star}\big\|_{\mathrm{F}}^{2}\big\|(\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}-\bm{\Lambda}^{\star-4/3}\big\|^{2}\lesssim r\lambda_{\max}^{\star4/3}\cdot\left(\frac{1}{\lambda_{\min}^{\star8/3}}\frac{\mu r}{d}\lambda_{\max}^{\star4/3}\right)^{2}=\frac{o\left(1\right)}{\lambda_{\min}^{\star4/3}}.\label{eq:proof-estimation-delta-square-sum}
\end{align}
It then follows from the Cauchy-Schwartz inequality that
\begin{align*}
\left\Vert \bm{b}\right\Vert _{2}^{2} & =\sum_{1\leq i\leq d}\Big|\sum_{1\leq k\leq d}s_{k}^{2}u_{l,k}^{\star}\left(s_{i}^{2}\delta_{i,k}\right)\Big|^{2}\leq\max_{1\leq i\leq d}s_{i}^{8}\sum_{1\leq k\leq d}u_{l,k}^{\star2}\sum_{1\leq i,k\leq d}\delta_{i,k}^{2}\lesssim\frac{\sigma_{\max}^{8/3}}{\lambda_{\min}^{\star4/3}}\frac{\mu^{2}r^{3}}{d^{2}}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{2};\\
\left\Vert \bm{\Upsilon}\right\Vert _{\mathrm{F}}^{2} & =\sum_{1\leq i,j\leq d}\Big|\sum_{1\leq k\leq d}s_{k}^{2}\left(s_{i}^{2}\delta_{i,k}\right)\left(s_{j}^{2}\delta_{j,k}\right)\Big|^{2}\leq\max_{1\leq i\leq d}s_{i}^{12}\,\Big|\sum_{1\leq i,k\leq d}\delta_{i,k}^{2}\Big|^{2}\lesssim\left(\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star4/3}}\frac{\mu^{2}r^{3}}{d^{2}}\right)^{2}.
\end{align*}
This combined with the condition $r=o\big(\sqrt{d/\mu}\big)$ and
$\kappa\asymp1$ reveals that
\begin{align*}
\left\Vert \bm{a}\bm{b}^{\top}+\bm{b}\bm{a}^{\top}+\bm{\Upsilon}\right\Vert  & \leq2\left\Vert \bm{a}\right\Vert _{2}\left\Vert \bm{b}\right\Vert _{2}+\left\Vert \bm{\Upsilon}\right\Vert _{\mathrm{F}}\lesssim\frac{\sigma_{\max}^{2/3}}{\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{3}}\frac{\sigma_{\max}^{4/3}}{\lambda_{\min}^{\star2/3}}\frac{\mu r^{3/2}}{d}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}+\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star4/3}}\frac{\mu^{2}r^{3}}{d^{2}}=\frac{o\left(1\right)\sigma_{\max}^{2}}{\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.
\end{align*}
Taken collectively with (\ref{eq:cov-hat-diag-UB}), (\ref{eq:cov-hat-diag-LB})
and (\ref{eq:cov-hat-rank1-eigval}), we conclude that
\[
\lambda_{\max}(\widehat{\bm{S}}_{l}^{\star})\lesssim\frac{\sigma_{\max}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}},\qquad\lambda_{\min}(\widehat{\bm{S}}_{l}^{\star})\gtrsim\frac{\sigma_{\min}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}.
\]
Applying a similar argument, one can easily show that 
\begin{align*}
\|\breve{\bm{S}}_{l}^{\star}\| & \lesssim\frac{\sigma_{\max}^{2}}{p}\sum_{1\leq k\leq d}V_{(k,k),l}^{\star2}\lesssim\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star4/3}p}\frac{\mu r}{d}=\frac{o\left(1\right)\sigma_{\min}^{2}}{p\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{4}}=o\left(1\right)\lambda_{\min}(\widehat{\bm{S}}_{l}^{\star}).
\end{align*}
Therefore, the advertised bound of the eigenvalues of $\bm{S}_{l}^{\star}=2\widehat{\bm{S}}_{l}^{\star}-\breve{\bm{S}}_{l}^{\star}$
immediately follows from Weyl's inequality.

\subsection{$\ell_{2}$ risk for tensor estimation}

\label{subsec:proof-l2-loss-Tensor}

To begin with, we recall the notation $\bm{\Delta}_{l}:=\bm{u}_{l}-\bm{u}_{l}^{\star},1\leq l\leq r$,
allowing us to expand
\begin{align*}
\bm{T}-\bm{T}^{\star} & =\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2}+\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star}+\sum_{1\leq l\leq r}\bm{u}_{l}^{\star\otimes2}\otimes\bm{\Delta}_{l}\\
 & \quad+\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2}+\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}+\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes2}\otimes\bm{u}_{l}^{\star}+\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes3}.
\end{align*}
By symmetry, straightforward calculation yields
\begin{align*}
\left\Vert \bm{T}-\bm{T}^{\star}\right\Vert _{\mathrm{F}}^{2} & =3\underbrace{\Big\|\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2}\Big\|_{\mathrm{F}}^{2}}_{=:\,\beta_{1}}+3\underbrace{\Big\|\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2}\big\|_{\mathrm{F}}^{2}}_{=:\,\beta_{2}}+\underbrace{\Big\|\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes3}\Big\|_{\mathrm{F}}^{2}}_{=:\,\beta_{4}}\\
 & \quad+6\underbrace{\Big\langle\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2},\sum_{1\leq l\leq r}\bm{u}_{l}^{\star\otimes2}\otimes\bm{\Delta}_{l}\Big\rangle}_{=:\,\beta_{4}}+\,\beta_{5},
\end{align*}
where
\begin{align*}
\beta_{5} & :=6\,\Big\langle\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2},\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes2}\otimes\bm{u}_{l}^{\star}\Big\rangle+6\,\Big\langle\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2},\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes3}\Big\rangle\\
 & \quad+6\,\Big\langle\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2},\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2}\Big\rangle+6\,\Big\langle\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2},\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes3}\Big\rangle\\
 & \quad+12\,\Big\langle\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2},\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes2}\otimes\bm{u}_{l}^{\star}\Big\rangle.
\end{align*}
In what follows, we shall control the $\beta_{i}$'s separately. In
particular, we want to show that the $\ell_{2}$ loss of interest
is mainly controlled by $\beta_{1}$, with the remaining four terms
being negligible with high probability.
\begin{enumerate}
\item We start with $\beta_{1}$. Recalling (\ref{eq:U-loss-decomp}), (\ref{def:W1-W4})
and (\ref{def:W}) that $\bm{\Delta}:=\bm{U}-\bm{U}^{\star}=\bm{Z}+\bm{W}$
as well as the notation $\widetilde{\bm{U}}^{\star}:=\big[\bm{u}_{l}^{\star\otimes2}\big]_{1\leq l\leq r}\in\mathbb{R}^{d^{2}\times r}$,
we can easily see that
\begin{align*}
\beta_{1} & =\big\|\bm{\Delta}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}^{2}=\big\|\bm{Z}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}^{2}+\big\|\bm{W}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}^{2}+2\,\big\langle\bm{Z}\widetilde{\bm{U}}^{\star\top},\bm{W}\widetilde{\bm{U}}^{\star\top}\big\rangle.
\end{align*}
One can apply an analogous argument as in Appendix~\ref{subsec:proof-l2-loss-Tensor-factors}
to show that the distribution of $\bm{Z}\widetilde{\bm{U}}^{\star\top}$
converges to a multivariate normal distribution, whose Euclidean norm
concentrates around its expectation with high probability. We omit
the detailed proof for conciseness. One can verify that with probability
exceeding $1-o\left(1\right)$,
\[
\|\bm{Z}\widetilde{\bm{U}}^{\star\top}\|_{\mathrm{F}}^{2}=\frac{\left(2+o\left(1\right)\right)\sigma_{\max}^{2}d}{p}\big\|\widetilde{\bm{U}}^{\star}(\widetilde{\bm{U}}^{\star\top}\widetilde{\bm{U}}^{\star})^{-1}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}^{2}=\frac{\left(2+o\left(1\right)\right)\sigma_{\max}^{2}rd}{p}.
\]
In addition, we know from (\ref{eq:U-true-tilde-spectrum}) and (\ref{eq:W-2inf-norm-UB})
that
\[
\big\|\bm{W}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}^{2}\leq\big\|\widetilde{\bm{U}}^{\star}\big\|^{2}\big\|\bm{W}\big\|_{\mathrm{F}}^{2}\lesssim\lambda_{\max}^{\star4/3}\cdot d\left\Vert \bm{W}\right\Vert _{2,\infty}^{2}=o\left(1\right)\frac{\sigma_{\max}^{2}d}{p},
\]
which further implies that
\[
\big|\big\langle\bm{Z}\widetilde{\bm{U}}^{\star\top},\bm{W}\widetilde{\bm{U}}^{\star\top}\big\rangle\big|\leq\big\|\bm{Z}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}\big\|\bm{W}\widetilde{\bm{U}}^{\star\top}\big\|_{\mathrm{F}}=o\left(1\right)\frac{\sigma_{\max}^{2}rd}{p}.
\]
As a result, we find that
\begin{equation}
\Big\|\sum_{1\leq l\leq r}\bm{\Delta}_{l}\otimes\bm{u}_{l}^{\star\otimes2}\Big\|_{\mathrm{F}}^{2}=\frac{\left(2+o\left(1\right)\right)\sigma_{\max}^{2}rd}{p}.\label{eq:T-l2-loss-beta1}
\end{equation}
\item Next, let us look at $\beta_{2}$. We denote by $\widetilde{\bm{\Delta}}:=\big[\bm{\Delta}_{l}^{\otimes2}\big]_{1\leq l\leq r}\in\mathbb{R}^{d^{2}\times r}$,
whose Frobenius norm can be bounded by
\begin{equation}
\big\|\widetilde{\bm{\Delta}}\big\|_{\mathrm{F}}^{2}=\sum_{1\leq l\leq r}\big\|\bm{\Delta}_{l}^{\otimes2}\big\|_{2}^{2}=\sum_{1\leq l\leq r}\big\|\bm{\Delta}_{l}\big\|_{2}^{4}\leq\max_{1\leq l\leq r}\big\|\bm{\Delta}_{l}\big\|_{2}^{2}\left\Vert \bm{\Delta}\right\Vert _{\mathrm{F}}^{2}\leq\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{2,\infty}^{2}\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{\mathrm{F}}^{2}.\label{eq:delta-tilde-fro-UB}
\end{equation}
Consequently, we use (\ref{eq:U-loss-fro}) and (\ref{eq:U-loss-2inf})
to obtain
\begin{align}
\beta_{2} & =\big\|\bm{U}^{\star}\widetilde{\bm{\Delta}}^{\top}\big\|_{\mathrm{F}}^{2}\leq\left\Vert \bm{U}^{\star}\right\Vert ^{2}\big\|\widetilde{\bm{\Delta}}\big\|_{\mathrm{F}}^{2}\lesssim\left\Vert \bm{U}^{\star}\right\Vert ^{2}\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{2,\infty}^{2}\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{\mathrm{F}}^{2}\nonumber \\
 & \lesssim\lambda_{\max}^{\star2/3}\cdot\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star2}}\frac{\mu r\log d}{p}\lambda_{\max}^{\star2/3}\cdot\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star2}}\frac{rd\log d}{p}\lambda_{\max}^{\star2/3}=o\left(1\right)\frac{\sigma_{\max}^{2}rd}{p},\label{eq:T-l2-loss-beta2}
\end{align}
where the last step holds as long $\sigma_{\max}/\lambda_{\min}^{\star}\ll\sqrt{p/(\mu r\log^{2}d)}$
and $\kappa\asymp1$.
\item In a similar way, we can use (\ref{eq:U-T-loss-UB}) and (\ref{eq:delta-tilde-fro-UB})
to upper bound $\beta_{3}$ as follows
\begin{align}
\beta_{3} & =\big\|\bm{\Delta}\widetilde{\bm{\Delta}}^{\top}\big\|_{\mathrm{F}}^{2}\leq\|\bm{\Delta}\|^{2}\|\widetilde{\bm{\Delta}}\|_{\mathrm{F}}^{2}\lesssim\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert ^{2}\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{2,\infty}^{2}\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{\mathrm{F}}^{2}\nonumber \\
 & \lesssim\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star2}}\frac{rd\log d}{p}\lambda_{\max}^{\star2/3}\cdot\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star2}}\frac{\mu r\log d}{p}\lambda_{\max}^{\star2/3}\cdot\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star2}}\frac{rd\log d}{p}\lambda_{\max}^{\star2/3}=o\left(1\right)\frac{\sigma_{\max}^{2}rd}{p},\label{eq:T-l2-loss-beta3}
\end{align}
where the last step follows from the conditions that $\sigma_{\max}/\lambda_{\min}^{\star}\ll\sqrt{p/(\mu rd\log^{2}d)}$
and $\kappa\asymp1$.
\item As for $\beta_{4}$, one can apply the triangle inequality and Cauchy-Schwartz
to upper bound
\begin{align*}
\left|\beta_{4}\right| & =\Big|\sum_{1\leq l\leq r}\left\langle \bm{\Delta}_{l},\bm{u}_{l}^{\star}\right\rangle ^{2}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{2}+\sum_{1\leq l\neq s\leq r}\left\langle \bm{\Delta}_{l},\bm{u}_{s}^{\star}\right\rangle \left\langle \bm{u}_{l}^{\star},\bm{\Delta}_{s}\right\rangle \left\langle \bm{u}_{l}^{\star},\bm{u}_{s}^{\star}\right\rangle \Big|\\
 & \lesssim\sum_{1\leq l\leq r}\left\langle \bm{\Delta}_{l},\bm{u}_{l}^{\star}\right\rangle ^{2}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}^{2}+\max_{1\leq l\neq s\leq r}\left|\left\langle \bm{u}_{l}^{\star},\bm{u}_{s}^{\star}\right\rangle \right|\Big(\sum_{1\leq l\leq r}\left\Vert \bm{\Delta}_{l}\right\Vert _{2}\left\Vert \bm{u}_{l}^{\star}\right\Vert _{2}\Big)^{2}\\
 & \leq\max_{1\leq l\leq r}\left\langle \bm{\Delta}_{l},\bm{u}_{l}^{\star}\right\rangle ^{2}\left\Vert \bm{U}^{\star}\right\Vert _{\mathrm{F}}^{2}+\max_{1\leq l\neq s\leq r}\left|\left\langle \bm{u}_{l}^{\star},\bm{u}_{s}^{\star}\right\rangle \right|\left\Vert \bm{U}-\bm{U}^{\star}\right\Vert _{\mathrm{F}}^{2}\left\Vert \bm{U}^{\star}\right\Vert _{\mathrm{F}}^{2}.
\end{align*}
We then use the incoherence assumption~(\ref{assumption:u-inner-prod}),
Lemma~\ref{lemma:u-loss-u-true-inner-product-UB} in Appendix~\ref{subsec:U-loss-dist-W1},
(\ref{eq:U-true-norm}) and (\ref{eq:U-loss-fro}) to find that
\begin{equation}
\left|\beta_{4}\right|=o\left(1\right)\frac{\sigma^{2}}{\lambda_{\min}^{\star2/3}}\frac{d}{p}\cdot r\lambda_{\max}^{\star2/3}+\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{\star2/3}\cdot\frac{\sigma_{\max}^{2}}{\lambda_{\min}^{\star2}}\frac{rd\log d}{p}\lambda_{\max}^{\star2/3}\cdot r\lambda_{\max}^{\star2/3}=o\left(1\right)\frac{\sigma_{\max}^{2}rd}{p},\label{eq:T-l2-loss-beta4}
\end{equation}
where we use the assumption that $r=o\,\big(\sqrt{d/(r\log^{2}d)}\big)$
and $\kappa\asymp1$.
\item It remains to bound $\beta_{5}$. Given the Cauchy-Schwartz inequality
$|\langle\bm{A},\bm{B}\rangle|\leq\left\Vert \bm{A}\right\Vert _{\mathrm{F}}\left\Vert \bm{B}\right\Vert _{\mathrm{F}}$,
it immediately follows from (\ref{eq:T-l2-loss-beta1}), (\ref{eq:T-l2-loss-beta2})
and (\ref{eq:T-l2-loss-beta3}) that
\begin{align*}
\left|\beta_{5}\right| & \lesssim\Big\|\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2}\Big\|_{\mathrm{F}}^{2}+\Big(\Big\|\sum_{1\leq l\leq r}\bm{u}_{l}^{\star\otimes2}\otimes\bm{\Delta}_{l}\Big\|_{\mathrm{F}}+\Big\|\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2}\Big\|_{\mathrm{F}}\Big)\Big\|\sum_{1\leq l\leq r}\bm{\Delta}_{l}^{\otimes3}\Big\|_{\mathrm{F}}\\
 & \quad+\Big\|\sum_{1\leq l\leq r}\bm{u}_{l}^{\star}\otimes\bm{\Delta}_{l}^{\otimes2}\Big\|_{\mathrm{F}}\Big\|\sum_{1\leq l\leq r}\bm{u}_{l}^{\star\otimes2}\otimes\bm{\Delta}_{l}\Big\|_{\mathrm{F}}=o\left(1\right)\frac{\sigma_{\max}^{2}rd}{p}.
\end{align*}
This taken collectively with (\ref{eq:T-l2-loss-beta4}) finishes
the proof.
\end{enumerate}
{"config": "arxiv", "file": "2006.08580/proof-estimation.tex"}