(285a) $\displaystyle\|\bm{V}-\bm{V}^{\star}\bm{S}^{(2)}\|_{\mathrm{F}}$
$\displaystyle\leq\delta\left\|\bm{V}^{\star}\right\|_{\mathrm{F}}\quad\text{and}\quad\left\|\bm{V}-\bm{V}^{\star}\bm{S}^{(2)}\right\|_{2,\infty}\leq\delta\left\|\bm{V}^{\star}\right\|_{2,\infty};$
(285b) $\displaystyle\|\bm{W}-\bm{W}^{\star}\bm{S}^{(3)}\|_{\mathrm{F}}$
$\displaystyle\leq\delta\left\|\bm{V}^{\star}\right\|_{\mathrm{F}}\quad\text{and}\quad\left\|\bm{W}-\bm{W}^{\star}\bm{S}^{(3)}\right\|_{2,\infty}\leq\delta\left\|\bm{W}^{\star}\right\|_{2,\infty}.$
(285c)

Here, $\delta\leq c_{3}/(\mu^{3/2}r)$ for some sufficiently small constant
$c_{3}>0$, and $\bm{S}^{(1)}$, $\bm{S}^{(2)}$ and $\bm{S}^{(3)}$ are some
diagonal matrices in $\mathbb{R}^{r\times r}$ such that for each $1\leq i\leq
r$, two of $S_{i,i}^{(1)}$, $S_{i,i}^{(2)}$ and $S_{i,i}^{(3)}$ equal to $-1$
with the remaining one equal to $1$.

###### Proof.

See Appendix E.5. ∎

In a nutshell, Lemma E.2 confirms local strong convexity and smoothness of the
noiseless regularized loss $g_{\mathsf{clean}}(\bm{U},\bm{V},\bm{W})$,
provided that (282) holds and that the matrices $\bm{U}$, $\bm{V}$ and
$\bm{W}$ are sufficiently close to the ground truth in every single row. This
is similar to the property of the symmetric counterpart
$f_{\mathsf{clean}}(\bm{U})$ (cf. Lemma 5.1 in Appendix 5.1), except that we
need to deal with asymmetric tensor factors as well as additional
regularization terms. In particular, when $d_{1}\asymp d_{2}\asymp d_{3}\asymp
d$ and $\mu,r\asymp 1$, Condition (282) reduces to $p\gg d^{-3/2}\log^{3}d$
and $r\ll\sqrt{d}$, which resembles (42) in Lemma 5.1 derived for the
symmetric case.

Having established the preceding local geometric properties of
$g_{\mathsf{clean}}$, one can then argue similarly as in Lemmas 5.3 and 5.6 in
Appendix 5.1 to prove that gradient descent converges linearly, as long as it
is provided with an initial estimate satisfying the condition (285). Here, we
emphasize that the regularization term (277), which essentially balances the
sizes of the three tensor factors, is crucial for the local strong convexity
and smoothness of $g_{\mathsf{clean}}$ to hold.

##### 2\. Guaranteeing a reasonably good initialization.

Another crucial ingredient lies in guaranteeing an initial estimate with
sufficiently good accuracy. Recall that our initialization scheme consists of
two stages: (1) subspace estimation, and (2) retrieval of individual tensor
factors.

  * •

The subspace estimation part remains largely unchanged: we shall unfold the
observed tensor along the $1$-st mode to estimate the subspace spanned by
tensor factors $\\{\bm{u}_{i}^{\star}\\}_{i=1}^{r}$, and the $\ell_{2,\infty}$
subspace estimation accuracy can be established by invoking the main theorems
of our companion paper [CLC+20].

  * •

Regarding the retrieval of individual tensor factors, the key observation is
that: the random vector $\bm{g}^{\tau}$ we generate satisfies

$\displaystyle\bm{T}^{\star}\times_{1}\mathcal{P}_{\bm{U}^{\star}}(\bm{g}^{\tau})=\sum_{i=1}^{r}\lambda_{i}^{\star}\langle\overline{\bm{u}}_{i}^{\star},\mathcal{P}_{\bm{U}^{\star}}(\bm{g}^{\tau})\rangle\overline{\bm{v}}_{i}^{\star}\overline{\bm{w}}_{i}^{\star\top}=\sum_{i=1}^{r}\lambda_{i}^{\star}\langle\overline{\bm{u}}_{i}^{\star},\bm{g}^{\tau}\rangle\overline{\bm{v}}_{i}^{\star}\overline{\bm{w}}_{i}^{\star\top},$

where $\mathcal{P}_{\bm{U}^{\star}}$ is the projection onto the subspace
spanned by $\\{\bm{u}_{i}^{\star}\\}_{i=1}^{r}$, and

$\displaystyle\overline{\bm{u}}_{i}^{\star}=\frac{1}{\|\bm{u}_{i}^{\star}\|_{2}}\bm{u}_{i}^{\star},\qquad\overline{\bm{v}}_{i}^{\star}=\frac{1}{\|\bm{v}_{i}^{\star}\|_{2}}\bm{v}_{i}^{\star},\qquad
and\qquad\overline{\bm{w}}_{i}^{\star}=\frac{1}{\|\bm{w}_{i}^{\star}\|_{2}}\bm{w}_{i}^{\star}.$
(286)

Given a sufficiently accurate subspace estimate $\bm{U}$ for $\bm{U}^{\star}$
obtained in the subspace estimation stage, for each $1\leq i\leq r$, there
exists at least a point $1\leq\tau\leq L$ such that the spectral gap of the
population version of
$\bm{T}\times_{1}\bm{\theta}^{\tau}=\bm{T}\times_{1}\mathcal{P}_{\bm{U}}(\bm{g}^{\tau})$
(with respect to the sampling and noise) is large enough and that the
perturbation is sufficiently small. As a result, the top left (resp. right)
singular vector $\bm{\nu}^{(2)}$ (resp. $\bm{\nu}^{(3)}$) of
$\bm{T}\times_{1}\bm{\theta}^{\tau}$ is close to the (normalized) tensor
factor $\overline{\bm{v}}_{i}^{\star}$ (resp. $\overline{\bm{w}}_{i}^{\star}$)
both in the $\ell_{2}$ and $\ell_{\infty}$ norm (similar to Lemmas 5.13-5.14
in Section 5.3 for the symmetric case). In turn, this further allows us to
reliably estimate $\overline{\bm{u}}_{i}^{\star}$ and the magnitude
$\lambda_{i}^{\star}$, in a way similar to what we have done in Lemma 5.16 in
Section 5.3. By repeating the procedures with random restarts and invoking a
pruning procedure similar to the symmetric case, we can hope to recover all
tensor factors with high probability.

Following the above strategies, one could adapt the proofs of Theorems
5.9-5.10 in Section 5.3 to show that: our initial estimates
$\\{\bm{u}_{i},\bm{v}_{i},\bm{w}_{i}\\}_{i=1}^{r}$ are all exceedingly close
to the ground truth in the entrywise sense (up to global permutation and
global signs). This in turn confirms that the algorithm will enter a locally
strongly convex and smooth region as characterized in Lemma E.2, thus leading
to our performance guarantees for the entire algorithm. Once again, while the
analysis ideas for the asymmetric case bear much resemblance to the symmetric
counterpart, a complete proof has to be fairly long due to more clumsy
notation compared to the symmetric case; for the sake of brevity, we do not
provide the full proof here.

###  E.5 Proof of Lemma E.2

Fix arbitrary matrices
$\bm{X}=[\bm{x}_{1},\cdots,\bm{x}_{r}]\in\mathbb{R}^{d_{1}\times r}$,
$\bm{Y}=[\bm{y}_{1},\cdots,\bm{y}_{r}]\in\mathbb{R}^{d_{2}\times r}$ and
$\bm{Z}=[\bm{z}_{1},\cdots,\bm{z}_{r}]\in\mathbb{R}^{d_{3}\times r}$. Direct
computation reveals that

$\displaystyle\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\ \bm{Y}\\\
\bm{Z}\end{bmatrix}\right)^{\top}\nabla^{2}g_{\mathsf{clean}}(\bm{U},\bm{V},\bm{W})\,\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\
\bm{Y}\\\ \bm{Z}\end{bmatrix}\right)$
$\displaystyle\qquad=\frac{1}{3p}\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{y}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{z}_{i}\Big{)}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\qquad\quad+\frac{2}{3p}\,\Big{\langle}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{y}_{i}\otimes\bm{w}_{i}+\bm{x}_{i}\otimes\bm{v}_{i}\otimes\bm{z}_{i}+\bm{u}_{i}\otimes\bm{y}_{i}\otimes\bm{z}_{i},\mathcal{P}_{\Omega}\Big{(}\sum_{i=1}^{r}\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}-\bm{T}^{\star}\Big{)}\Big{\rangle}$
$\displaystyle\qquad\quad+\frac{1}{3}\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{u}_{i}\rangle-\langle\bm{y}_{i},\bm{v}_{i}\rangle\big{)}^{2}+\frac{1}{6}\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{u}_{i}\|_{2}^{2}-\|\bm{v}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)}$
$\displaystyle\qquad\quad+\frac{1}{3}\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{u}_{i}\rangle-\langle\bm{z}_{i},\bm{w}_{i}\rangle\big{)}^{2}+\frac{1}{6}\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{u}_{i}\|_{2}^{2}-\|\bm{w}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{z}_{i}\|_{2}^{2}\big{)}$
$\displaystyle\qquad\quad+\frac{1}{3}\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{y}_{i},\bm{v}_{i}\rangle-\langle\bm{z}_{i},\bm{w}_{i}\rangle\big{)}^{2}+\frac{1}{6}\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{v}_{i}\|_{2}^{2}-\|\bm{w}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{y}_{i}\|_{2}^{2}-\|\bm{z}_{i}\|_{2}^{2}\big{)}.$

For notational convenience, we shall define

$\displaystyle\bm{\Delta}^{\bm{U}}=\big{[}\bm{\Delta}_{1}^{\bm{U}},\cdots,\bm{\Delta}_{r}^{\bm{U}}\big{]}:=\bm{U}\bm{S}^{(1)}-\bm{U}^{\star}\in\mathbb{R}^{d_{1}\times
r},$

and define $\bm{\Delta}^{\bm{V}}\in\mathbb{R}^{d_{2}\times r}$ and
$\bm{\Delta}^{\bm{W}}\in\mathbb{R}^{d_{3}\times r}$ in an analogous manner.
Without loss of generality, it is assumed that $\bm{S}^{(1)}=\bm{I}_{r}$ and
$\bm{S}^{(2)}=\bm{S}^{(3)}=-\bm{I}_{r}$.

With the above notation in place, one can decompose

$\displaystyle\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\ \bm{Y}\\\
\bm{Z}\end{bmatrix}\right)^{\top}\nabla^{2}g_{\mathsf{clean}}(\bm{U},\bm{V},\bm{W})\,\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\
\bm{Y}\\\ \bm{Z}\end{bmatrix}\right)$ $\displaystyle=\sum_{i=1}^{4}\beta_{i}$

where $\beta_{i},1\leq i\leq 4$ are given respectively by

$\displaystyle\beta_{1}$
$\displaystyle:=\frac{1}{3}\,\Big{\|}\sum_{i=1}^{r}\bm{x}_{i}\otimes(-\bm{v}_{i}^{\star})\otimes(-\bm{w}_{i}^{\star})+\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes(-\bm{w}_{i}^{\star})+\bm{u}_{i}^{\star}\otimes(-\bm{v}_{i}^{\star})\otimes\bm{z}_{i}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\,\quad+\frac{1}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\Big{[}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle-\langle\bm{y}_{i},-\bm{v}_{i}^{\star}\rangle\big{)}^{2}+\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle-\langle\bm{z}_{i},-\bm{w}_{i}^{\star}\rangle\big{)}^{2}+\big{(}\langle\bm{y}_{i},-\bm{v}_{i}^{\star}\rangle-\langle\bm{z}_{i},-\bm{w}_{i}^{\star}\rangle\big{)}^{2}\Big{]},$
(287a) $\displaystyle\beta_{2}$
$\displaystyle:=\frac{1}{3p}\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{y}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{z}_{i}\Big{)}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\,\qquad-\frac{1}{3}\,\Big{\|}\sum_{i=1}^{r}\bm{x}_{i}\otimes(-\bm{v}_{i}^{\star})\otimes(-\bm{w}_{i}^{\star})+\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes(-\bm{w}_{i}^{\star})+\bm{u}_{i}^{\star}\otimes(-\bm{v}_{i}^{\star})\otimes\bm{z}_{i}\Big{\|}_{\mathrm{F}}^{2},$
(287b) $\displaystyle\beta_{3}$
$\displaystyle:=\frac{2}{3p}\,\Big{\langle}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{y}_{i}\otimes\bm{w}_{i}+\bm{x}_{i}\otimes\bm{v}_{i}\otimes\bm{z}_{i}+\bm{u}_{i}\otimes\bm{y}_{i}\otimes\bm{z}_{i},\mathcal{P}_{\Omega}\Big{(}\sum_{i=1}^{r}\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}-\bm{T}^{\star}\Big{)}\Big{\rangle},$
(287c) $\displaystyle\beta_{4}$
$\displaystyle:=\frac{1}{3}\sum_{i=1}^{r}\big{(}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{)}\Big{[}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle-\langle\bm{y}_{i},-\bm{v}_{i}^{\star}\rangle\big{)}^{2}+\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle-\langle\bm{z}_{i},-\bm{w}_{i}^{\star}\rangle\big{)}^{2}+\big{(}\langle\bm{y}_{i},-\bm{v}_{i}^{\star}\rangle-\langle\bm{z}_{i},-\bm{w}_{i}^{\star}\rangle\big{)}^{2}\Big{]}$
$\displaystyle\,\quad+\frac{1}{3}\sum_{i=1}^{r}\alpha_{i}\Big{[}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle\big{)}^{2}+\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{z}_{i},\bm{\Delta}_{i}^{\bm{W}}\rangle\big{)}^{2}+\big{(}\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle-\langle\bm{z}_{i},\bm{\Delta}_{i}^{\bm{W}}\rangle\big{)}^{2}\Big{]}$
$\displaystyle\,\quad+\frac{2}{3}\sum_{i=1}^{r}\alpha_{i}\Big{[}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle-\langle\bm{y}_{i},-\bm{v}_{i}^{\star}\rangle\big{)}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle\big{)}+\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle-\langle\bm{z}_{i},-\bm{w}_{i}^{\star}\rangle\big{)}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{z}_{i},\bm{\Delta}_{i}^{\bm{W}}\rangle\big{)}$
$\displaystyle\,\quad\qquad+\big{(}\langle\bm{y}_{i},-\bm{v}_{i}^{\star}\rangle-\langle\bm{z}_{i},-\bm{w}_{i}^{\star}\rangle\big{)}\big{(}\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle-\langle\bm{z}_{i},\bm{\Delta}_{i}^{\bm{W}}\rangle\big{)}\Big{]}$
$\displaystyle\,\quad+\frac{1}{6}\sum_{i=1}^{r}\alpha_{i}\Big{[}\big{(}\|\bm{u}_{i}\|_{2}^{2}-\|\bm{v}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)}+\big{(}\|\bm{u}_{i}\|_{2}^{2}-\|\bm{w}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{z}_{i}\|_{2}^{2}\big{)}$
$\displaystyle\,\quad\qquad+\big{(}\|\bm{v}_{i}\|_{2}^{2}-\|\bm{w}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{y}_{i}\|_{2}^{2}-\|\bm{z}_{i}\|_{2}^{2}\big{)}\Big{]}.$
(287d)

In what follows, we shall demonstrate that $\beta_{1}$ is the dominant term,
with the remaining terms being negligible compared to $\beta_{1}$. Here, we
note that the proof idea is almost identical to that of the symmetric case
(cf. Lemma 5.1 in Appendix 5.1). For the sake of conciseness, we will focus
only on the part where the symmetric and the asymmetric cases differ, and omit
the proof details when their analyses are similar.

##### Bounding $\beta_{1}$

Let us first expand

$\displaystyle\beta_{1}$
$\displaystyle=\frac{1}{3}\,\Big{\|}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}^{\star}-\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes\bm{w}_{i}^{\star}-\bm{u}_{i}^{\star}\otimes\bm{v}_{i}^{\star}\otimes\bm{z}_{i}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\quad+\frac{1}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\Big{[}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle+\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle\big{)}^{2}+\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle+\langle\bm{z}_{i},\bm{w}_{i}^{\star}\rangle\big{)}^{2}+\big{(}\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle-\langle\bm{z}_{i},\bm{w}_{i}^{\star}\rangle\big{)}^{2}\Big{]}$
$\displaystyle=\underbrace{\frac{1}{3}\,\Big{\|}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}^{\star}\Big{\|}_{\mathrm{F}}^{2}+\frac{1}{3}\,\Big{\|}\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes\bm{w}_{i}^{\star}\Big{\|}_{\mathrm{F}}^{2}+\frac{1}{3}\,\Big{\|}\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{v}_{i}^{\star}\otimes\bm{z}_{i}\Big{\|}_{\mathrm{F}}^{2}}_{=:\,\gamma_{1}}$
$\displaystyle\quad+\underbrace{\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle^{2}+\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle^{2}+\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\langle\bm{z}_{i},\bm{w}_{i}^{\star}\rangle^{2}}_{=:\,\gamma_{2}}$
$\displaystyle\quad+\underbrace{-\frac{2}{3}\,\Big{\langle}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}^{\star},\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes\bm{w}_{i}^{\star}\Big{\rangle}+\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle}_{=:\,\gamma_{3}}$
$\displaystyle\quad+\underbrace{-\frac{2}{3}\,\Big{\langle}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}^{\star},\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{v}_{i}^{\star}\otimes\bm{z}_{i}\Big{\rangle}+\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle\langle\bm{z}_{i},\bm{w}_{i}^{\star}\rangle}_{=:\,\gamma_{4}}$
$\displaystyle\quad+\underbrace{\frac{2}{3}\,\Big{\langle}\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes\bm{w}_{i}^{\star},\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{v}_{i}^{\star}\otimes\bm{z}_{i}\Big{\rangle}-\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle\langle\bm{z}_{i},\bm{w}_{i}^{\star}\rangle}_{=:\,\gamma_{5}},$

leaving us with five terms to control.

  1. 1.

Let us begin with $\gamma_{1}$. Observe that we can express

$\displaystyle\Big{\|}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}^{\star}\Big{\|}_{\mathrm{F}}=\big{\|}\bm{X}\bm{H}^{\top}\big{\|}_{\mathrm{F}},\qquad\text{with}\quad\bm{H}=[\bm{v}_{1}^{\star}\otimes\bm{w}_{1}^{\star},\cdots,\bm{v}_{r}^{\star}\otimes\bm{w}_{r}^{\star}]\in\mathbb{R}^{d^{2}\times
r}$

Arguing similarly as in the proof of Lemma D.1, one can derive

$\displaystyle\big{|}\sigma_{\min}(\bm{H})-\lambda_{\min}^{\star
2/3}\big{|}\ll\lambda_{\min}^{\star
2/3}\qquad\text{and}\qquad\big{|}\sigma_{\max}(\bm{H})-\lambda_{\max}^{\star
2/3}\big{|}\ll\lambda_{\min}^{\star 2/3},$

provided that $r\ll d_{\min}/\mu$. This leads to the following inequalities

$\displaystyle\frac{19}{20}\lambda_{\min}^{\star
2/3}\left\|\bm{X}\right\|_{\mathrm{F}}\leq\sigma_{\min}(\bm{H})\left\|\bm{X}\right\|_{\mathrm{F}}\leq\Big{\|}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}^{\star}\Big{\|}_{\mathrm{F}}\leq\sigma_{\max}(\bm{H})\left\|\bm{X}\right\|_{\mathrm{F}}\leq\frac{11}{10}\lambda_{\max}^{\star
2/3}\left\|\bm{X}\right\|_{\mathrm{F}}.$

Clearly, the same argument reveals that

$\displaystyle\frac{19}{20}\lambda_{\min}^{\star
2/3}\left\|\bm{Y}\right\|_{\mathrm{F}}\leq\Big{\|}\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes\bm{w}_{i}^{\star}\Big{\|}_{\mathrm{F}}\leq\frac{11}{10}\lambda_{\max}^{\star
2/3}\left\|\bm{Y}\right\|_{\mathrm{F}},$
$\displaystyle\frac{19}{20}\lambda_{\min}^{\star
2/3}\left\|\bm{Z}\right\|_{\mathrm{F}}\leq\Big{\|}\sum_{i=1}^{r}\bm{u}_{i}^{\star}\otimes\bm{v}_{i}^{\star}\otimes\bm{z}_{i}\Big{\|}_{\mathrm{F}}\leq\frac{11}{10}\lambda_{\max}^{\star
2/3}\left\|\bm{Z}\right\|_{\mathrm{F}}.$

Combining these bounds, we reach

$\displaystyle\gamma_{1}\leq\frac{3}{2}\lambda_{\max}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

  2. 2.

We now move on to $\gamma_{2}$. Recall our assumption that
$\|\bm{u}_{i}^{\star}\|_{2}=\|\bm{v}_{i}^{\star}\|_{2}=\|\bm{w}_{i}^{\star}\|_{2}=\lambda_{i}^{\star
1/3}$ for all $1\leq i\leq r$. It follows from the Cauchy-Schwartz inequality
that

$\displaystyle 0\leq\gamma_{2}$
$\displaystyle\leq\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\|\bm{x}_{i}\|^{2}\|\bm{u}_{i}^{\star}\|_{2}^{2}+\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\|\bm{y}_{i}\|^{2}\|\bm{v}_{i}^{\star}\|_{2}^{2}+\frac{2}{3}\sum_{i=1}^{r}\lambda_{i}^{\star
2/3}\|\bm{z}_{i}\|_{2}^{2}\|\bm{w}_{i}^{\star}\|_{2}^{2}$
$\displaystyle\leq\frac{2}{3}\lambda_{\max}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

  3. 3.

Turning to $\gamma_{3}$, one can straightforwardly bound

$\displaystyle|\gamma_{3}|$
$\displaystyle\overset{(\mathrm{i})}{=}\frac{2}{3}\Big{|}\sum_{i_{1}\neq
i_{2}}\langle\bm{x}_{i_{1}},\bm{u}_{i_{2}}^{\star}\rangle\langle\bm{v}_{i_{1}}^{\star},\bm{y}_{i_{2}}\rangle\langle\bm{w}_{i_{1}}^{\star},\bm{w}_{i_{2}}^{\star}\rangle\Big{|}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\max_{i_{1}\neq
i_{2}}\big{|}\langle\bm{w}_{i_{1}}^{\star},\bm{w}_{i_{2}}^{\star}\rangle\big{|}\Big{(}\sum_{i=1}^{r}\|\bm{x}_{i}\|_{2}\|\bm{v}_{i}^{\star}\|_{2}\Big{)}\Big{(}\sum_{i=1}^{r}\|\bm{u}_{i}^{\star}\|_{2}\|\bm{y}_{i}\|_{2}\Big{)}$
$\displaystyle\overset{(\mathrm{iii})}{\leq}\max_{i_{1}\neq
i_{2}}\big{|}\langle\bm{w}_{i_{1}}^{\star},\bm{w}_{i_{2}}^{\star}\rangle\big{|}\|\bm{U}^{\star}\|_{\mathrm{F}}\|\bm{V}^{\star}\|_{\mathrm{F}}\|\bm{X}\|_{\mathrm{F}}\|\bm{Y}\|_{\mathrm{F}}$
$\displaystyle\overset{(\mathrm{iv})}{\leq}r\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{\star
4/3}\|\bm{X}\|_{\mathrm{F}}\|\bm{Y}\|_{\mathrm{F}}$
$\displaystyle\overset{(\mathrm{v})}{\ll}\lambda_{\max}^{\star
4/3}\|\bm{X}\|_{\mathrm{F}}\|\bm{Y}\|_{\mathrm{F}}.$

Here, we have used the fact that
$\|\bm{w}_{i}^{\star}\|_{2}=\lambda_{i}^{\star 1/3}$ in (i); the inequalities
(ii) and (iii) arise from the Cauchy-Schwartz inequality; (iv) follows from
(280c); (v) holds as long as $r\ll\sqrt{d_{\min}/\mu}$. In a similar manner,
one can easily verify that

$\displaystyle|\gamma_{4}|\ll\lambda_{\max}^{\star
4/3}\|\bm{X}\|_{\mathrm{F}}\|\bm{Z}\|_{\mathrm{F}}\qquad\text{and}\qquad|\gamma_{5}|\ll\lambda_{\max}^{\star
4/3}\|\bm{Y}\|_{\mathrm{F}}\|\bm{Z}\|_{\mathrm{F}}.$

It then follows from the AM-GM inequality that

$\displaystyle|\gamma_{3}|+|\gamma_{4}|+|\gamma_{5}|\ll\lambda_{\max}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

  4. 4.

Putting the above bounds together allows us to bound $\beta_{1}$ as follows

$\displaystyle\beta_{1}$
$\displaystyle\leq\gamma_{1}+\gamma_{2}+|\gamma_{3}|+|\gamma_{4}|+|\gamma_{5}|\leq\frac{7}{2}\lambda_{\max}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right);$
$\displaystyle\beta_{1}$
$\displaystyle\geq\gamma_{1}-|\gamma_{3}|-|\gamma_{4}|-|\gamma_{5}|\geq\frac{9}{10}\lambda_{\min}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

##### Bounding $\beta_{2}$

To control $\beta_{2}$, we note that $\beta_{2}$ involves two quantities: (1)
the deviation of
$\frac{1}{p}\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{y}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{z}_{i}\Big{)}\Big{\|}_{\mathrm{F}}^{2}$
from its expectation with respect to $\Omega$; (2) the distance between
$\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{y}_{i}\otimes\bm{w}_{i}+\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{z}_{i}$
and
$\sum_{i=1}^{r}\bm{x}_{i}\otimes\bm{v}_{i}^{\star}\otimes\bm{w}_{i}-\bm{u}_{i}^{\star}\otimes\bm{y}_{i}\otimes\bm{w}_{i}^{\star}-\bm{u}_{i}^{\star}\otimes\bm{v}_{i}^{\star}\otimes\bm{z}_{i}$.
The first term can be shown to be exceedingly small under our sample size
condition with the help of [YZ16, Lemma 5], while the second term is also
guaranteed to be sufficiently small by the assumptions of the error of
$\bm{U},\bm{V}$ and $\bm{W}$ in (285). Therefore, one can apply an analogous
argument for $\alpha_{1}$ and $\alpha_{2}$ in the proof of Lemma 5.1 in
Appendix A to derive: with probability at least
$1-O\big{(}d_{\min}^{-10}\big{)}$ one has

$\displaystyle\big{|}\beta_{2}\big{|}\ll\lambda_{\min}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right),$

provided the sampling rate exceeds
$p\gg\frac{\mu^{2}r^{2}d_{\max}\log^{2}d_{\max}}{d_{1}d_{2}d_{3}}$.

##### Bounding $\beta_{3}$

By the definition of the operator norm, one can bound

$\displaystyle|\beta_{3}|$
$\displaystyle\lesssim\Big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum_{i=1}^{r}\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}-\bm{T}^{\star}\Big{)}\Big{\|}\cdot\sum_{i=1}^{r}\Big{(}\left\|\bm{w}_{i}\right\|_{2}\|\bm{x}_{i}\|_{2}\|\bm{y}_{i}\|_{2}+\left\|\bm{v}_{i}\right\|_{2}\|\bm{x}_{i}\|_{2}\|\bm{z}_{i}\|_{2}+\left\|\bm{u}_{i}\right\|_{2}\|\bm{y}_{i}\|_{2}\|\bm{z}_{i}\|_{2}\Big{)}$
$\displaystyle\lesssim\lambda_{\max}^{2/3}\,\Big{\|}\sum_{i=1}^{r}\bm{u}_{i}\otimes\bm{v}_{i}\otimes\bm{w}_{i}-\bm{T}^{\star}\Big{\|}\Big{\|}p^{-1}\mathcal{P}_{\Omega}\big{(}\bm{1}_{d_{1}}\otimes\bm{1}_{d_{2}}\otimes\bm{1}_{d_{3}}\big{)}\Big{\|}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

One can easily adapt the proof of Lemma D.2 to show that, with probability at
with probability at least $1-O\big{(}d_{\min}^{-10}\big{)},$

$\displaystyle\big{\|}\big{(}p^{-1}\mathcal{P}_{\Omega}-\mathcal{I}\big{)}\big{(}\bm{1}_{d_{1}}\otimes\bm{1}_{d_{2}}\otimes\bm{1}_{d_{3}}\big{)}\big{\|}\lesssim\frac{\log^{3}d_{\max}}{p}+\sqrt{\frac{d_{\max}\log^{5}d_{\max}}{p}}\lesssim\sqrt{d_{1}d_{2}d_{3}}=\big{\|}\bm{1}_{d_{1}}\otimes\bm{1}_{d_{2}}\otimes\bm{1}_{d_{3}}\big{\|}$

holds as long as
$p\gg\max\Big{\\{}\frac{\log^{3}d_{\max}}{\sqrt{d_{1}d_{2}d_{3}}},\,\frac{d_{\max}\log^{5}d_{\max}}{d_{1}d_{2}d_{3}}\Big{\\}}$.
We can then adapt the proof for bounding $\alpha_{3}$ in the proof of Lemma
5.1 in Appendix A to derive that with probability at least
$1-O\big{(}d_{\min}^{-10}\big{)},$

$\displaystyle\big{|}\beta_{3}\big{|}\ll\lambda_{\min}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

##### Bounding $\beta_{4}$

It remains to control $\beta_{4}$. By symmetry, it suffices to consider the
following terms:

$\displaystyle\gamma_{1}$
$\displaystyle:=\sum_{i=1}^{r}\big{(}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{)}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle+\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle\big{)}^{2},$
$\displaystyle\gamma_{2}$
$\displaystyle:=\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle\big{)}^{2},$
$\displaystyle\gamma_{3}$
$\displaystyle:=\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle+\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle\big{)}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle\big{)},$
$\displaystyle\gamma_{4}$
$\displaystyle:=\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{u}_{i}\|_{2}^{2}-\|\bm{v}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)}.$

In the following, we shall bound these four terms separately. By the
assumptions that
$\bm{S}^{(1)}=\bm{I}_{r},\bm{S}^{(2)}=\bm{S}^{(3)}=-\bm{I}_{r}$, $\delta\ll 1$
and $\kappa\asymp 1$, one has

$\displaystyle\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}$
$\displaystyle\leq\|\bm{U}-\bm{U}^{\star}\|_{\mathrm{F}}\leq\delta\,\|\bm{U}^{\star}\|_{\mathrm{F}}\leq\delta\sqrt{r}\lambda_{\max}^{\star
1/3}\ll\lambda_{\min}^{\star 1/3}\leq\|\bm{u}_{i}^{\star}\|_{2};$ (288a)
$\displaystyle\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}$
$\displaystyle\leq\left\|-\bm{V}-\bm{V}^{\star}\right\|_{\mathrm{F}}\leq\delta\,\|\bm{V}^{\star}\|_{\mathrm{F}}\leq\delta\sqrt{r}\lambda_{\max}^{\star
1/3}\ll\lambda_{\min}^{\star 1/3}\leq\|\bm{v}_{i}^{\star}\|_{2};$ (288b)
$\displaystyle\|\bm{\Delta}_{i}^{\bm{W}}\|_{2}$
$\displaystyle\leq\left\|-\bm{W}-\bm{W}^{\star}\right\|_{\mathrm{F}}\leq\delta\,\|\bm{W}^{\star}\|_{\mathrm{F}}\leq\delta\sqrt{r}\lambda_{\max}^{\star
1/3}\ll\lambda_{\min}^{\star 1/3}\leq\|\bm{w}_{i}^{\star}\|_{2}.$ (288c)

In addition, for each $1\leq i\leq r$ , one has

$\frac{9}{10}\lambda_{\min}^{\star
2/3}\leq\lambda_{i}-\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\leq\alpha_{i}\leq\lambda_{i}+\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\leq\frac{11}{10}\lambda_{\max}^{\star 2/3}$ (289)

by virtue of the condition that $\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\ll\lambda_{\min}^{\star 2/3}$.

  1. 1.

Let us start with $\gamma_{1}$. By the condition that
$\max_{i}\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\ll\lambda_{\min}^{\star 2/3}$, it is easily seen that

$\displaystyle|\gamma_{1}|$
$\displaystyle\lesssim\sum_{i=1}^{r}\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle^{2}+\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle^{2}\big{)}\leq\max_{i}\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\sum_{i=1}^{r}\big{(}\|\bm{x}_{i}\|_{2}^{2}\|\bm{u}_{i}^{\star}\|_{2}^{2}+\|\bm{y}_{i}\|_{2}^{2}\|\bm{v}_{i}^{\star}\|_{2}^{2}\big{)}$
$\displaystyle\leq\max_{i}\big{|}\alpha_{i}-\lambda_{i}^{\star
2/3}\big{|}\left(\|\bm{u}_{i}^{\star}\|_{2}^{2}+\|\bm{v}_{i}^{\star}\|_{2}^{2}\right)\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)}\ll\lambda_{\min}^{\star
4/3}\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)},$

with the proviso that $\kappa\asymp 1$.

  2. 2.

As for $\gamma_{2}$, one can bound

$\displaystyle|\gamma_{2}|$
$\displaystyle\lesssim\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle^{2}-\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle^{2}\big{)}\leq\max_{i}\alpha_{i}\sum_{i=1}^{r}\big{(}\|\bm{x}_{i}\|_{2}^{2}\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}+\|\bm{y}_{i}\|_{2}^{2}\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}^{2}\big{)}$
$\displaystyle\leq\max_{i}\alpha_{i}\big{(}\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}+\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}^{2}\big{)}\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)}\ll\lambda_{\min}^{\star
4/3}\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)}.$

Here, we use (288a), (288b), (289) and $\kappa\asymp 1$ in the last step.

  3. 3.

Turning to $\gamma_{3}$, one can develop a similar bound as follows

$\displaystyle|\gamma_{3}|$
$\displaystyle\leq\sqrt{\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{u}_{i}^{\star}\rangle+\langle\bm{y}_{i},\bm{v}_{i}^{\star}\rangle\big{)}^{2}}\cdot\sqrt{\sum_{i=1}^{r}\alpha_{i}\big{(}\langle\bm{x}_{i},\bm{\Delta}_{i}^{\bm{U}}\rangle-\langle\bm{y}_{i},\bm{\Delta}_{i}^{\bm{V}}\rangle\big{)}^{2}}$
$\displaystyle\lesssim\max_{i}\alpha_{i}\sqrt{\left(\|\bm{u}_{i}^{\star}\|_{2}^{2}+\|\bm{v}_{i}^{\star}\|_{2}^{2}\right)\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)}}\cdot\sqrt{\big{(}\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}+\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}^{2}\big{)}\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)}}$
$\displaystyle\ll\lambda_{\min}^{\star
4/3}\big{(}\|\bm{X}\|_{\mathrm{F}}^{2}+\|\bm{Y}\|_{\mathrm{F}}^{2}\big{)}.$

  4. 4.

With regards to $\gamma_{4}$, we can expand

$\displaystyle|\gamma_{4}|$
$\displaystyle=\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{u}_{i}^{\star}+\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}-\left\|-\bm{v}_{i}^{\star}+\bm{\Delta}_{i}^{\bm{V}}\right\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)}$
$\displaystyle=\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{u}_{i}^{\star}\|_{2}^{2}+2\langle\bm{u}_{i}^{\star},\bm{\Delta}_{i}^{\bm{U}}\rangle+\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}-\|\bm{v}_{i}^{\star}\|_{2}^{2}+2\langle\bm{v}_{i}^{\star},\bm{\Delta}_{i}^{\bm{V}}\rangle-\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)}$
$\displaystyle=\sum_{i=1}^{r}\alpha_{i}\big{(}2\langle\bm{u}_{i}^{\star},\bm{\Delta}_{i}^{\bm{U}}\rangle+\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}+2\langle\bm{v}_{i}^{\star},\bm{\Delta}_{i}^{\bm{V}}\rangle-\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)},$

where the last step follows from the assumption
$\|\bm{u}_{i}^{\star}\|_{2}=\|\bm{v}_{i}^{\star}\|_{2}=\|\bm{w}_{i}^{\star}\|_{2}$.
It follows that

$\displaystyle\Big{|}\sum_{i=1}^{r}\alpha_{i}\big{(}\|\bm{u}_{i}\|_{2}^{2}-\|\bm{v}_{i}\|_{2}^{2}\big{)}\big{(}\|\bm{x}_{i}\|_{2}^{2}-\|\bm{y}_{i}\|_{2}^{2}\big{)}\Big{|}$
$\displaystyle\lesssim\sum_{i=1}^{r}\alpha_{i}\big{|}\langle\bm{u}_{i}^{\star},\bm{\Delta}_{i}^{\bm{U}}\rangle+\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}^{2}+\langle\bm{v}_{i}^{\star},\bm{\Delta}_{i}^{\bm{V}}\rangle+\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}^{2}\big{|}\left(\|\bm{x}_{i}\|_{2}^{2}+\|\bm{y}_{i}\|_{2}^{2}\right)$
$\displaystyle\leq\max_{i}\alpha_{i}\big{(}\|\bm{u}_{i}^{\star}\|_{2}\|\bm{\Delta}_{i}^{\bm{U}}\|_{2}+\|\bm{v}_{i}^{\star}\|_{2}\|\bm{\Delta}_{i}^{\bm{V}}\|_{2}\big{)}\sum_{i=1}^{r}\left(\|\bm{x}_{i}\|_{2}^{2}+\|\bm{y}_{i}\|_{2}^{2}\right)$
$\displaystyle\ll\lambda_{\min}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}\right),$

where we have used the conditions that
$\max_{i}\alpha_{i}\lesssim\lambda_{\max}^{\star 2/3}$ and $\kappa\asymp 1$.

  5. 5.

It is not hard to check that similar bounds also hold for the remaining terms
in $\beta_{4}$. As a result, we arrive at

$\displaystyle\big{|}\beta_{4}\big{|}\ll\lambda_{\min}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right).$

##### Combining the previous bounds on $\beta_{1},\beta_{2},\beta_{3}$ and
$\beta_{4}$

Putting the above estimates together, we conclude that with probability at
least $1-O(d_{\min}^{-10})$, one has

$\displaystyle\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\ \bm{Y}\\\
\bm{Z}\end{bmatrix}\right)^{\top}\nabla^{2}g_{\mathsf{clean}}(\bm{U},\bm{V},\bm{W})\,\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\
\bm{Y}\\\ \bm{Z}\end{bmatrix}\right)$
$\displaystyle\geq\beta_{1}-|\beta_{2}|-|\beta_{3}|-|\beta_{4}|\geq\frac{1}{2}\lambda_{\min}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right)$
$\displaystyle\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\ \bm{Y}\\\
\bm{Z}\end{bmatrix}\right)^{\top}\nabla^{2}g_{\mathsf{clean}}(\bm{U},\bm{V},\bm{W})\,\mathsf{vec}\left(\begin{bmatrix}\bm{X}\\\
\bm{Y}\\\ \bm{Z}\end{bmatrix}\right)$
$\displaystyle\leq\beta_{1}+|\beta_{2}|+|\beta_{3}|+|\beta_{4}|\leq
4\lambda_{\max}^{\star
4/3}\left(\left\|\bm{X}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Y}\right\|_{\mathrm{F}}^{2}+\left\|\bm{Z}\right\|_{\mathrm{F}}^{2}\right)$

as claimed.

## References

  * [AFWZ17] E. Abbe, J. Fan, K. Wang, and Y. Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  arXiv:1709.09565, 2017.
  * [AGH+14] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky.  Tensor decompositions for learning latent variable models.  The Journal of Machine Learning Research, 15(1):2773–2832, 2014\.
  * [AGJ14] A. Anandkumar, R. Ge, and M. Janzamin.  Guaranteed non-orthogonal tensor decomposition via alternating rank-$1$ updates.  arXiv preprint arXiv:1402.5180, 2014.
  * [AGJ15] A. Anandkumar, R. Ge, and M. Janzamin.  Learning overcomplete latent variable models through tensor methods.  In Proceedings of the Conference on Learning Theory, pages 36–112, 2015.
  * [AGJ17] A. Anandkumar, R. Ge, and M. Janzamin.  Analyzing tensor power method dynamics in overcomplete regime.  The Journal of Machine Learning Research, 18(1):752–791, 2017.
  * [AW17] M. Ashraphijuo and X. Wang.  Fundamental conditions for low-CP-rank tensor completion.  The Journal of Machine Learning Research, 18(1):2116–2145, 2017\.
  * [BM16] B. Barak and A. Moitra.  Noisy tensor completion via the sum-of-squares hierarchy.  In Conference on Learning Theory, pages 417–445, 2016.
  * [Bub15] S. Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
  * [CC14] Y. Chen and Y. Chi.  Robust spectral compressed sensing via structured matrix completion.  IEEE Transactions on Information Theory, 60(10):6576 – 6601, 2014\.
  * [CC17] Y. Chen and E. J. Candès.  Solving random quadratic systems of equations is nearly as easy as solving linear systems.  Comm. Pure Appl. Math., 70(5):822–883, 2017.
  * [CC18] Y. Chen and Y. Chi.  Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization.  IEEE Signal Processing Magazine, 35(4):14–31, July 2018.
  * [CCF+19] Y. Chen, Y. Chi, J. Fan, C. Ma, and Y. Yan.  Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization.  arXiv preprint arXiv:1902.07698, accepted to SIAM Journal on Optimization, 2019.
  * [CCFM19] Y. Chen, Y. Chi, J. Fan, and C. Ma.  Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval.  Mathematical Programming, 176(1-2):5–37, July 2019.
  * [CFMW19] Y. Chen, J. Fan, C. Ma, and K. Wang.  Spectral method and regularized MLE are both optimal for top-$K$ ranking.  Annals of Statistics, 47(4):2204–2235, August 2019.
  * [CFMY19] Y. Chen, J. Fan, C. Ma, and Y. Yan.  Inference and uncertainty quantification for noisy matrix completion.  arXiv:1906.04159, accepted to the Proceedings of the National Academy of Sciences (PNAS), 2019.
  * [CKK+97] C. A. Cocosco, V. Kollokian, R. K.-S. Kwan, G. B. Pike, and A. C. Evans.  Brainweb: Online interface to a 3d mri simulated brain database.  In NeuroImage. Citeseer, 1997.
  * [CLC19] Y. Chi, Y. Lu, and Y. Chen.  Nonconvex optimization meets low-rank matrix factorization: An overview.  IEEE Transactions on Signal Processing, 67(20):5239–5269, 2019\.
  * [CLC+20] C. Cai, G. Li, Y. Chi, H. V. Poor, and Y. Chen.  Subspace estimation from unbalanced and incomplete data matrices: $\ell_{2,\infty}$ statistical guarantees.  The Annals of Statistics, to appear, 2020.
  * [CLL19] J. Chen, D. Liu, and X. Li.  Nonconvex rectangular matrix completion via gradient descent without $\ell_{2,\infty}$ regularization.  arXiv:1901.06116v1, 2019.
  * [CLPC19] C. Cai, G. Li, H. V. Poor, and Y. Chen.  Nonconvex low-rank tensor completion from noisy data.  In Advances in Neural Information Processing Systems, pages 1863–1874, 2019.
  * [CLS15] E. J. Candes, X. Li, and M. Soltanolkotabi.  Phase retrieval via wirtinger flow: Theory and algorithms.  IEEE Transactions on Information Theory, 61(4):1985–2007, 2015\.
  * [CR09] E. Candès and B. Recht.  Exact matrix completion via convex optimization.  Foundations of Computational Mathematics, 9(6):717–772, April 2009\.
  * [CRY19] H. Chen, G. Raskutti, and M. Yuan.  Non-convex projected gradient descent for generalized low-rank tensor regression.  The Journal of Machine Learning Research, 20(1):172–208, 2019.
  * [CW15] Y. Chen and M. J. Wainwright.  Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees.  arXiv:1509.03025, 2015.
  * [CZA+17] J. Y. Cheng, T. Zhang, M. T. Alley, M. Uecker, M. Lustig, J. M. Pauly, and S. S. Vasanawala.  Comprehensive multi-dimensional MRI for the simultaneous assessment of cardiopulmonary anatomy and physiology.  Scientific reports, 7(1):5330, 2017.
  * [DBBG19] D. Driggs, S. Becker, and J. Boyd-Graber.  Tensor robust principal component analysis: Better recovery with atomic norm regularization.  arXiv preprint arXiv:1901.10991, 2019.
  * [DC18] L. Ding and Y. Chen.  The leave-one-out approach for matrix completion: Primal and dual analysis.  arXiv preprint arXiv:1803.07554, 2018.
  * [DR16] M. A. Davenport and J. Romberg.  An overview of low-rank matrix recovery from incomplete observations.  IEEE Journal of Selected Topics in Signal Processing, 10(4):608–622, 2016.
  * [EAHK13] G. Ely, S. Aeron, N. Hao, and M. E. Kilmer.  5D and 4D pre-stack seismic data completion using tensor nuclear norm (TNN).  In SEG Technical Program Expanded Abstracts 2013, pages 3639–3644. Society of Exploration Geophysicists, 2013.
  * [EK15] N. El Karoui.  On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators.  Probability Theory and Related Fields, pages 1–81, 2015.
  * [FL19] V. F. Farias and A. A. Li.  Learning preferences with side information.  Management Science, 65(7):3131–3149, 2019.
  * [GBW18] D. Gilboa, S. Buchanan, and J. Wright.  Efficient dictionary learning with gradient descent.  arXiv preprint arXiv:1809.10313, 2018.
  * [GHJY15] R. Ge, F. Huang, C. Jin, and Y. Yuan.  Escaping from saddle points online stochastic gradient for tensor decomposition.  In Conference on Learning Theory, pages 797–842, 2015.
  * [GM17] R. Ge and T. Ma.  On the optimization landscape of tensor decompositions.  arXiv preprint arXiv:1706.05598, 2017.
  * [GQ14] D. Goldfarb and Z. Qin.  Robust low-rank tensor recovery: Models and algorithms.  SIAM Journal on Matrix Analysis and Applications, 35(1):225–253, 2014.
  * [Gro11] D. Gross.  Recovering low-rank matrices from few coefficients in any basis.  IEEE Transactions on Information Theory, 57(3):1548–1566, March 2011.
  * [GRY11] S. Gandy, B. Recht, and I. Yamada.  Tensor completion and low-$n$-rank tensor recovery via convex optimization.  Inverse Problems, 27(2):025010, 2011.
  * [HL13] C. J. Hillar and L.-H. Lim.  Most tensor problems are np-hard.  Journal of the ACM (JACM), 60(6):45, 2013.
  * [HMGW15] B. Huang, C. Mu, D. Goldfarb, and J. Wright.  Provable models for robust low-rank tensor completion.  Pacific Journal of Optimization, 11(2):339–364, 2015.
  * [HSSS16] S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer.  Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 178–191. ACM, 2016.
  * [HWW+19] B. Hao, B. Wang, P. Wang, J. Zhang, J. Yang, and W. W. Sun.  Sparse tensor additive regression.  arXiv preprint arXiv:1904.00479, 2019.
  * [HZC20] B. Hao, A. Zhang, and G. Cheng.  Sparse and low-rank tensor estimation via cubic sketchings.  IEEE Transactions on Information Theory, 2020.
  * [JHZ+16] T.-Y. Ji, T.-Z. Huang, X.-L. Zhao, T.-H. Ma, and G. Liu.  Tensor completion using total variation and low-rank matrix factorization.  Information Sciences, 326:243–257, 2016.
  * [JO14] P. Jain and S. Oh.  Provable tensor factorization with missing data.  In Advances in Neural Information Processing Systems, pages 1431–1439, 2014.
  * [KB09] T. G. Kolda and B. W. Bader.  Tensor decompositions and applications.  SIAM review, 51(3):455–500, 2009.
  * [KBHH13] M. E. Kilmer, K. Braman, N. Hao, and R. C. Hoover.  Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging.  SIAM Journal on Matrix Analysis and Applications, 34(1):148–172, 2013.
  * [KM16] H. Kasai and B. Mishra.  Low-rank tensor completion: a riemannian manifold preconditioning approach.  In International Conference on Machine Learning, pages 1012–1021, 2016.
  * [KMO10a] R. H. Keshavan, A. Montanari, and S. Oh.  Matrix completion from a few entries.  IEEE transactions on information theory, 56(6):2980–2998, 2010\.
  * [KMO10b] R. H. Keshavan, A. Montanari, and S. Oh.  Matrix completion from noisy entries.  J. Mach. Learn. Res., 11:2057–2078, 2010.
  * [KOKC13] H.-J. Kim, E. Ollila, V. Koivunen, and C. Croux.  Robust and sparse estimation of tensor decompositions.  In 2013 IEEE Global Conference on Signal and Information Processing, pages 965–968. IEEE, 2013.
  * [Kol01] T. G. Kolda.  Orthogonal tensor decompositions.  SIAM Journal on Matrix Analysis and Applications, 23(1):243–255, 2001.
  * [Kol11] V. Koltchinskii.  Oracle inequalities in empirical risk minimization and sparse recovery problems, volume 2033 of Lecture Notes in Mathematics.  2011\.
  * [KS13] A. Krishnamurthy and A. Singh.  Low-rank matrix and tensor completion via adaptive sampling.  In Advances in Neural Information Processing Systems, pages 836–844, 2013.
  * [KSS13] N. Kreimer, A. Stanton, and M. D. Sacchi.  Tensor completion based on nuclear norm minimization for 5d seismic data reconstruction.  Geophysics, 78(6):V273–V284, 2013.
  * [LFC+16] C. Lu, J. Feng, Y. Chen, W. Liu, Z. Lin, and S. Yan.  Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5249–5257, 2016.
  * [LMWY13] J. Liu, P. Musialski, P. Wonka, and J. Ye.  Tensor completion for estimating missing values in visual data.  IEEE transactions on pattern analysis and machine intelligence, 35(1):208–220, 2013.
  * [Lou14] K. Lounici.  High-dimensional covariance matrix estimation with missing observations.  Bernoulli, 20(3):1029–1058, 2014.
  * [LSC+14] Y. Liu, F. Shang, H. Cheng, J. Cheng, and H. Tong.  Factor matrix trace norm minimization for low-rank tensor completion.  In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 866–874. SIAM, 2014.
  * [LT17] Q. Li and G. Tang.  Convex and nonconvex geometries of symmetric tensor factorization.  In 2017 51st Asilomar Conference on Signals, Systems, and Computers, pages 305–309. IEEE, 2017.
  * [LYX17] X. Li, Y. Ye, and X. Xu.  Low-rank tensor completion with total variation for visual data inpainting.  In Thirty-First AAAI Conference on Artificial Intelligence, 2017\.
  * [LZT19] Q. Li, Z. Zhu, and G. Tang.  The non-convex geometry of low-rank matrix optimization.  Information and Inference: A Journal of the IMA, 8(1):51–96, 2019\.
  * [MHWG14] C. Mu, B. Huang, J. Wright, and D. Goldfarb.  Square deal: Lower bounds and improved relaxations for tensor recovery.  In International conference on machine learning, pages 73–81, 2014\.
  * [MP20] V. V. Mišić and G. Perakis.  Data analytics in operations management: A review.  Manufacturing & Service Operations Management, 22(1):158–169, 2020\.
  * [MS18] A. Montanari and N. Sun.  Spectral algorithms for tensor completion.  Communications on Pure and Applied Mathematics, 71(11):2381–2425, 2018.
  * [MWCC17] C. Ma, K. Wang, Y. Chi, and Y. Chen.  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution.  arXiv preprint arXiv:1711.10467, accepted to Foundations of Computational Mathematics, 2017.
  * [NDT15] N. H. Nguyen, P. Drineas, and T. D. Tran.  Tensor sparsification via a bound on the spectral norm of random tensors.  Information and Inference: A Journal of the IMA, 4(3):195–229, 2015\.
  * [Paw19] C. Pawlowski.  Machine learning for problems with missing and uncertain data with applications to personalized medicine.  PhD thesis, Massachusetts Institute of Technology, 2019.
  * [PS17] A. Potechin and D. Steurer.  Exact tensor completion with sum-of-squares.  In Conference on Learning Theory, pages 1619–1673, 2017.
  * [PW19] A. Pananjady and M. J. Wainwright.  Value function estimation in markov reward processes: Instance-dependent $\ell_{\infty}$-bounds for policy evaluation.  arXiv preprint arXiv:1909.08749, 2019.
  * [RM14] E. Richard and A. Montanari.  A statistical model for tensor PCA.  In Advances in Neural Information Processing Systems, pages 2897–2905, 2014.
  * [RPP13] B. Romera-Paredes and M. Pontil.  A new convex relaxation for tensor completion.  In Advances in Neural Information Processing Systems, pages 2967–2975, 2013.
  * [RSS17] H. Rauhut, R. Schneider, and Ž. Stojanac.  Low rank tensor recovery via iterative hard thresholding.  Linear Algebra and its Applications, 523:220–262, 2017.
  * [SDLF+17] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. E. Papalexakis, and C. Faloutsos.  Tensor decomposition for signal processing and machine learning.  IEEE Transactions on Signal Processing, 65(13):3551–3582, 2017\.
  * [SHKM14] O. Semerci, N. Hao, M. E. Kilmer, and E. L. Miller.  Tensor-based formulation and nuclear norm regularization for multienergy computed tomography.  IEEE Transactions on Image Processing, 23(4):1678–1693, 2014.
  * [SL16] R. Sun and Z.-Q. Luo.  Guaranteed matrix completion via non-convex factorization.  IEEE Transactions on Information Theory, 62(11):6535–6579, 2016\.
  * [SLLC17] W. W. Sun, J. Lu, H. Liu, and G. Cheng.  Provable sparse tensor decomposition.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(3):899–916, 2017.
  * [SN16] S. R. Soroushmehr and K. Najarian.  Transforming big data into computational models for personalized medicine and health care.  Dialogues in clinical neuroscience, 18(3):339, 2016.
  * [Ste16] M. Steinlechner.  Riemannian optimization for high-dimensional tensor completion.  SIAM Journal on Scientific Computing, 38(5):S461–S484, 2016.
  * [SY19] D. Shah and C. L. Yu.  Iterative collaborative filtering for sparse noisy tensor estimation.  arXiv preprint arXiv:1908.01241, 2019.
  * [TBS+16] S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht.  Low-rank solutions of linear matrix equations via procrustes flow.  In International Conference on Machine Learning, pages 964–973, 2016.
  * [THK10] R. Tomioka, K. Hayashi, and H. Kashima.  Estimation of low-rank tensors via convex optimization.  arXiv preprint arXiv:1010.0789, 2010.
  * [TS15] G. Tang and P. Shah.  Guaranteed tensor decomposition: A moment approach.  In International Conference on Machine Learning, pages 1491–1500, 2015.
  * [TV19] Y. S. Tan and R. Vershynin.  Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval.  arXiv preprint arXiv:1910.12837, 2019.
  * [Ver10] R. Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  arXiv preprint arXiv:1011.3027, 2010.
  * [Ver18] R. Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge University Press, 2018.
  * [WAA16] W. Wang, V. Aggarwal, and S. Aeron.  Tensor completion by alternating minimization under the tensor train (tt) model.  arXiv preprint arXiv:1609.05587, 2016.
  * [XHYS15] Y. Xu, R. Hao, W. Yin, and Z. Su.  Parallel matrix factorization for low-rank tensor completion.  Inverse Problems & Imaging, 9(2):601–624, 2015.
  * [XY13] Y. Xu and W. Yin.  A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion.  SIAM Journal on imaging sciences, 6(3):1758–1789, 2013.
  * [XY17] D. Xia and M. Yuan.  On polynomial time methods for exact low rank tensor completion.  arXiv preprint arXiv:1702.06980, 2017.
  * [XYZ17] D. Xia, M. Yuan, and C.-H. Zhang.  Statistically optimal and computationally efficient low rank tensor completion from noisy entries.  arXiv preprint arXiv:1711.04934, 2017.
  * [Yao18] Q. Yao.  Scalable tensor completion with nonconvex regularization.  arXiv preprint arXiv:1807.08725, 2018.
  * [YLW+17] J. Ying, H. Lu, Q. Wei, J.-F. Cai, D. Guo, J. Wu, Z. Chen, and X. Qu.  Hankel matrix nuclear norm regularized tensor completion for $n$-dimensional exponential signals.  IEEE Transactions on Signal Processing, 65(14):3702–3717, 2017\.
  * [YPCC16] X. Yi, D. Park, Y. Chen, and C. Caramanis.  Fast algorithms for robust PCA via gradient descent.  In NIPS, pages 4152–4160, 2016.
  * [YZ16] M. Yuan and C.-H. Zhang.  On tensor completion via nuclear norm minimization.  Foundations of Computational Mathematics, 16(4):1031–1068, 2016\.
  * [YZ17] M. Yuan and C.-H. Zhang.  Incoherent tensor norms and their applications in higher order tensor completion.  IEEE Transactions on Information Theory, 63(10):6753–6766, 2017\.
  * [ZA17] Z. Zhang and S. Aeron.  Exact tensor completion using t-svd.  IEEE Trans. Signal Processing, 65(6):1511–1526, 2017.
  * [ZB18] Y. Zhong and N. Boumal.  Near-optimal bounds for phase synchronization.  SIAM Journal on Optimization, 28(2):989–1016, 2018.
  * [Zha19] A. Zhang.  Cross: Efficient low-rank tensor completion.  The Annals of Statistics, 47(2):936–964, 2019.
  * [ZKOM18] A. M. Zoubir, V. Koivunen, E. Ollila, and M. Muma.  Robust statistics for signal processing.  Cambridge University Press, 2018.
  * [ZL16] Q. Zheng and J. Lafferty.  Convergence analysis for rectangular matrix completion using Burer-Monteiro factorization and gradient descent.  arXiv:1605.07051, 2016.
  * [ZX18] A. Zhang and D. Xia.  Tensor SVD: Statistical and computational limits.  IEEE Transactions on Information Theory, 64(11):7311–7338, 2018\.