varying from 0.001 to 0.015. The results are displayed in Figure 7 showing
that BIC is more sensitive to $\mathbf{r}$ and less sensitive to $\alpha$ for
a small range. After the true $\mathbf{r}$ is identified, the BIC criterion
works reasonably well for selecting $\alpha$.

Figure 7: BIC values for binary tensor learning; the true rank
$\mathbf{r}=(3,3,3)^{\top}$. Left: true $\alpha=0.005$; Right: true
$\alpha=0.01$. The BIC curve for $\mathbf{r}=(3,3,3)^{\top}$ is highlighted.

###  10.2 Tensor Sub-Gaussian Robust PCA

The low-rank tensor $\bm{\mathcal{T}}^{\ast}\in\mathbb{R}^{d\times d\times d}$
with $d=100$ and Tucker ranks $\mathbf{r}=(2,2,2)^{\top}$ is generated from
the HOSVD of a trimmed standard normal tensor. It satisfies the spikiness
condition, with high probability, and has singular values
$\bar{\lambda}\approx 3$ and $\underline{\lambda}\approx 1$. Given a sparsity
level $\alpha\in(0,1)$, the entries of sparse tensor $\bm{\mathcal{S}}^{\ast}$
are i.i.d. sampled from ${\rm Be}(\alpha)\times{\rm N}(0,1)$, which ensures
$\bm{\mathcal{S}}^{\ast}\in\SS_{O(\alpha)}$ with high probability. This
ensures that the non-zero entries of $\bm{\mathcal{S}}^{\ast}$ have typically
much larger magnitudes than the entries of $\bm{\mathcal{T}}^{\ast}$. The
noise tensor $\bm{\mathcal{Z}}$ has i.i.d. entries sampled from ${\rm
N}(0,\sigma_{z}^{2})$. The default choice of $\gamma$ is 2,
$\textsf{k}_{\textsf{pr}}=\infty$ and $\mu_{1}$ is set as previously. The
convergence performances of
$\log(\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm
F}/\|\bm{\mathcal{T}}^{\ast}\|_{\rm F})$ by Algorithm 2 are examined and
presented in the left panels of Figure 8.

The top-left plot in Figure 8 displays the effects of $\alpha$ on the
convergence of Algorithm 2. It shows that the convergence speed of Algorithm 2
is insensitive to $\alpha$, while the error of final estimates
$\widehat{\bm{\mathcal{T}}}_{l_{\max}}$ is related to $\alpha$. This is
consistent with the claims of Theorem 5.1. In the middle-left plot of Figure
8, we observe that, for a fixed sparsity level $\alpha$, the error of final
estimates grows as the tuning parameter $\gamma$ becomes larger. The bottom-
left plot of Figure 8 shows the convergence of Algorithm 2 for different noise
levels. All these plots confirm the fast convergence of our Riemannian
gradient descent algorithm. In particular, there are stages during which the
log relative error decreases linearly w.r.t. the number of iterations, as
proved in Theorem 4.1.

The statistical stability of the final estimates by Algorithm 2 is
demonstrated in the right panels of Figure 8. Each curve represents the
average relative error of $\widehat{\bm{\mathcal{T}}}_{l_{\max}}$ based on
$10$ simulations, and the error bar shows the confidence region by one
empirical standard deviation. Based on these plots, we observe that the
standard deviations of
$\|\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{\ast}\|_{\rm F}$
grow as the noise level $\sigma_{z}$, the sparsity level $\alpha$ or the
tuning parameter $\gamma$ increases.

(a) Change of sparsity $\alpha$. Left: $\sigma_{z}=0.01,\gamma=2$; Right:
$\gamma=2$

(b) Change of $\gamma$. Left: $\alpha=0.02,\sigma_{z}=0.01$; Right:
$\alpha=0.02$

(c) Change of noise size $\sigma_{z}$. Left: $\alpha=0.02,\gamma=2$; Right:
$\gamma=2$

Figure 8: Performances of Algorithm 2 for SG-RPCA. The low-rank
$\bm{\mathcal{T}}^{\ast}$ has size $d\times d\times d$ with $d=100$ and has
Tucker ranks $\mathbf{r}=(2,2,2)^{\top}$. The relative error on left panels is
defined by $\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm
F}/\|\bm{\mathcal{T}}^{\ast}\|_{\rm F}$. The error bars on the right panels
are based on $1$ standard deviation from 10 replications. Here the default
$\gamma$ is $2$.

###  10.3 Tensor PCA with Heavy-tailed Noise

The low-rank tensor $\bm{\mathcal{T}}^{\ast}\in\mathbb{R}^{d\times d\times d}$
with $d=100$ and Tucker ranks $\mathbf{r}=(2,2,2)^{\top}$ is generated from
the HOSVD of a trimmed standard normal tensor, as in Section 10.2. Given a
parameter $\theta$, we generate the noisy tensor whose entries are i.i.d. and
satisfy the Student-t distribution with degree of freedom $\theta$. But notice
here we also apply a global scaling to better control the noise standard
deviation. We denote the noisy tensor after scaling by $\bm{\mathcal{Z}}$.
This generated tensor $\bm{\mathcal{Z}}$ satisfies Assumption 4 with the same
parameter $\theta$. Once the parameter $\theta$ and global scaling are given,
we are able to calculate the variance $\sigma_{z}^{2}$. The convergence
performances of
$\log(\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm
F}/\|\bm{\mathcal{T}}^{\ast}\|_{\rm F})$ by Algorithm 2 are examined and
presented in the upper panels of Figure 9.

In this experiment, we set $\gamma=2,\textsf{k}_{\textsf{pr}}=\infty$ and
$\mu_{1}$ as previously. The top-left plot in Figure 9 displays the effects of
$\alpha$ on the convergence of Algorithm 2. The case $\alpha=0$ reduces to the
normal Riemannian gradient descent, which cannot output a satisfiable result
due to the heavy-tailed noise, even if a warm initialization is provided. This
shows the importance of gradient pruning in Algorithm 2. When $\alpha>0$, the
convergence speed of the algorithm is insensitive to $\alpha$, but the final
estimates $\widehat{\bm{\mathcal{T}}}_{l_{\max}}$ is related to $\alpha$. In
the top-right plot of Figure 9, we observe the error becomes larger as
$\theta$ decreases (or equivalently, as $\sigma_{z}^{2}$ increases). All these
results match the claim of Theorem 5.4 and confirm the fast convergence of
Riemannian gradient descent. And there are indeed stages where the log
relative error decreases linearly w.r.t. the number of iterations.

The statistical stability of the final estimates by Algorithm 2 applied to
tensor PCA with heavy-tailed noise is demonstrated in the bottom panel of
Figure 9. Each curve represents the average relative error of
$\widehat{\bm{\mathcal{T}}}_{l_{\max}}$ based on $5$ simulations, and the
error bar shows the confidence region by one empirical standard deviation.
Based on these plots, we observe that for each fixed $\theta$ (or
$\sigma_{z}^{2}$, equivalently), we need to choose $\alpha$ carefully to
achieve the best performance. This is reasonable since in the heavy-tail noise
setting, we do not know the sparsity of outliers. Also, the figure shows that
Algorithm 2 is stable for different $\alpha$ and $\theta$.

(a) Left: Change of $\alpha$, $\theta=2.2(\sigma_{z}=0.332)$; Right: Change of
$\theta$, $\alpha=0.01$

(b) Change of $\theta$

Figure 9: Performances of Algorithm 2 for tensor PCA with heavy-tailed noise.
The low-rank $\bm{\mathcal{T}}^{\ast}$ has size $d\times d\times d$ with
$d=100$ and has Tucker ranks $\mathbf{r}=(2,2,2)^{\top}$. The relative error
on upper panels is defined by
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm
F}/\|\bm{\mathcal{T}}^{\ast}\|_{\rm F}$. The error bars on the lower panels
are based on $1$ standard deviation from 5 replications. Here the default
choice of $\gamma$ is 2.

###  10.4 Binary Tensor Learning

In the binary tensor setting, we generate the low-rank tensor
$\bm{\mathcal{T}}^{\ast}\in\mathbb{R}^{d\times d\times d}$ with $d=100$ and
Tucker ranks $\mathbf{r}=(2,2,2)^{\top}$ from the HOSVD of a trimmed standard
normal tensor. But here we did a scaling to $\bm{\mathcal{T}}^{*}$ so that the
singular value $\bar{\lambda}\approx 300$ and $\underline{\lambda}\approx
100$. Given a sparsity level $\alpha\in(0,1)$, the entries of sparse tensor
$\bm{\mathcal{S}}^{\ast}$ are i.i.d. sampled from ${\rm Be}(\alpha)\times{\rm
N}(0,1)$, which ensures $\bm{\mathcal{S}}^{\ast}\in\SS_{O(\alpha)}$ with high
probability. We generate the tensor $\bm{\mathcal{T}}^{*}$ and
$\bm{\mathcal{S}}^{*}$ in this way in order to meet the requirements of
Assumption 5. In the following experiments, we are considering the logistic
link function with the scaling parameter $\sigma$, i.e.,
$p(x)=(1+e^{-x/\sigma})^{-1}$. The default choice of $\gamma$ is $1.1$,
$\textsf{k}_{\textsf{pr}}=1$ and $\mu_{1}$ is set as previously. The
convergence performances of
$\log(\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm
F}/\|\bm{\mathcal{T}}^{\ast}\|_{\rm F})$ by Algorithm 2 are examined and
presented in the top two panels of Figure 10.

The top-left plot in Figure 10 shows the effect of $\alpha$ on the convergence
of Algorithm 2. From the figure, it is clear that the error of final estimates
$\widehat{\bm{\mathcal{T}}}_{l_{\max}}$ is related to $\alpha$. This again
verifies the results in Theorem 5.7. In the top-right plot in Figure 10, we
can see the error of the final estimates increases as the parameter $\gamma$
becomes larger. All these experiments show that Riemannian gradient descent
converges fast and there are stages when the log relative error decreases
linearly w.r.t. the number of iterations.

The statistical stability of the final estimates by Algorithm 2 is
demonstrated in the bottom panel of Figure 10. Each curve represents the
average relative error of $\widehat{\bm{\mathcal{T}}}_{l_{\max}}$ based on $5$
simulations, and the error bar shows the confidence region by one empirical
standard deviation. From these plots, we observe that the standard deviations
of $\|\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{\ast}\|_{\rm F}$
grow as the noise level, the sparsity level $\alpha$ or the tuning parameter
$\gamma$ increases.

(a) Left: Change of sparsity $\alpha$, $\sigma=1,\gamma=1.1$; Right: Change of
$\gamma$, $\alpha=0.001,\sigma=1$

(b) Left: Change of $\sigma$, $\gamma=1.1$; Right: Change of $\gamma$,
$\alpha=0.001$

Figure 10: Performances of Algorithm 2 for binary tensor learning. The low-
rank $\bm{\mathcal{T}}^{\ast}$ has size $d\times d\times d$ with $d=100$ and
has Tucker ranks $\mathbf{r}=(2,2,2)^{\top}$. The relative error on left
panels is defined by
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm
F}/\|\bm{\mathcal{T}}^{\ast}\|_{\rm F}$. The error bars on the bottom panels
are based on $1$ standard deviation from 5 replications. The default choice of
$\gamma$ is $1.1$.

###  10.5 Tensor Poisson Robust PCA

In the Poisson tensor RPCA case, we generate
$\bm{\mathcal{T}}^{*}\in\mathbb{R}^{d\times d\times d}$ with $d=100$ and
Tucker rank $\mathbf{r}=(2,2,2)^{\top}$ such that
$\|\bm{\mathcal{T}}^{*}\|_{\ell_{\infty}}=0.5$. Meanwhile, the sparse outliers
$\bm{\mathcal{S}}^{*}$ is generated such that all its entries are i.i.d.
sampled from ${\rm Be}(\alpha)\times{\rm N}(0,1)$ and scaled such that
$\|\bm{\mathcal{S}}^{*}\|_{\ell_{\infty}}=0.5$. Throughout the experiments,
both $\zeta$ and $\textsf{k}_{\textsf{pr}}$ is set to 0.5, and the default
choice of $\gamma$ is $1.1$.

In the first experiment, we fix the intensity $I=10$ and change the sparsity
level. The convergence performances of
$\log(\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}/\|\bm{\mathcal{T}}^{*}\|_{\rm F})$ by Algorithm 2 is displayed in the left
panel of Figure 11. In the second experiment, for different values of $\alpha$
and $I$, we conduct 5 i.i.d. instances and plot the error bar. The results are
displayed in the right panel of Figure 11.

Figure 11: Performance of Algorithm 2 for tensor Poisson RPCA. The Tucker rank
of $\bm{\mathcal{T}}^{*}$ is $\mathbf{r}=(2,2,2)^{\top}$. Left: Convergence
behaviors with different $\alpha$ and $I$ is fixed with $I=10$; Right: Error
bar with each setting repeated 5 i.i.d. times. Here $\gamma=1.1$ and
$\textsf{k}_{\textsf{pr}}=0.5$.

##  11 Real Data: Statisticians Hypergraph Co-authorship Network

This dataset [Ji and Jin, 2016] contains the co-authorship relations of $3607$
statisticians based on $3248$ papers published in four prestigious statistics
journals during 2003-2012. The co-authorship network thus has $3607$ nodes and
two nodes are connected by an edge if they collaborated on at least one paper.
A giant connected component of this network consisting of $236$ nodes is seen
to be the “High-Dimensional Data Analysis” community. They also carried out
community detection analysis to discover substructures in this giant
component. See more details in [Ji and Jin, 2016].

We analyze the substructures of the giant component by treating it as a
hypergraph co-authorship network. These $236$ statisticians co-authored $542$
papers555There are $328$ single-authored papers. They provide no information
to co-authorship relations, and are left out in our analysis., among which
$356$ papers have two co-authors, $162$ papers have three co-authors and $24$
papers have four co-authors. A $3$-uniform hypergraph co-authorship network is
constructed by, for $i\neq j\neq k$, adding the hyperedge $(i,j,k)$ if the
authors $i,j,k$ co-authored at least one paper, and adding the hyperedges
$(i,i,j)$ and $(i,j,j)$ if the authors $i,j$ co-authored at least one paper.
The hyperedges are undirected resulting into a symmetric adjacency tensor
$\bm{\mathcal{A}}$. We adopt the framework from Section 5.1 to learn the
latent low-rank tensor $\widehat{\bm{\mathcal{T}}}$ in $\bm{\mathcal{A}}$,
which is used to detect communities in the giant component. We emphasize that
our primary goal is to present the new findings by taking into consideration
of higher-order interactions among co-authors and applying novel robust tensor
methods. It is not our intention to label an author with a certain community.

The Tucker ranks are set as $(4,4,4)$ and sparsity ratio $\alpha$ is varied at
$\\{0,10^{-4},5\times 10^{-4}\\}$. The number of communities is set at $K=3$
and the algorithm is initialized by the HOSVD of $\bm{\mathcal{A}}$. To
uncover community structures, we apply spectral clustering to the singular
vectors of $\widehat{\bm{\mathcal{T}}}$. The node degrees are severely
heterogeneous with Peter Hall, Jianqing Fan and Raymond Carroll being the
top-$3$ statisticians in terms of $\\#$ of co-authors. The naive spectral
clustering often performs poorly in the existence of heterogeneity, skewing to
the high-degree nodes. Indeed, the top-left plot in Figure 12 shows that the
naive spectral clustering identifies these three statisticians as the corners
in a triangle, and puts Peter Hall in a single community. To mitigate the
influence of node heterogeneity, we apply SCORE [Jin, 2015] for community
detection, which uses the leading singular vector of
$\widehat{\bm{\mathcal{T}}}$ as normalization.

(a) Top-left: $\alpha=10^{-4}$ and naive spectral clustering; top-right:
$\alpha=0$ and SCORE; bottom-left: $\alpha=10^{-4}$ and SCORE; bottom-right:
$\alpha=5\times 10^{-4}$ and SCORE.  Figure 12: Sub-structures detected in the
“High-Dimensional Data Analysis” community based on the hypergraph co-
authorship network. The Tucker ranks are set as $(4,4,4)$ with varied sparsity
ratio at $\\{0,10^{-4},5\times 10^{-4}\\}$ and the algorithm is initialized by
the HOSVD of adjacency tensor $\bm{\mathcal{A}}$.

The community structures found by SCORE are displayed in Figure 12. The top-
right plot shows the three clusters identified by SCORE when the sparsity
ratio is zero. The three communities are: 1). “North Carolina” group including
researchers from Duke University, University of North Carolina and North
Carolina State University, together with their close collaborators such as
Debajyoti Sinha, Qi-Man Shao, Bing-Yi Jing, Michael J Todd and etc.; 2).
“Carroll-Hall” group including researchers in non-parametric and semi-
parametric statistics, functional estimation and high-dimensional statistics,
together with collaborators; 3). “Fan and Others” group666We name it the “Fan
and Others” group simply because many researchers in this group are the co-
authors of Jianqing Fan. It is not our intention to rank/label the authors.
including primarily the researchers collaborating closely with Jianqing Fan or
his co-authors, and other researchers who do not obviously belong to the first
two groups. We note that the fields of researchers in “Fan and Others” group
are quite diverse, some of which overlap with those in “Carroll-Hall” group
and “North Carolina” group. However, unlike the results in [Ji and Jin, 2016],
the top-right plot in Figure 12 does not cluster the “Fan and Others” group
into either the “North Carolina” group or “Carroll-Hall” group.

We then set the sparsity ratio of $\widehat{\bm{\mathcal{S}}}$ by
$\alpha=10^{-4}$. The communities identified by SCORE based on the singular
vectors of $\widehat{\bm{\mathcal{T}}}$ are illustrated in the bottom-left
plot of Figure 12. Compared with the top-right plot ($\alpha=0$), the three
communities displayed in the bottom-left plot largely remain the same. But the
group memberships of some authors do change. Notably, Debajyoti Sinha and
Michael J Todd move from the “North Carolina” group to “Fan and Others” group;
Abel Rodriguez moves from the “Carroll-Hall” group to “North-Carolina” group;
several authors (e.g. Daniela M Witten, Jacob Bien, Pan Wei, Chiung-Yu Huang,
Debashis Paul, Zhezhen Jin, Lan Zhang and etc.) move from the “Fan and Others”
group to “Carroll-Hall” group; Hsin-Cheng Huang moves from the “North
Carolina” group to “Carroll-Hall” group; Rasmus Waggepetersen moves from the
“Carroll-Hall” group to “Fan and Others” group. These changes of memberships
suggest that these authors may not have strong ties to the “North Carolina”,
“Carroll-Hall” group or be the co-authors of Jianqing Fan. It may be more
reasonable that these authors constitute a separate group.

This indeed happens when the sparsity ratio $\alpha$ increases to a certain
level. The bottom-right plot of Figure 12 shows the clustering result of SCORE
when $\alpha=5\times 10^{-4}$. Compared with the top-right ($\alpha=0$) and
bottom-left ($\alpha=10^{-4}$) plots, the community structure has a
significant change. Indeed, the “Fan and Others” group now splits into a “Fan”
group including Jianqing Fan and his co-authors, and an “Others” group
including the researchers who do not have obvious ties with “Fan” group.
Moreover, the “Fan” group merges into the “Carroll-Hall” group, which
coincides with the clustering result of SCORE when applied onto the graph co-
authorship network (Fig. 6 in [Ji and Jin, 2016]). Consequently, we name the
three communities in the top-right plot by the “North Carolina”, “Carroll-Fan-
Hall” and “Others” group. Interestingly, many of the authors in the “Others”
group are those whose memberships change when the sparsity ratio $\alpha$
increases from $0$ to $10^{-4}$. See the top-right and bottom-left plots of
Figure 12. In addition, we observe that, as $\alpha$ increases from $10^{-4}$
to $5\times 10^{-4}$, Donglin Zeng and Dan Yu Lin in the “Fan and Others”
group moves to “North Carolina” group. This might be more reasonable since
they both work at the University of North Carolina.

##  12 Proofs of theorems

###  12.1 Proof of Theorem 4.1

We prove the theorem by induction on
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}$ and
$\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm F}$
alternatively. From the initialization condition we have
$\|\widehat{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
c_{1,m}\min\\{\frac{\delta^{2}}{\sqrt{\bar{r}}},(\kappa_{0}^{2m}\sqrt{\bar{r}})^{-1}\\}\cdot\underline{\lambda}$
and $\widehat{\bm{\mathcal{T}}}_{0}\in\mathbb{B}_{\infty}^{\ast}$ is
$(2\mu_{1}\kappa_{0})^{2}$-incoherent.

#### Step 1: Bounding
$\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{\ast}\|_{\rm F}$ for all
$l\geq 0$.

Suppose we have $\widehat{\bm{\mathcal{T}}}_{l}\in\mathbb{B}_{\infty}^{\ast}$
is $(2\mu_{1}\kappa_{0})^{2}$-incoherent and
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
c_{1,m}\min\\{\frac{\delta^{2}}{\sqrt{\bar{r}}},(\kappa_{0}^{2m}\sqrt{\bar{r}})^{-1}\\}\cdot\underline{\lambda}$.

Now we estimate $\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}$. Denote $\Omega_{l}=\text{supp}(\widehat{\bm{\mathcal{S}}}_{l})$ and
$\Omega^{*}=\text{supp}(\bm{\mathcal{S}}^{*})$. For
$\forall\omega\in\Omega_{l}$, from the construction of
$\widehat{\bm{\mathcal{S}}}_{l}$ in Algorithm 1, we have by the definition of
$\textsf{Err}_{\infty}$,

$\displaystyle|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l})]_{\omega}|\leq\min\nolimits_{\|\bm{\mathcal{X}}\|_{\ell_{\infty}}\leq\textsf{k}_{\textsf{pr}}}\|\nabla\mathfrak{L}(\bm{\mathcal{X}})\|_{\ell_{\infty}}\leq\textsf{Err}_{\infty}$
(12.1)

From Assumption 3, we get

$\displaystyle|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l})]_{\omega}-[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*})]_{\omega}|\geq
b_{l}|[\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}]_{\omega}|.$ (12.2)

Note that to use (12.2), we shall verify the neighborhood condition. From the
upper bound of $\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}$ we have $\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\underline{\lambda}/8$, and $\widehat{\bm{\mathcal{T}}}_{l}$ is
$(2\mu_{1}\kappa_{0})^{2}$-incoherent. Therefore, from Lemma 13.7, we have:

$|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|^{2}\leq
C_{1,m}\bar{r}^{m}\underline{d}^{-(m-1)}(\mu_{1}\kappa_{0})^{4m}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}.$

So we have

$|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|\leq
C_{1,m}\sqrt{\frac{\bar{r}^{m}}{\underline{d}^{m-1}}}(\mu_{1}\kappa_{0})^{2m}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq
C_{1,m}\mu_{1}^{2m}\sqrt{\frac{\bar{r}^{m-1}}{\underline{d}^{m-1}}}\underline{\lambda},$

where the last inequality is from the upper bound of
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}$. As a
result, we have

$\big{|}[\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{T}}^{\ast}-\bm{\mathcal{S}}^{\ast}]_{\omega}\big{|}\leq\big{|}[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}]_{\omega}\big{|}+|[\widehat{\bm{\mathcal{S}}}_{l}]_{\omega}|+|[\bm{\mathcal{S}}^{\ast}]_{\omega}|\leq
C_{1,m}\mu_{1}^{2m}\sqrt{\frac{\bar{r}^{m-1}}{\underline{d}^{m-1}}}\underline{\lambda}+\textsf{k}_{\textsf{pr}}+\|\bm{\mathcal{S}}^{\ast}\|_{\ell_{\infty}}.$

Thus, both $\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l}$ and
$\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{\ast}$ belong to the ball
$\mathbb{B}_{\infty}^{*}$ and thus (12.2) holds.

As a result of (12.1) and (12.2), we get for any $\omega\in\Omega_{l}$

$b_{l}\big{|}[\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{\ast}]_{\omega}\big{|}\leq\big{|}[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{\ast})]_{\omega}\big{|}+\textsf{Err}_{\infty}.$

Therefore,

$\displaystyle\|{\cal P}_{\Omega_{l}}$
$\displaystyle(\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}\leq\frac{2}{b_{l}^{2}}\|{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))\|_{\rm
F}^{2}+\frac{2|\Omega_{l}|}{b_{l}^{2}}\textsf{Err}_{\infty}^{2}$
$\displaystyle=\frac{2}{b_{l}^{2}}\|{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))-{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))+{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\|_{\rm
F}^{2}+\frac{2|\Omega_{l}|}{b_{l}^{2}}\textsf{Err}_{\infty}^{2}$
$\displaystyle\leq\frac{4}{b_{l}^{2}}\|{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))-{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\|_{\rm
F}^{2}+\frac{4}{b_{l}^{2}}\|{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\|_{\rm
F}^{2}+\frac{2|\Omega_{l}|}{b_{l}^{2}}\textsf{Err}_{\infty}^{2}$
$\displaystyle\leq\frac{4b_{u}^{2}}{b_{l}^{2}}\|{\cal
P}_{\Omega_{l}}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*})\|_{\rm
F}^{2}+\frac{6|\Omega_{l}|}{b_{l}^{2}}\textsf{Err}_{\infty}^{2},$ (12.3)

where the last inequality is due to $\|{\cal
P}_{\Omega_{l}}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\|_{\rm
F}^{2}\leq|\Omega_{l}|\textsf{Err}_{\infty}^{2}$ and Assumption 3 since
$\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{\ast}\in\mathbb{B}_{\infty}^{*}$.

From (12.1), Lemma 13.8, we have

$\displaystyle\|{\cal
P}_{\Omega_{l}}(\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}$
$\displaystyle\leq\frac{C_{2,m}b_{u}^{2}}{b_{l}^{2}}(\mu_{1}\kappa_{0})^{4m}\bar{r}^{m}\alpha\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{6|\Omega_{l}|}{b_{l}^{2}}\textsf{Err}_{\infty}^{2}$ (12.4)

here $C_{2,m}>0$ is an absolute constant depending only on $m$.

For
$\forall\omega=(\omega_{1},\ldots,\omega_{m})\in\Omega^{*}\backslash\Omega_{l}$,
we have
$|[\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}]_{\omega}|=|[\bm{\mathcal{S}}^{*}]_{\omega}|$.
Since the loss function is entry-wise by Assumption 3, we have
$[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}=[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l})]_{\omega}$.
Clearly, $\widehat{\bm{\mathcal{T}}}_{l}$ and
$\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{\ast}$ both belong to
$\mathbb{B}_{\infty}^{*}$, by Assumption 3 we get

$|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}-[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*})]_{\omega}|\geq
b_{l}|[\bm{\mathcal{S}}^{*}]_{\omega}|.$

Now we bound
$|[\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}]_{\omega}|$ as follows.
For any $\omega\in\Omega^{\ast}\backslash\Omega_{l}$,

$\displaystyle|[\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}]_{\omega}|$
$\displaystyle=|[\bm{\mathcal{S}}^{*}]_{\omega}|\leq\frac{1}{b_{l}}|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}-[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*})]_{\omega}|$
$\displaystyle\leq\frac{1}{b_{l}}\left(|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}|+|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*})]_{\omega}|\right)$
$\displaystyle\leq\frac{1}{b_{l}}\left(|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}|+|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*})-\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*})]_{\omega}|+|[\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*})]_{\omega}|\right)$
$\displaystyle\leq\frac{1}{b_{l}}|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}|+\frac{b_{u}}{b_{l}}|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|+\frac{1}{b_{l}}\textsf{Err}_{\infty},$

where the last inequality is again due to Assumption 3 since
$\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}\in\mathbb{B}_{\infty}^{*}$.
Therefore we have

$\displaystyle\|{\cal
P}_{\Omega^{*}\backslash\Omega_{l}}(\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}\leq\frac{2}{b_{l}^{2}}\|{\cal
P}_{\Omega^{*}\backslash\Omega_{l}}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}))\|_{\rm
F}^{2}+\frac{4b_{u}^{2}}{b_{l}^{2}}\|{\cal
P}_{\Omega^{*}\backslash\Omega_{l}}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*})\|_{\rm
F}^{2}+\frac{4}{b_{l}^{2}}|\Omega^{\ast}\backslash\Omega_{l}|\textsf{Err}_{\infty}^{2}$
(12.5)

Since $\omega\in\Omega^{*}\backslash\Omega_{l}$, we have

$\displaystyle|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}|\leq\max\nolimits_{i=1}^{m}|\mathbf{e}_{\omega_{i}}^{\top}\mathcal{M}_{i}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}))|^{(\gamma\alpha
d_{i}^{-})}$ (12.6)

Now since we have $\bm{\mathcal{S}}^{*}\in\SS_{\alpha}$, we have

$\displaystyle|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}|$
$\displaystyle\leq\max\nolimits_{i=1}^{m}|\mathbf{e}_{\omega_{i}}^{T}\mathcal{M}_{i}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))|^{\left((\gamma-1)\alpha
d_{i}^{-}\right)}$
$\displaystyle\leq\max\nolimits_{i=1}^{m}\Big{|}\mathbf{e}_{\omega_{i}}^{\top}\left(\mathcal{M}_{i}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))-\mathcal{M}_{i}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\right)\Big{|}^{\left((\gamma-1)\alpha
d_{i}^{-}\right)}+\textsf{Err}_{\infty}$ (12.7)

Using AM-GM inequality, we have:

$\displaystyle|[\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l})]_{\omega}|^{2}$
$\displaystyle\leq
2\max\nolimits_{i=1}^{m}\frac{\Big{\|}\mathbf{e}_{\omega_{i}}^{\top}\left(\mathcal{M}_{i}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))-\mathcal{M}_{i}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\right)\Big{\|}_{\rm
F}^{2}}{(\gamma-1)\alpha d_{i}^{-}}+2\textsf{Err}_{\infty}^{2}$
$\displaystyle\leq
2\sum_{i=1}^{m}\frac{\Big{\|}\mathbf{e}_{\omega_{i}}^{\top}\left(\mathcal{M}_{i}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*}))-\mathcal{M}_{i}(\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}))\right)\Big{\|}_{\rm
F}^{2}}{(\gamma-1)\alpha d_{i}^{-}}+2\textsf{Err}_{\infty}^{2}$ (12.8)

Now for all fixed $i\in[m]$, for all $\omega_{i}\in[d_{i}]$, $\omega_{i}$
appears at most $\alpha d_{i}^{-}$ times since
$\Omega^{*}\backslash\Omega_{l}$ is an $\alpha$-fraction set. This observation
together with (12.1) lead to the following:

$\displaystyle\|{\cal
P}_{\Omega^{*}\backslash\Omega_{l}}(\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}))\|_{\rm
F}^{2}$ $\displaystyle\leq
2\sum_{i=1}^{m}\frac{\|\nabla\mathfrak{L}(\widehat{\bm{\mathcal{T}}}_{l}+\bm{\mathcal{S}}^{*})-\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}}{\gamma-1}+2|\Omega^{*}\backslash\Omega_{l}|\textsf{Err}_{\infty}^{2}$
$\displaystyle\leq\frac{2mb_{u}^{2}}{\gamma-1}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+2|\Omega^{*}\backslash\Omega_{l}|\textsf{Err}_{\infty}^{2}.$ (12.9)

Therefore together with (12.5) and (12.1) and Lemma 13.8, we have

$\displaystyle\|{\cal
P}_{\Omega^{*}\backslash\Omega_{l}}(\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}$
$\displaystyle\leq\left(\frac{4mb_{u}^{2}}{b_{l}^{2}}\frac{1}{\gamma-1}+C_{4,m}\frac{b_{u}^{2}}{b_{l}^{2}}(\mu_{1}\kappa_{0})^{4m}\bar{r}^{m}\alpha\right)\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{16}{b_{l}^{2}}|\Omega^{*}\backslash\Omega_{l}|\textsf{Err}_{\infty}^{2}$
(12.10)

where $C_{4,m}>0$ are constants depending only on $m$. Now we combine (12.4)
and (12.10) and we get

$\displaystyle\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}$
$\displaystyle\leq\left(\frac{4mb_{u}^{2}}{b_{l}^{2}}\frac{1}{\gamma-1}+C_{5,m}(\mu_{1}\kappa_{0})^{4m}\bar{r}^{m}\frac{b_{u}^{2}}{b_{l}^{2}}\alpha\right)\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{C_{1}}{b_{l}^{2}}|\Omega^{\ast}\cup\Omega_{l}|\textsf{Err}_{\infty}^{2}$
(12.11)

where $C_{5,m}>0$ depending only on $m$ and $C_{1}>0$ an absolute constant.

Now if we choose
$\alpha\leq(C_{5,m}\kappa_{0}^{4m}\mu_{0}^{4m}\bar{r}^{m}\frac{b_{u}^{4}}{b_{l}^{4}})^{-1}$
and $\gamma-1\geq 4m\frac{b_{u}^{4}}{b_{l}^{4}}$ for some sufficient large
constants $C_{5,m}>0$ depending only on $m$, then we have

$\displaystyle\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}\leq\frac{b_{l}^{2}}{b_{u}^{2}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{C_{1}}{b_{l}^{2}}|\Omega^{*}\cup\Omega_{l}|\textsf{Err}_{\infty}^{2}$
(12.12)

and

$\displaystyle\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}\leq\frac{b_{l}}{b_{u}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+\frac{C_{1}}{b_{l}}\sqrt{|\Omega^{*}\cup\Omega_{l}|}\textsf{Err}_{\infty}$
(12.13)

In addition, from the upper bound of
$\|\bm{\mathcal{T}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm F}$, (12.13) implies
that $\|\widehat{\bm{\mathcal{S}}}_{l}-\bm{\mathcal{S}}^{\ast}\|_{\rm F}\leq
c_{0}\underline{\lambda}$ for a small $c_{0}>0$. This fact is helpful later
since it implies that
$\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l}$ belongs to the
ball $\mathbb{B}_{2}^{*}$ and thus activates the conditions in Assumption 2.

#### Step 2: bounding
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{\ast}\|_{\rm F}^{2}$ for
all $l\geq 1$.

From previous step, we have verified

$\displaystyle\|\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{\ast}\|_{\rm
F}\leq\frac{b_{l}}{b_{u}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+\frac{C_{1}}{b_{l}}\sqrt{|\Omega^{*}\cup\Omega_{l}|}\textsf{Err}_{\infty}\leq
c_{0}\underline{\lambda}.$ (12.14)

And from the Algorithm 2,
$\widehat{\bm{\mathcal{T}}}_{l}=\textsf{Trim}_{\zeta_{l},\mathbf{r}}(\bm{\mathcal{W}}_{l-1})$.
Now from Lemma 13.6, we get,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-$
$\displaystyle\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}=\|\textsf{Trim}_{\zeta_{l},\mathbf{r}}(\bm{\mathcal{W}}_{l-1})-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}$ $\displaystyle\leq\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+C_{m}\frac{\sqrt{\bar{r}}}{\underline{\lambda}}\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{3}$
$\displaystyle\leq(1+\frac{\delta}{4})\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}$
$\displaystyle\leq(1-\delta^{2})\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+6\delta^{-1}\textsf{Err}_{2\mathbf{r}}+C_{1}\left(1+b_{u}+b_{u}^{2}\right)b_{l}^{-2}\left(|\Omega^{*}|+\gamma\alpha
d^{*}\right)\textsf{Err}_{\infty}^{2}$ (12.15)

Notice to use Lemma 13.6, we need to verify
$\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\underline{\lambda}/8$, which we will check momentarily. Also, from
(12.1) and the signal-to-noise ration condition, we get

$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
c_{1}\min\\{\delta^{2}\bar{r}^{-1/2},\kappa_{0}^{-2m}\bar{r}^{-1/2}\\}\cdot\underline{\lambda}.$

On the other hand, from lemma 13.6, we have $\widehat{\bm{\mathcal{T}}}_{l}$
is $(2\mu_{1}\kappa_{0})^{2}$-incoherent. Further, from Lemma 13.7 and the
definition of $\textsf{k}_{\infty}$ we have
$\widehat{\bm{\mathcal{T}}}_{l}\in\mathbb{B}_{\infty}^{\ast}$. This finishes
the induction for the error
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}$. Now the
only thing we need to check is the upper bound for
$\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm F}$.

#### Step 2.1: bounding $\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}$.

From the Algorithm 2, we have for arbitrary $1\geq\delta>0$,

$\displaystyle\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm F}^{2}$
$\displaystyle=\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})-\beta\mathcal{P}_{\mathbb{T}_{l-1}}\bm{\mathcal{G}}^{*}\|_{\rm
F}^{2}$
$\displaystyle\leq(1+\frac{\delta}{2})\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}+(1+\frac{2}{\delta})\beta^{2}\|\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$ (12.16)

Now we consider the bound for
$\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$
$\displaystyle=\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}-2\beta\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle$
$\displaystyle~{}~{}~{}~{}+\beta^{2}\|\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$ (12.17)

The upper bound of
$\|\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{\ast}\|_{\rm F}$ ensures
that
$\widehat{\bm{\mathcal{T}}}_{l-1}+\widehat{\bm{\mathcal{S}}}_{l-1}\in\mathbb{B}_{2}^{*}$.
Using the smoothness condition in Assumption 2, we get

$\displaystyle\beta^{2}\|\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}\leq\beta^{2}b_{u}^{2}\|\widehat{\bm{\mathcal{T}}}_{l-1}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{T}}^{*}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}$ (12.18)

Now we consider the bound for
$|\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle|$.
First we have:

$\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle=\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle-\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}^{\perp}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle.$

The estimation of
$\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle$
is as follows:

$\displaystyle\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle$
$\displaystyle=\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle-\langle\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle$
$\displaystyle\geq
b_{l}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}-\langle\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle,$
(12.19)

where the last inequality follows from Assumption 2. And the estimation of
$\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}^{\perp}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle$
is as follows:

$\displaystyle|\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}^{\perp}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle|$
$\displaystyle\leq\|\mathcal{P}_{\mathbb{T}_{l-1}}^{\perp}(\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*})\|_{\rm
F}\|\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\|_{\rm F}$
$\displaystyle\leq\frac{C_{1,m}b_{u}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}$ (12.20)

where the last inequality follows from Lemma 13.1. Together with (12.1) and
(12.1), we get,

$\displaystyle\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\rangle$
$\displaystyle\geq
b_{l}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}-\langle\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle$
$\displaystyle~{}~{}~{}~{}-\frac{C_{1,m}b_{u}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}$ (12.21)

Together with (12.18) and (12.1), we get

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$ $\displaystyle\leq\left(1+2\beta
b_{u}\frac{C_{1,m}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}\right)\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}$ $\displaystyle~{}~{}~{}~{}+(\beta^{2}b_{u}^{2}-2\beta
b_{l})\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}$
$\displaystyle~{}~{}~{}~{}+2\beta|\langle\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*},\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\rangle|$
(12.22)

In order to bound (12.1), we derive separately the bound for each terms.

#### Bounding
$\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}$.

From the bound for
$\|\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm F}$ in
(12.14), we get,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}$ $\displaystyle\leq
2\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+2\|\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm F}^{2}$
$\displaystyle\leq
4\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{C_{1}}{b_{l}^{2}}|\Omega^{*}\cup\Omega_{l-1}|\textsf{Err}_{\infty}^{2}$
(12.23)

Thus,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}\leq 2\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+\frac{C_{1}}{b_{l}}\sqrt{|\Omega^{*}\cup\Omega_{l-1}|}\textsf{Err}_{\infty}$
(12.24)

#### Bounding
$|\langle\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*},\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\rangle|$.

We first bound $\|\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\|_{\rm F}$ by
(12.24):

$\displaystyle\|\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\|_{\rm F}$
$\displaystyle\leq
b_{u}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}+\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm
F}$ $\displaystyle\leq
2b_{u}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+\frac{C_{1}b_{u}}{b_{l}}\sqrt{|\Omega^{*}\cup\Omega_{l-1}|}\textsf{Err}_{\infty}$
(12.25)

Now we estimate
$|\langle\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*},\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\rangle|$
from (12.14) and (12.1) as follows,

$\displaystyle~{}~{}~{}~{}|\langle\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*},\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\rangle|\leq\|\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*}\|_{\rm
F}\|\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm F}$
$\displaystyle\leq(0.02b_{l}+0.01\beta
b_{u}^{2})\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{1}{\beta}\frac{C_{1}}{b_{l}^{2}}|\Omega^{*}\cup\Omega_{l-1}|\textsf{Err}_{\infty}^{2}+\frac{C_{1}b_{u}}{b_{l}^{2}}|\Omega^{*}\cup\Omega_{l-1}|\textsf{Err}_{\infty}^{2}$
(12.26)

#### Bounding
$|\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\rangle|$.

From (12.14), we have

$\displaystyle|\langle\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*},\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\rangle|$
$\displaystyle\leq\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\|\widehat{\bm{\mathcal{S}}}_{l-1}-\bm{\mathcal{S}}^{*}\|_{\rm F}$
$\displaystyle\leq(0.01\frac{b_{l}}{b_{u}}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+\frac{C_{1}}{b_{l}}\sqrt{|\Omega^{*}\cup\Omega_{l-1}|}\textsf{Err}_{\infty})\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}$ $\displaystyle\leq
0.02\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{C_{1}}{b_{l}^{2}}|\Omega^{*}\cup\Omega_{l-1}|\textsf{Err}_{\infty}^{2}$
(12.27)

Now we go back to (12.1) and from (12.1) - (12.1), we get:

$\displaystyle~{}~{}~{}~{}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$ $\displaystyle\leq\left(1-1.84\beta
b_{l}+5\beta^{2}b_{u}^{2}\right)\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+C_{1}(1+b_{u}+b_{u}^{2})b_{l}^{-2}|\Omega^{*}\cup\Omega_{l-1}|\textsf{Err}_{\infty}^{2}$
(12.28)

where the condition $\underline{\lambda}\geq
C_{1,m}\frac{b_{u}}{b_{l}}\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}$ is used in the last step.

By combining (12.1) and (12.1), we get

$\displaystyle\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm F}^{2}$
$\displaystyle=\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}\bm{\mathcal{G}}_{l-1}\|_{\rm
F}^{2}$
$\displaystyle\leq(1+\frac{\delta}{2})\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}_{l-1}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}+(1+\frac{2}{\delta})\beta^{2}\|\mathcal{P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$ $\displaystyle\leq(1+\frac{\delta}{2})\left(1-1.84\beta
b_{l}+5\beta^{2}b_{u}^{2}\right)\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+(1+\frac{2}{\delta})\beta^{2}\textsf{Err}_{2\mathbf{r}}^{2}$
$\displaystyle~{}~{}~{}~{}+C_{1}\left(1+\beta
b_{u}+\beta^{2}b_{u}^{2}\right)b_{u}^{-2}|\Omega^{*}\cup\Omega_{l-1}|\textsf{Err}_{\infty}^{2}$
$\displaystyle\leq(1+\frac{\delta}{2})\left(1-1.84\beta
b_{l}+5\beta^{2}b_{u}^{2}\right)\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+(1+\frac{2}{\delta})\beta^{2}\textsf{Err}_{2\mathbf{r}}^{2}$
$\displaystyle~{}~{}~{}~{}+C_{1}\left(1+\beta
b_{u}+\beta^{2}b_{u}^{2}\right)\frac{1}{b_{u}^{2}}\left(|\Omega^{*}|+\gamma\alpha
d^{*}\right)\textsf{Err}_{\infty}^{2}$ (12.29)

where in the second inequality we used

$\displaystyle\|{\cal P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}^{*})\|_{\rm
F}=\sup_{\|\bm{\mathcal{Y}}\|_{\rm F}=1}\langle{\cal
P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{G}}^{*}),\bm{\mathcal{Y}}\rangle=\sup_{\|\bm{\mathcal{Y}}\|_{\rm
F}=1}\langle\bm{\mathcal{G}}^{*},{\cal
P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{Y}})\rangle\leq\textsf{Err}_{2\mathbf{r}}$
(12.30)

since ${\cal
P}_{\mathbb{T}_{l-1}}(\bm{\mathcal{Y}})\in\mathbb{M}_{2\mathbf{r}}$ and in the
last inequality we use
$|\Omega^{*}\cup\Omega_{l-1}|\leq|\Omega^{*}|+|\Omega_{l-1}|\leq|\Omega^{*}|+\gamma\alpha
d^{*}$.

Now we choose proper $\beta\in[0.005b_{l}/(b_{u}^{2}),0.36b_{l}/(b_{u}^{2})]$
so $1-1.84\beta b_{l}+5\beta^{2}b_{u}^{2}\leq 1-\delta$, and we get

$\displaystyle\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm F}$
$\displaystyle\leq(1-\delta)(1+\delta/2)\|\widehat{\bm{\mathcal{T}}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+3\delta^{-1}\textsf{Err}_{2\mathbf{r}}+C_{1}(b_{u}+1)b_{l}^{-1}\sqrt{|\Omega^{*}|+\alpha\gamma
d^{*}}\textsf{Err}_{\infty}$ (12.31)

where we use the fact that $\beta\leq 1$. From the signal-to-noise ratio
condition, we have
$3\delta^{-1}\textsf{Err}_{2\mathbf{r}}+C_{1}(b_{u}+1)b_{l}^{-1}\sqrt{|\Omega^{*}|+\alpha\gamma
d^{*}}\textsf{Err}_{\infty}\leq\frac{\delta}{4}\frac{\underline{\lambda}}{C_{m}\sqrt{\bar{r}}}$.
This implies that $\|\bm{\mathcal{W}}_{l-1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\underline{\lambda}/8$ holds.

###  12.2 Proof of Theorem 4.3

Let $\widehat{\Omega}$ and $\Omega^{\ast}$ denote the support of
$\widehat{\bm{\mathcal{S}}}_{l_{\max}}$ and $\bm{\mathcal{S}}^{\ast}$,
respectively. By the proof of Theorem 4.1, we have

$\displaystyle\big{|}[\widehat{\bm{\mathcal{S}}}_{l_{\max}}-\bm{\mathcal{S}}^{\ast}]_{\omega}\big{|}\leq\begin{cases}\frac{b_{u}}{b_{l}}\big{|}[\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{\ast}]_{\omega}\big{|}+\frac{2\textsf{Err}_{\infty}}{b_{l}}&,\textrm{
if }\omega\in\widehat{\Omega}\\\
\frac{2b_{u}}{b_{l}}\|\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{*}\|_{\ell_{\infty}}+\frac{2\textsf{Err}_{\infty}}{b_{l}}&,\textrm{
if }\omega\in\Omega^{\ast}\setminus\widehat{\Omega}\end{cases}$

Therefore, we conclude that

$\displaystyle\|\widehat{\bm{\mathcal{S}}}_{l_{\max}}-\bm{\mathcal{S}}^{\ast}\|_{\ell_{\infty}}\leq\frac{2b_{u}}{b_{l}}\big{\|}\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{\ast}\big{\|}_{\ell_{\infty}}+\frac{2\textsf{Err}_{\infty}}{b_{l}}.$
(12.32)

Now, we can apply Lemma 13.7 and we obtain

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{\ast}\|_{\ell_{\infty}}\leq
C_{1,m}\bar{r}^{m/2}\underline{d}^{-(m-1)/2}\mu_{1}^{2m}\kappa_{0}^{2m}\|\widehat{\bm{\mathcal{T}}}_{l_{\max}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}$ (12.33)

Now, by putting together (12.32), (12.33) and (4.8), we get

$\|\widehat{\bm{\mathcal{S}}}_{l_{\max}}-\bm{\mathcal{S}}^{\ast}\|_{\ell_{\infty}}\leq
C_{2,m}\kappa_{0}^{2m}\mu_{1}^{2m}\Big{(}\frac{\bar{r}^{m}}{\underline{d}^{m-1}}\Big{)}^{1/2}\cdot\big{(}\textsf{Err}_{2\mathbf{r}}+(|\Omega^{\ast}|+\gamma\alpha
d^{\ast})^{1/2}\textsf{Err}_{\infty}\big{)}+\frac{2\textsf{Err}_{\infty}}{b_{l}},$

where $C_{1,m}$ and $C_{2,m}$ are constants depending only on $m$. Now since
we assume $b_{l},b_{u}=O(1)$, we finish the proof of Theorem 4.3.

###  12.3 Proof of Theorem 5.1

We first estimate the probability of the following two events.

$\displaystyle\textsf{Err}_{2\mathbf{r}}$ $\displaystyle\leq
C_{0,m}\sigma_{z}\cdot(\bar{d}\bar{r}+r^{\ast})^{1/2}$ (12.34)
$\displaystyle\textsf{Err}_{\infty}$ $\displaystyle\leq
C_{0,m}^{\prime}\sigma_{z}\log^{1/2}\bar{d}$ (12.35)

for some constants $C_{0,m},C_{0,m}^{\prime}>0$ depending only on $m$. Notice
here the first event (12.34) holds with probability at least
$1-\exp(-c_{m}\bar{r}\bar{d})$ by Lemma 13.3. And for the second event
(12.35), we have from the definition,

$\displaystyle\textsf{Err}_{\infty}=\max\Big{\\{}\|\nabla\mathfrak{L}(\bm{\mathcal{T}}^{\ast}+\bm{\mathcal{S}}^{\ast})\|_{\ell_{\infty}},\min\nolimits_{\|\bm{\mathcal{X}}\|_{\ell_{\infty}}\leq\infty}\|\nabla\mathfrak{L}(\bm{\mathcal{X}})\|_{\ell_{\infty}}\Big{\\}}=\|\bm{\mathcal{Z}}\|_{\ell_{\infty}}$
(12.36)

So we have (12.35) holds with probability at least $1-0.5\bar{d}^{-2}$ from
Lemma 13.4. Taking union bounds and we get both (12.35) and (12.34) hold with
probability at least $1-\bar{d}^{-2}$. And finally applying Theorem 4.1 and
Theorem 4.3 gives the desired result.

###  12.4 Proof of Lemma 5.2

Denote the event ${\cal E}_{1}=\\{\|\bm{\mathcal{Z}}\|_{\ell_{\infty}}\leq
2\sqrt{m}\sigma_{z}\sqrt{\log(\bar{d})}\\}$, then from Lemma 13.4, we have
${\cal E}_{1}$ holds with probability at least $1-2(d^{*})^{-1}$. Now we set
$\tau_{l}=2\sqrt{m}\sigma_{z}\sqrt{\log(\bar{d})}+(d^{*})^{-1/2}\mu_{1}\|\bm{\mathcal{T}}^{*}\|_{\rm
F}$, then under ${\cal E}_{1}$, we have
$\|\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}\|_{\ell_{\infty}}\leq\tau_{l}$. From
the definition of $\tau_{0}$, we have
$|\tau_{0}|\leq|\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}|^{(\lfloor
pd^{*}-|\Omega^{*}|\rfloor)}\leq\tau_{l}$. Denote
$\Omega_{1}=\\{\omega:|[\bm{\mathcal{A}}]_{\omega}|\leq\tau_{0}\\}$ From the
definition of $\bm{\mathcal{A}}_{0}$, we have

$\displaystyle\|\bm{\mathcal{A}}_{0}\|_{\rm F}^{2}$
$\displaystyle=\sum_{\omega\in\Omega_{1}}[\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}+\bm{\mathcal{Z}}]_{\omega}^{2}$
$\displaystyle\geq\sum_{\omega\in\Omega_{1}}[\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}]_{\omega}^{2}+2\sum_{\omega\in\Omega_{1}\cap\Omega^{*}}[\bm{\mathcal{S}}^{*}]_{\omega}[\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}]_{\omega}$
$\displaystyle\geq\sum_{\omega\in\Omega_{1}}[\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}]_{\omega}^{2}-4|\Omega^{*}|\tau_{l}^{2}$
$\displaystyle=\|\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}\|_{\rm
F}^{2}-\sum_{\omega\in\Omega_{1}^{c}}[\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}]_{\omega}^{2}-4|\Omega^{*}|\tau_{l}^{2}$
$\displaystyle\geq\|\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}\|_{\rm
F}^{2}-(pd^{*}+4|\Omega^{*}|)\tau_{l}^{2},$ (12.37)

where the penultimate inequality holds since for all $\omega$,
$|[\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}]_{\omega}|\leq\tau_{l}$ and for all
$\omega\in\Omega_{1}$, we have
$|[\bm{\mathcal{S}}^{*}]_{\omega}|\leq|[\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}]_{\omega}|+\tau_{0}\leq
2\tau_{l}$. Now we estimate the lower bound for
$\|\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}\|_{\rm F}^{2}$. Since
$\bm{\mathcal{Z}}$ has i.i.d. subgaussian entries, we have
$\|\bm{\mathcal{Z}}\|_{\rm F}^{2}\geq\frac{1}{2}d^{*}\sigma_{z}^{2}$ with
probability at least $1-2\exp(-cd^{*})$ for some absolute constant $c>0$, and
$2\langle\bm{\mathcal{T}}^{*},\bm{\mathcal{Z}}\rangle\leq\frac{1}{2}\|\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+2\sigma_{z}^{2}\log(\bar{d})$ with probability at least
$1-2(d^{*})^{-1}$. Put these altogether, we see

$\displaystyle\|\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}\|_{\rm
F}^{2}=\|\bm{\mathcal{T}}^{*}\|_{\rm F}^{2}+\|\bm{\mathcal{Z}}\|_{\rm
F}^{2}+2\langle\bm{\mathcal{T}}^{*},\bm{\mathcal{Z}}\rangle\geq\frac{1}{2}\|\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{1}{4}\sigma_{z}^{2}d^{*}.$ (12.38)

Combine (12.4) and (12.38), we have

$\displaystyle\|\bm{\mathcal{A}}_{0}\|_{\rm
F}^{2}\geq\frac{1}{2}\|\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{1}{4}\sigma_{z}^{2}d^{*}-(pd^{*}+4|\Omega^{*}|)\tau_{l}^{2}.$
(12.39)

Therefore with the choice
$\tau=10\sqrt{m}\sqrt{\log(\bar{d})}\mu_{1}\frac{\|\bm{\mathcal{A}}_{0}\|_{\rm
F}}{\sqrt{d^{*}}}$, we see that $\tau\geq\tau_{l}$ and
$\tau_{u}:=10\sqrt{m}\sqrt{\log(\bar{d})}\mu_{1}\tau_{l}\geq\tau$. With such a
choice of $\tau$, since for $\omega\in(\Omega^{*})^{c}$, we have
$|[\bm{\mathcal{T}}^{*}]_{\omega}+[\bm{\mathcal{Z}}]_{\omega}|\leq\tau_{l}\leq\tau$,
so we obtain

$\displaystyle\widetilde{\bm{\mathcal{A}}}$ $\displaystyle={\cal
P}_{(\Omega^{*})^{c}}(\bm{\mathcal{A}})+{\cal
P}_{\Omega^{*}}(\widetilde{\bm{\mathcal{A}}})={\cal
P}_{(\Omega^{*})^{c}}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}})+{\cal
P}_{\Omega^{*}}(\textsf{Trunc}_{\tau}(\bm{\mathcal{A}}))$
$\displaystyle=\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}+{\cal
P}_{\Omega^{*}}(\textsf{Trunc}_{\tau}(\bm{\mathcal{A}})-\bm{\mathcal{T}}^{*}-\bm{\mathcal{Z}})$
$\displaystyle=:\bm{\mathcal{T}}^{*}+\bm{\mathcal{Z}}+\mathbb{E},$

where $\bm{\mathcal{E}}={\cal
P}_{\Omega^{*}}(\textsf{Trunc}_{\tau}(\bm{\mathcal{A}})-\bm{\mathcal{T}}^{*}-\bm{\mathcal{Z}})$
and the first equality holds since for $\omega\in(\Omega^{*})^{c}$,
$|[\bm{\mathcal{A}}]_{\omega}|\leq|[\bm{\mathcal{T}}^{*}]|_{\omega}+|[\bm{\mathcal{Z}}_{\omega}]|\leq\tau_{u}$.
Under event ${\cal E}_{1}$, we have $\|\bm{\mathcal{E}}\|_{\rm F}\leq
2|\Omega^{*}|^{1/2}\tau_{u}$.

Now we use bold-face capital letters as shorthand notation for the unfolding
of corresponding calligraphic-font bold-face letters, for example,
$\mathbf{T}_{i}^{*}=\mathcal{M}_{i}(\bm{\mathcal{T}}^{*}),i\in[m]$. We denote
$\bm{\mathcal{X}}=\bm{\mathcal{T}}^{*}+\bm{\mathcal{E}}$. We also denote
$\mathbf{U}_{i}^{*}$ be the top $r_{i}$ left singular vectors of
$\mathbf{T}_{i}^{*}$, $\mathbf{V}_{i}$ be the top $r_{i}$ left singular
vectors of $\mathbf{X}_{i}$ and $\widehat{}\mathbf{U}_{i}^{0}$ be the top
$r_{i}$ left singular vectors of $\widetilde{}\mathbf{A}_{i}$.

From Wedin’s sin$\Theta$ theorem, we have from condition $(a)$,

$\displaystyle
d_{c}(\mathbf{U}_{i}^{*},\mathbf{V}_{i})\leq\frac{C|\Omega^{*}|^{1/2}\tau_{u}}{\underline{\lambda}},$
(12.40)

where
$d_{c}(\mathbf{U},\mathbf{V})=\min_{\mathbf{R}\in\mathbb{O}_{r}}\|\mathbf{U}\mathbf{R}-\mathbf{V}\|$.
Meanwhile, from $\|\mathbf{X}_{i}-\mathbf{T}_{i}^{*}\|_{\rm
F}=\|\bm{\mathcal{E}}\|_{\rm F}\leq|\Omega^{*}|^{1/2}\tau_{u}$, we also have
$\sigma_{r_{i}}(\mathbf{X}_{i})\geq\frac{3\underline{\lambda}}{4}$,
$\sigma_{r_{i}+1}(\mathbf{X}_{i})\leq\frac{\underline{\lambda}}{4}$ and
$\|\mathbf{X}_{i}\|\leq\frac{5\bar{\lambda}}{4}$.

Since subtracting a multiple of identity matrix does not change the top
eigenvectors, in order to bound the distance
$d_{c}(\mathbf{V}_{i},\widehat{}\mathbf{U}_{i}^{0})$, we consider
$\|\widetilde{}\mathbf{A}_{i}\widetilde{}\mathbf{A}_{i}^{T}-\mathbf{X}_{i}\mathbf{X}_{i}^{T}-\sigma_{v}^{2}d_{i}^{-}\mathbf{I}_{d_{i}}\|$,
where $\sigma_{v}^{2}$ is the variance of the entry of $\bm{\mathcal{Z}}$ and
$d_{i}^{-}=d^{*}/d_{i}$. In fact, we have

$\widetilde{}\mathbf{A}_{i}\widetilde{}\mathbf{A}_{i}^{T}-\mathbf{X}_{i}\mathbf{X}_{i}^{T}-\sigma_{v}^{2}d_{i}^{-}\mathbf{I}_{d_{i}}=\mathbf{X}_{i}\mathbf{Z}_{i}^{T}+\mathbf{Z}_{i}\mathbf{X}_{i}^{T}+\mathbf{Z}_{i}\mathbf{Z}_{i}^{T}-\sigma_{v}^{2}d_{i}^{-}\mathbf{I}_{d_{i}}.$

Now we first consider the operator norm of $\mathbf{X}_{i}\mathbf{Z}_{i}^{T}$
under the event ${\cal E}_{1}$. From Talagrand’s concentration inequality, we
have

$\mathbb{P}\bigg{(}\big{|}\|\mathbf{X}_{i}\mathbf{Z}_{i}^{T}\|-\mathbb{E}\|\mathbf{X}_{i}\mathbf{Z}_{i}^{T}\|\big{|}\leq
C_{m}\sqrt{\log(\bar{d})}\sigma_{z}\|\mathbf{X}_{i}\|\cdot t\bigg{|}{\cal
E}_{1}\bigg{)}\geq 1-2\exp(-ct^{2}).$

Since $\mathbb{P}({\cal E}_{1})\geq 1/2$ and from [Vershynin, 2011, Theorem
1.1], we have $\mathbb{E}[\|\mathbf{X}_{i}\mathbf{Z}_{i}^{T}\||{\cal
E}_{1}]\leq 2\mathbb{E}\|\mathbf{X}_{i}\mathbf{Z}_{i}^{T}\|\leq
C\sqrt{d_{i}}\sigma_{z}\|\mathbf{X}_{i}\|$. Therefore setting
$t=\sqrt{\log(\bar{d})}$ and the event

${\cal E}_{2}^{i}=\\{\|\mathbf{X}_{i}\mathbf{Z}_{i}^{T}\|\leq
C_{m}\sqrt{d_{i}}\|\mathbf{X}_{i}\|\sigma_{z}\\},\quad{\cal
E}_{2}=\cap_{i=1}^{m}{\cal E}_{2}^{i},$

we know that $\mathbb{P}({\cal E}_{2}|{\cal E}_{1})\geq 1-2m\bar{d}^{-1}$ and
thus $\mathbb{P}({\cal E}_{2})\geq(1-2m\bar{d}^{-1})(1-2(d^{*})^{-1})$.

Now we turn to bounding
$\|\mathbf{Z}_{i}\mathbf{Z}_{i}^{T}-d_{i}^{-}\sigma_{z}^{2}\mathbf{I}_{d_{i}}\|$.
From [Vershynin, 2018, Theorem 4.6.1], we have with probability exceeding
$1-2\exp(-d_{i})$,

$\displaystyle\|\mathbf{Z}_{i}\mathbf{Z}_{i}^{T}-d_{i}^{-}\sigma_{z}^{2}\mathbf{I}_{d_{i}}\|\leq
C(d^{*})^{1/2}\sigma_{z}^{2}.$

Denote the event ${\cal
E}_{3}^{i}=\\{\|\mathbf{Z}_{i}\mathbf{Z}_{i}^{T}-d_{i}^{-}\sigma_{v}^{2}\mathbf{I}_{d_{i}}\|\leq
C(d^{*})^{1/2}\sigma_{z}^{2}\\}$ and ${\cal E}_{3}=\cap_{i=1}^{m}{\cal
E}_{3}^{i}$ and we have $\mathbb{P}({\cal E}_{3})\geq
1-2\sum_{i=1}^{m}\exp(-d_{i})$. Therefore under the event ${\cal E}_{2},{\cal
E}_{3}$, and from condition $(b)$, we have

$d_{c}(\mathbf{V}_{i},\widehat{}\mathbf{U}_{i}^{0})\leq\frac{C_{m}\sqrt{\bar{d}}\sigma_{z}\bar{\lambda}+C(d^{*})^{1/2}\sigma_{z}^{2}}{\underline{\lambda}^{2}}.$

Together with (12.40), we have

$\displaystyle
d_{c}(\mathbf{U}_{i}^{*},\widehat{}\mathbf{U}_{i}^{0})\leq\frac{C_{m}\sqrt{\bar{d}}\sigma_{z}\bar{\lambda}+C(d^{*})^{1/2}\sigma_{z}^{2}}{\underline{\lambda}^{2}}+\frac{C|\Omega^{*}|^{1/2}\tau_{u}}{\underline{\lambda}}.$
(12.41)

Denote the event

${\cal E}_{4}=\left\\{\max_{i=1}^{m}\max_{\|\mathbf{V}_{j}\|\leq 1,j\neq
i}\|\mathbf{Z}_{i}(\mathbf{V}_{i+1}\otimes\cdots\otimes\mathbf{V}_{m}\otimes\mathbf{V}_{1}\otimes\cdots\otimes\mathbf{V}_{i-1})\|\leq
C_{m}(\sqrt{\bar{d}\bar{r}}+\bar{r}^{\frac{m-1}{2}})\sigma_{z}\right\\}.$

And from [Zhang and Xia, 2018, Lemma 5], we have $\mathbb{P}({\cal E}_{4})\geq
1-Cm\exp(-c\bar{d})$. For the following we denote

$\displaystyle\mathbf{X}_{1}^{t}$
$\displaystyle=\mathbf{T}_{1}^{*}(\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t})=\mathbf{T}_{1}^{*}({\cal
P}_{\mathbf{U}_{2}^{*}}\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes{\cal
P}_{\mathbf{U}_{m}^{*}}\widehat{}\mathbf{U}_{m}^{t})$
$\displaystyle\mathbf{Z}_{1}^{t}$
$\displaystyle=\mathbf{Z}_{1}(\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t})$
$\displaystyle\widetilde{}\mathbf{A}_{1}^{t}$
$\displaystyle=\widetilde{}\mathbf{A}_{1}(\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t}),$

where ${\cal P}_{\mathbf{U}}=\mathbf{U}\mathbf{U}^{T}$. We shall denote
$L_{t}=\max_{i=1}^{m}d_{c}(\widehat{}\mathbf{U}_{i}^{t},\mathbf{U}_{i}^{*})$.
For the base case, from (12.41) and condition $(b)$, we see
$L_{0}\leq\frac{1}{2}$. Now suppose we have $L_{t}\leq\frac{1}{2}$.

From the process of HOOI, we have
$\widehat{}\mathbf{U}_{1}^{t+1}=\textrm{SVD}_{r_{1}}(\widetilde{}\mathbf{A}_{1}(\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t}))$.
And thus we obtain

$\displaystyle\sigma_{r_{1}}(\mathbf{X}_{1}^{t})$
$\displaystyle\geq\sigma_{r_{1}}(\mathbf{U}_{2}^{*}\otimes\cdots\otimes\mathbf{U}_{m}^{*})\cdot\prod_{i=2}^{m}\sigma_{\min}(\mathbf{U}_{i}^{*T}\widehat{}\mathbf{U}_{i}^{t})$
$\displaystyle\geq\sigma_{r_{1}}(\mathbf{U}_{2}^{*}\otimes\cdots\otimes\mathbf{U}_{m}^{*})(1-L_{t}^{2})^{(m-1)/2}$
$\displaystyle\geq c_{m}(1-L_{t})^{2}\underline{\lambda},$ (12.42)

for some small constant $c_{m}>0$ depending only on $m$, and the last
inequality holds since $1-L_{t}^{2}\geq\frac{3}{4}$. We bound
$\|\mathbf{Z}_{1}^{t}\|$ under the event ${\cal E}_{4}$.

$\displaystyle\|\mathbf{Z}_{1}^{t}\|$
$\displaystyle=\|\mathbf{Z}_{1}(\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t})\|$
$\displaystyle=\|\mathbf{Z}_{1}\big{(}({\cal P}_{\mathbf{U}_{2}^{*}}+{\cal
P}_{\mathbf{U}_{2}^{*}}^{\perp})\otimes\cdots\otimes({\cal
P}_{\mathbf{U}_{m}^{*}}+{\cal
P}_{\mathbf{U}_{m}^{*}}^{\perp})\big{)}(\widehat{}\mathbf{U}_{2}^{t}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t})\|$
$\displaystyle\leq
C_{m}[(\bar{d})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}+C_{m}[(\bar{d}\bar{r})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}L_{t},$
(12.43)

where the last inequality holds since ${\cal E}_{4}$ holds and
$\|\widehat{}\mathbf{U}_{i}^{tT}\mathbf{U}_{i\perp}^{*}\|\leq L_{t}$. Now
since $\widehat{}\mathbf{U}_{1}^{t+1}$ is the top $r_{1}$ left singular
vectors of $\widetilde{}\mathbf{A}_{1}^{t}$ and $\mathbf{U}_{1}$ is the top
$r_{1}$ left singular vectors of $\mathbf{X}_{1}^{t}$, from Wedin’s
sin$\Theta$ Theorem, we have

$\displaystyle d_{c}(\widehat{}\mathbf{U}_{1}^{t+1},\mathbf{U}_{1})$
$\displaystyle\leq\frac{C\|\widetilde{}\mathbf{A}_{1}^{t}-\mathbf{X}_{1}^{t}\|}{\underline{\lambda}}\leq\frac{C(\|\mathbf{E}_{1}\|_{\rm
F}+\|\mathbf{Z}_{1}^{t}\|)}{\underline{\lambda}}$
$\displaystyle\overset{\eqref{Z1t}}{\leq}\frac{C|\Omega^{*}|^{1/2}\tau_{u}+C_{m}[(\bar{d})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}+C_{m}[(\bar{d}\bar{r})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}L_{t}}{\underline{\lambda}}.$

The derivation for $d_{c}(\widehat{}\mathbf{U}_{i}^{t+1},\mathbf{U}_{i})$ when
$i\geq 2$ is similar to this case and hence

$\displaystyle
L_{t+1}\leq\frac{C|\Omega^{*}|^{1/2}\tau_{u}+C_{m}[(\bar{d})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}}{\underline{\lambda}}+\frac{C_{m}[(\bar{d}\bar{r})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}}{\underline{\lambda}}L_{t}.$

From condition $(b)$, we have
$C_{m}[(\bar{d}\bar{r})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}/\underline{\lambda}\leq
1/2$, so the above inequality implies

$\displaystyle L_{t_{\max}}\leq(\frac{1}{2})^{t_{\max}}\cdot
L_{0}+\frac{C|\Omega^{*}|^{1/2}\tau_{u}+C_{m}[(\bar{d})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}}{\underline{\lambda}}.$

If we choose $t_{\max}\geq(C_{m}\log(\bar{d}\kappa_{0})\vee 1)$, then

$\displaystyle
L_{t_{\max}}\leq\frac{C|\Omega^{*}|^{1/2}\tau_{u}}{\underline{\lambda}}+\frac{C_{m}[(\bar{d})^{1/2}+\bar{r}^{(m-1)/2}]\sigma_{z}}{\underline{\lambda}}.$
(12.44)

Set the event ${\cal E}_{5}=\\{\|\bm{\mathcal{Z}}\times_{i=1}^{m}{\cal
P}_{\widehat{}\mathbf{U}_{i}}\|_{\rm F}\leq
C(r^{*}+\sum_{i=1}^{m}d_{i}r_{i})\sigma_{z}^{2}\\}$. Then from [Zhang and Xia,
2018, Lemma 5], $\mathbb{P}({\cal E}_{5})\geq 1-\exp(-C\bar{d}\bar{r})$. And
we also consider
$\|\bm{\mathcal{T}}^{*}\times_{i}\widehat{}\mathbf{U}_{i\perp}^{T}\|_{\rm F}$,
we consider $i=1$ for simplicity.

$\displaystyle\|\bm{\mathcal{T}}^{*}\times_{1}\widehat{}\mathbf{U}_{1\perp}^{T}\|_{\rm
F}$
$\displaystyle=\|\widehat{}\mathbf{U}_{1\perp}^{T}\mathbf{T}_{1}^{*}\|_{\rm
F}\leq\|{\cal
P}_{\widehat{}\mathbf{U}_{1\perp}}\mathbf{T}_{1}^{*}(\widehat{}\mathbf{U}_{2}^{t_{\max}-1}\otimes\cdots\otimes\widehat{}\mathbf{U}_{m}^{t_{\max}-1})\|_{\rm
F}\cdot\prod_{i=2}^{m}\sigma_{\min}^{-1}(\mathbf{U}_{i}^{*T}\widehat{}\mathbf{U}_{i}^{t_{\max}-1})$
$\displaystyle\leq C_{m}(\|\bm{\mathcal{E}}\|_{\rm
F}+\sqrt{r_{1}}\|\mathbf{Z}_{1}^{t_{\max}-1}\|)$ $\displaystyle\leq
C_{m}|\Omega^{*}|^{1/2}\tau_{u}+C_{m}(\sqrt{d_{1}r_{1}}+\sqrt{r^{*}})\sigma_{z},$
(12.45)

where the second inequality holds from [Zhang and Xia, 2018, Lemma 6] and the
last inequality holds from (12.4).

Now we are in the right position to bound
$\|\widehat{\bm{\mathcal{T}}}-\bm{\mathcal{T}}^{*}\|_{\rm F}$ under ${\cal
E}_{5}$.

$\displaystyle\|\widehat{\bm{\mathcal{T}}}-\bm{\mathcal{T}}^{*}\|_{\rm F}$
$\displaystyle=\|\widetilde{\bm{\mathcal{A}}}\times_{i=1}^{m}{\cal
P}_{\widehat{}\mathbf{U}_{i}}-\bm{\mathcal{T}}^{*}\|_{\rm F}$
$\displaystyle\leq\|(\widetilde{\bm{\mathcal{A}}}-\bm{\mathcal{T}}^{*})\times_{i=1}^{m}{\cal
P}_{\widehat{}\mathbf{U}_{i}}\|_{\rm
F}+\|\bm{\mathcal{T}}^{*}-\bm{\mathcal{T}}^{*}\times_{i=1}^{m}{\cal
P}_{\widehat{}\mathbf{U}_{i}}\|_{\rm F}$
$\displaystyle\leq\|\bm{\mathcal{E}}\|_{\rm
F}+\|\bm{\mathcal{Z}}\times_{i=1}^{m}{\cal
P}_{\widehat{}\mathbf{U}_{i}}\|_{\rm
F}+\sum_{i=1}^{m}\|\bm{\mathcal{T}}^{*}\times_{i}\widehat{}\mathbf{U}_{i\perp}^{T}\|_{\rm
F}$ $\displaystyle\leq
C_{m}|\Omega^{*}|^{1/2}\tau_{u}+C_{m}(\sqrt{r^{*}}+\sqrt{\bar{d}\bar{r}})\sigma_{z},$
(12.46)

where the last inequality follows from (12.4). Finally applying Lemma 13.6 and
we get $\widehat{\bm{\mathcal{T}}}_{0}$ is
$(2\mu_{1}\kappa_{0})^{2}$-incoherent and
$\|\widehat{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
2\|\widehat{\bm{\mathcal{T}}}-\bm{\mathcal{T}}^{*}\|_{\rm F}$. Therefore from
condition $(a),(b)$ in Lemma 5.2, the initialization condition $(a)$ in
Theorem 5.1 holds.

###  12.5 Proof of Lemma 5.3

For each $j\in[m]$ and $i\in[d_{j}]$, we have

$\|\mathbf{e}_{i}^{\top}{\cal
M}_{j}(\bm{\mathcal{S}}_{\alpha})\|_{\ell_{0}}=\sum\nolimits_{\omega:\omega_{j}=i}\mathbbm{1}\big{(}|[\bm{\mathcal{Z}}]_{\omega}|>\alpha\sigma_{z}\big{)}=\sum\nolimits_{\omega:\omega_{j}=i}[\bm{\mathcal{Y}}]_{\omega}$

where $\bm{\mathcal{Y}}\in\\{0,1\\}^{d_{1}\times\cdots\times d_{m}}$ having
$i.i.d.$ Bernoulli entries and
$q:=\mathbb{P}([\bm{\mathcal{Y}}]_{\omega}=1)=\mathbb{P}(|[\bm{\mathcal{Z}}]_{\omega}|>\alpha\sigma_{z})\leq\alpha^{-\theta}$.

Denote
$X_{ij}=\sum\nolimits_{\omega:\omega_{j}=i}[\bm{\mathcal{Y}}]_{\omega}$. By
Chernoff bound, if $d_{j}^{-}q\geq 3\log(m\bar{d}^{3})$, we get

$\displaystyle\mathbb{P}\Big{(}X_{ij}-d_{j}^{-}q\geq
d_{j}^{-}q\Big{)}\leq\exp\big{\\{}-d_{j}^{-1}q/3\big{\\}}\leq(m\bar{d}^{3})^{-1}$

implying that

$\displaystyle\mathbb{P}\Big{(}\bigcap\nolimits_{i,j}\big{\\{}X_{ij}\leq
2d_{j}^{-}q\big{\\}}\Big{)}\geq 1-m\bar{d}(m\bar{d}^{3})^{-1}=1-\bar{d}^{-2}.$
(12.47)

On the other hand, if $d_{j}^{-}q\leq 3\log(m\bar{d}^{3})$, by Chernoff bound,
we get

$\displaystyle\mathbb{P}\Big{(}X_{ij}\geq
10\log(m\bar{d}^{3})\Big{)}\leq(m\bar{d}^{3})^{-1}$

implying that

$\displaystyle\mathbb{P}\Big{(}\bigcap\nolimits_{i,j}\big{\\{}X_{ij}\leq
10\log(m\bar{d}^{3})\big{\\}}\Big{)}\geq
1-m\bar{d}(m\bar{d}^{3})^{-1}=1-\bar{d}^{-2}.$ (12.48)

Putting (12.47) and (12.48), since $q\leq\alpha^{-\theta}$, we get

$\mathbb{P}\Big{(}\bigcap\nolimits_{i,j}\Big{\\{}X_{ij}\leq\max\big{\\{}10\log(m\bar{d}^{3}),2d_{j}^{-}\alpha^{-\theta}\big{\\}}\Big{\\}}\Big{)}\geq
1-\bar{d}^{-2},$

which completes the proof.

###  12.6 Proof of Theorem 5.4

Conditioned on $\mathfrak{E}_{1}$ defined in Lemma 5.3, Theorem 5.4 is a
special case of Theorem 5.1. Indeed, in Theorem 5.1, we replace $\sigma_{z}$
with $\alpha\sigma_{z}$, and $|\Omega^{\ast}|\log\bar{d}$ with
$\alpha^{\prime}d^{\ast}\asymp\bar{d}\log(m\bar{d})$, then we get Theorem 5.4.

###  12.7 Proof of Lemma 5.5

From the choice of $\alpha$ in Theorem 5.4, we see that the sparsity of
$\bm{\mathcal{S}}_{\alpha}$ is bounded by
$\alpha^{\prime}\asymp\frac{\bar{d}}{d^{*}}\log(m\bar{d}^{3})$. Therefore the
condition $(a)$ in Lemma 5.2 is satisfied. Now applying Lemma 5.2 and we get
the desired result.

###  12.8 Proof of Lemma 5.6

From Lemma 13.6, we have $\textsf{Trim}_{\eta,\mathbf{r}}(\bm{\mathcal{W}})$
is $2\mu_{1}\kappa_{0}$-incoherent. Now for all $j\in[m]$,

$\|\mathcal{M}_{j}(\mathscr{H}^{{\rm
HO}}_{\mathbf{r}}(\widetilde{\bm{\mathcal{W}}}))\|\leq\|\mathcal{M}_{j}(\widetilde{\bm{\mathcal{W}}})\|\leq\|\mathcal{M}_{j}(\bm{\mathcal{T}}^{*})\|+\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{9}{8}\bar{\lambda}.$

So we conclude

$\|\textsf{Trim}_{\eta,\mathbf{r}}(\bm{\mathcal{W}})\|_{\ell_{\infty}}\leq\frac{9}{8}\bar{\lambda}\prod_{i=1}^{m}(2\mu_{1}\kappa_{0})\sqrt{\frac{r_{j}}{d_{j}}}\leq(9\zeta/16)\cdot(\mu_{1}\kappa_{0})^{m}.$

where the last inequality follows from the upper bound for $\bar{\lambda}$.
This finishes the proof of the lemma.

###  12.9 Proof of Theorem 5.7

From the choice of $\zeta^{\prime}$ and Lemma 5.6, we know Assumption 2 and 3
hold with parameters $b_{l,\zeta^{\prime}}$ and $b_{u,\zeta^{\prime}}$ with
respect to the set
$\mathbb{B}_{2}^{\ast}=\mathbb{B}_{\infty}^{\ast}=\\{\bm{\mathcal{T}}+\bm{\mathcal{S}}:\|\bm{\mathcal{T}}+\bm{\mathcal{S}}\|_{\ell_{\infty}}\leq\zeta^{\prime},\bm{\mathcal{T}}\in\mathbb{M}_{\mathbf{r}},\bm{\mathcal{S}}\in\SS_{\gamma\alpha}\\}$.
Now the proof follows the proof of Theorem 4.1 with slight modification. Since
we can now guarantee in each iteration
$\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l}\in\mathbb{B}_{2}^{\ast}=\mathbb{B}_{\infty}^{\ast}$
from Lemma 5.6 and the choice of $\textsf{k}_{\textsf{pr}}$, we can use
Assumption 3 instead of Assumption 2 when estimating the low rank part. So we
only need to estimate $\textsf{Err}_{\infty}$ and
$\textsf{Err}_{2\mathbf{r}}$. From (5.8), we have $\textsf{Err}_{\infty}\leq
L_{\zeta}$. Now we estimate $\textsf{Err}_{2\mathbf{r}}$. In fact, from the
definition of $\textsf{Err}_{2\mathbf{r}}$, we have

$\textsf{Err}_{2\mathbf{r}}=\sup_{\bm{\mathcal{M}}\in\mathbb{M}_{2\mathbf{r}},\|\bm{\mathcal{M}}\|_{\rm
F}\leq
1}\langle\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}),\bm{\mathcal{M}}\rangle.$

Since for all $\omega\in[d_{1}]\times\ldots\times[d_{m}]$, we have
$[\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*})]_{\omega}$ is
bounded random variable with the upper bound given by $L_{\zeta}$. So apply
Lemma 13.3, we have $\textsf{Err}_{2\mathbf{r}}\leq
CL_{\zeta}\cdot(\bar{d}\bar{r}+r^{*})^{1/2}$ with with probability at least
$1-\bar{d}^{-2}$. Now we plug in the bounds for $\textsf{Err}_{\infty}$ and
$\textsf{Err}_{2\mathbf{r}}$ to Theorem 4.1 and we get the first part of the
theorem. For the $\ell_{\infty}$ bound, we apply Theorem 4.3 and Lemma 13.7.
And we finish the proof of the theorem.

###  12.10 Proof of Lemma 5.8

Algorithm 7 Initialization for binary tensor

Let $\mathbf{A}=\bm{\mathcal{A}}^{\langle
m_{0}\rangle}:=\textsf{reshape}(\bm{\mathcal{A}},[d_{1}\ldots
d_{m_{0}},d_{m_{0}+1}\ldots d_{m}])$ with $m_{0}=\lfloor\frac{m}{2}\rfloor$
and let $\widehat{}\mathbf{M}$ be the minimizer to (12.49).

$\widehat{\bm{\mathcal{T}}}=\textsf{reshape}(\widehat{}\mathbf{M},[d_{1},\ldots,d_{m}])$.

$\widehat{\bm{\mathcal{T}}}_{0}=\textsf{Trim}_{\eta,\mathbf{r}}(\widehat{\bm{\mathcal{T}}})$
with $\eta=16\mu_{1}\|\widehat{\bm{\mathcal{T}}}\|_{\rm F}/(7\sqrt{d^{*}})$.

Output: $\widehat{\bm{\mathcal{T}}}_{0}$.

We first introduce some notations. Let $m_{0}=\lfloor\frac{m}{2}\rfloor$, and
denote $\mathbf{T}^{*}=(\bm{\mathcal{T}}^{*})^{\langle m_{0}\rangle}$,
$\mathbf{S}^{*}=(\bm{\mathcal{S}}^{*})^{\langle m_{0}\rangle}$ and
$\mathbf{A}=\bm{\mathcal{A}}^{\langle m_{0}\rangle}$, then
$\mathbf{T}^{*},\mathbf{S}^{*},\mathbf{A}$ are matrices of size $d_{1}\ldots
d_{m_{0}}\times d_{m_{0}+1}\ldots d_{m}=:d_{1}^{*}\times d_{2}^{*}$. Since
$\bm{\mathcal{T}}^{\ast}$ admits the decomposition
$\bm{\mathcal{T}}^{\ast}=\bm{\mathcal{C}}^{\ast}\cdot\llbracket\mathbf{U}_{1}^{\ast},\cdots,\mathbf{U}_{m}^{\ast}\rrbracket$,
we have
$\bm{\mathcal{T}}^{*}=(\mathbf{U}_{m_{0}}\otimes\cdots\otimes\mathbf{U}_{1})\bm{\mathcal{C}}^{\langle
m_{0}\rangle}(\mathbf{U}_{m}\otimes\cdots\otimes\mathbf{U}_{m_{0}+1})^{T}$ and
hence the rank of $\mathbf{T}^{*}$ is $r=\min\\{r_{1}\cdots
r_{m_{0}},r_{m_{0}+1}\cdots r_{m}\\}$. We denote
$\mathbf{M}=\mathbf{T}^{*}+\mathbf{S}^{*}$.

Under Assumption 5, we have
$\|\mathbf{T}^{*}\|_{\ell_{\infty}},\|\mathbf{S}^{*}\|_{\ell_{\infty}}\leq\frac{\zeta}{2}$
and thus $\|\mathbf{M}\|_{\ell_{\infty}}\leq\zeta$. Now we bound the nuclear
norm of $\mathbf{M}$. Using triangle inequality and we have

$\displaystyle\|\mathbf{M}\|_{\ast}$
$\displaystyle\leq\|\mathbf{T}^{*}\|_{\ast}+\|\mathbf{S}^{*}\|_{\ast}$
$\displaystyle\leq\frac{\zeta}{2}(rd^{*})^{1/2}+\frac{\zeta}{2}|\Omega^{*}|^{1/2}\min(d_{1}^{*},d_{2}^{*})^{1/2}$
$\displaystyle=\big{(}\frac{\zeta}{2}+\frac{\zeta}{2}\cdot\frac{\min(d_{1}^{*},d_{2}^{*})^{1/2}}{(rd^{*})^{1/2}}|\Omega^{*}|^{1/2}\big{)}(rd^{*})^{1/2}$
$\displaystyle\leq\zeta(rd^{*})^{1/2},$

where the last inequality holds since condition $(a)$ holds. Now with a little
bit abuse of notation, we consider the following convex program,

$\displaystyle\min\mathfrak{L}(\mathbf{X})=-\langle\mathbf{A},\log(p(X))\rangle-\langle
1-\mathbf{A},\log(1-p(\mathbf{X}))\rangle,\text{~{}s.t.~{}}\|\mathbf{X}\|_{\ast}\leq\zeta\sqrt{d^{*}r}\text{~{}and~{}}\|\mathbf{X}\|_{\ell_{\infty}}\leq\zeta,$
(12.49)

where the notation $1-\mathbf{A}$ is the entrywise subtraction, and
$p(\mathbf{X})$ is applying $p$ entrywisely to $\mathbf{X}$. Denote
$\widehat{}\mathbf{M}$ be the minimizer to (12.49) and apply the Theorem 1 in
Davenport et al. [2014] with the sample size $d^{*}$ and we get with
probability at least $1-\frac{C}{d_{1}^{*}+d_{2}^{*}}$,

$\displaystyle\|\widehat{}\mathbf{M}-\mathbf{M}\|_{\rm F}^{2}\leq
C_{\zeta}[r(d_{1}^{*}+d_{2}^{*})d^{*}]^{1/2}$

with $C_{\zeta}=C\cdot\zeta L_{\zeta}\beta_{\zeta}$ and
$\beta_{\zeta}=\sup_{|x|\leq\zeta}\frac{p(x)(1-p(x))}{(p^{\prime}(x))^{2}}$.

Now we reshape $\widehat{}\mathbf{M}$ back to a tensor, and denote
$\widehat{\bm{\mathcal{T}}}=\textsf{reshape}(\widehat{}\mathbf{M},[d_{1},\ldots,d_{m}])$.
Since reshape keeps the Frobenius norm unchanged, we have

$\|\widehat{\bm{\mathcal{T}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}=\|\widehat{}\mathbf{T}-\mathbf{T}^{*}\|_{\rm
F}\leq\|\widehat{}\mathbf{M}-\mathbf{M}\|_{\rm F}+\|\mathbf{S}^{*}\|_{\rm
F}\leq
C_{\zeta}^{1/2}[r(d_{1}^{*}+d_{2}^{*})d^{*}]^{1/4}+|\Omega^{*}|^{1/2}\frac{\zeta}{2}.$

Finally we output
$\bm{\mathcal{T}}_{0}=\textsf{Trim}_{\eta,\mathbf{r}}(\widehat{\bm{\mathcal{T}}})$
with $\eta=16\mu_{1}\|\widehat{\bm{\mathcal{T}}}\|_{\rm F}/(7\sqrt{d^{*}})$,
and from Lemma 5.6 and Lemma 13.6, since condition $(b)$ and $(c)$ hold, we
get

$(1)~{}\mu(\widehat{\bm{\mathcal{T}}}_{0})\leq
2\kappa_{0}\mu_{1};~{}(2)~{}\|\widehat{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq 2\|\widehat{\bm{\mathcal{T}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F};~{}(3)~{}\|\widehat{\bm{\mathcal{T}}}\|_{\ell_{\infty}}\leq
C_{m}(\mu_{1}\kappa_{0})^{m}\frac{\sqrt{r^{*}}}{\sqrt{d^{*}}}\bar{\lambda}.$

And together with the upper bound for $\underline{\lambda}$ in Assumption 5,
the initialization condition in Theorem 5.7 is satisfied.

###  12.11 Proof of Theorem 5.9

The proof of this theorem is similar to that of Theorem 5.7. From the choice
of $\zeta^{\prime}$ and Lemma 5.6, we know Assumption 2 and 3 hold with
parameters $b_{l,\zeta^{\prime}}=e^{-\zeta^{\prime}}$ and
$b_{u,\zeta^{\prime}}=e^{\zeta^{\prime}}$ with respect to the set
$\mathbb{B}_{2}^{\ast}=\mathbb{B}_{\infty}^{\ast}=\\{\bm{\mathcal{T}}+\bm{\mathcal{S}}:\|\bm{\mathcal{T}}+\bm{\mathcal{S}}\|_{\ell_{\infty}}\leq\zeta^{\prime},\bm{\mathcal{T}}\in\mathbb{M}_{\mathbf{r}},\bm{\mathcal{S}}\in\SS_{\gamma\alpha}\\}$.
Now the proof follows the proof of Theorem 4.1 with slight modification. Since
we can now guarantee in each iteration
$\widehat{\bm{\mathcal{T}}}_{l}+\widehat{\bm{\mathcal{S}}}_{l}\in\mathbb{B}_{2}^{\ast}=\mathbb{B}_{\infty}^{\ast}$
from Lemma 5.6 and the choice of $\textsf{k}_{\textsf{pr}}$, we can use
Assumption 3 instead of Assumption 2 when estimating the low rank part. So we
only need to estimate $\textsf{Err}_{\infty}$ and
$\textsf{Err}_{2\mathbf{r}}$. From (5.8), we have
$\textsf{Err}_{\infty}\leq\|\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*})\|_{\ell_{\infty}}$.
Simple calculation shows

$\nabla\mathfrak{L}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*})=-\frac{1}{I}\bm{\mathcal{Y}}+\exp(\bm{\mathcal{T}}^{*}+\bm{\mathcal{S}}^{*}),$

and notice using a union bound and Poisson’s tail bound, when $I\geq
Ce^{\zeta}\log(d^{*})$, we have with probability exceeding
$1-\frac{1}{d^{*}}$, $\|\bm{\mathcal{Y}}\|_{\ell_{\infty}}\leq 10Ie^{\zeta}$.
Therefore we have $\textsf{Err}_{\infty}\leq 11e^{\zeta}$.

The estimation for $\textsf{Err}_{2\mathbf{r}}$ is given in Theorem 4.3 Han et
al. [2020], which states

$\textsf{Err}_{2\mathbf{r}}\leq
C\sqrt{\frac{r^{*}+m\bar{d}\bar{r}}{I/e^{\zeta}}}$

with probability exceeding $1-\frac{1}{d^{*}}$.

Now we plug in the bounds for $\textsf{Err}_{\infty}$ and
$\textsf{Err}_{2\mathbf{r}}$ to Theorem 4.1 and we get the first part of the
theorem. For the $\ell_{\infty}$ bound, we apply Theorem 4.3 and Lemma 13.7.
And we finish the proof of the theorem.

###  12.12 Proof of Lemma 5.10

With slight modification of the proof of Theorem 4.3 in Han et al. [2020], we
have

$\|\widetilde{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
C\sqrt{\frac{e^{\zeta}}{I}}(\sum_{i=1}^{m}\sqrt{d_{i}r_{i}}+\sqrt{d^{-}_{i}r_{i}})+\|\bm{\mathcal{S}}^{*}\|_{\rm
F}$

under the condition $I\geq Ce^{\zeta}\bar{d}$ with probability exceeding
$1-1/d^{*}$. Therefore since we assume $I\geq
C_{1}\sum_{i=1}^{m}(d_{i}r_{i}+d_{i}^{-}r_{i})\bar{r}\underline{\lambda}^{-2}$
and $|\Omega^{*}|\leq C\zeta^{-2}\underline{\lambda}^{2}\bar{r}^{-1}$, we have
$\|\widetilde{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
c_{1,m}\underline{\lambda}\cdot\min\big{\\{}\delta^{2}\bar{r}^{-1/2},(\kappa_{0}^{2m}\bar{r}^{1/2})^{-1}\big{\\}}\leq\underline{\lambda}/8$.
Now we apply Lemma 5.6 and Lemma 13.6 we see

$(1)~{}\mu(\widehat{\bm{\mathcal{T}}}_{0})\leq
2\kappa_{0}\mu_{1};~{}(2)~{}\|\widehat{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq 2\|\widehat{\bm{\mathcal{T}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F};~{}(3)~{}\|\widehat{\bm{\mathcal{T}}}\|_{\ell_{\infty}}\leq
C_{m}(\mu_{1}\kappa_{0})^{m}\frac{\sqrt{r^{*}}}{\sqrt{d^{*}}}\bar{\lambda}.$

From Assumption 6, we see the initialization requirements in 5.9 is satisfied.

###  12.13 Proof of Theorem 6.1

We use induction to prove this theorem.

#### Step 0: Base case.

From the initialization, we have
$\|\widehat{\bm{\mathcal{T}}}_{0}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
c_{1,m}\delta\bar{r}^{-1/2}\cdot\underline{\lambda}$.

#### Step 1: Estimating
$\|\widehat{\bm{\mathcal{T}}}_{l+1}-\bm{\mathcal{T}}^{*}\|_{\rm F}$.

We prove this case assuming

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq c_{1,m}\delta\bar{r}^{-1/2}\cdot\underline{\lambda}.$ (12.50)

We point out that this also implies
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}\leq
c_{1,m}b_{l}b_{u}^{-1}\bar{r}^{-1/2}\cdot\underline{\lambda}$ since
$\delta\lesssim b_{l}^{2}b_{u}^{-2}$. In order to use Lemma 13.2, we need to
derive an upper bound for
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm F}$.

#### Step 1.1: Estimating
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm F}$.

For arbitrary $1\geq\delta>0$, we have,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm
F}^{2}\leq(1+\delta/2)\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}+(1+2/\delta)\beta^{2}\|{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}^{*}\|_{\rm F}^{2}$ (12.51)

Now we consider the bound for
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\|_{\rm F}^{2}$.

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$
$\displaystyle=\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}-2\beta\langle\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\rangle+\beta^{2}\|\mathcal{P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$
$\displaystyle\leq(1+\beta^{2}b_{u}^{2})\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}-2\beta\langle\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\rangle$
(12.52)

where the last inequality holds from the Assumption 2 since
$\widehat{\bm{\mathcal{T}}}_{l}\in\mathbb{B}_{2}^{*}$ from (12.50). Also,

$\displaystyle\langle\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*},\mathcal{P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\rangle$
$\displaystyle=\langle\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*},\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*}\rangle-\langle{\cal
P}_{\mathbb{T}_{l}}^{\perp}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}),\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*}\rangle$
$\displaystyle\geq
b_{l}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}-\frac{C_{1,m}b_{u}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{3}$ (12.53)

where the last inequality is from Assumption 2, Lemma 13.1 and Cauchy-Schwartz
inequality and $C_{1,m}=2^{m}-1$. Together with (12.13) and (12.13), and since
we have $\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{0.1b_{l}}{2b_{u}C_{1,m}}\cdot\underline{\lambda}$, we get,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta\mathcal{P}_{\mathbb{T}_{l}}(\bm{\mathcal{G}}_{l}-\bm{\mathcal{G}}^{*})\|_{\rm
F}^{2}$ $\displaystyle\leq(1-2\beta
b_{l}+\beta^{2}b_{u}^{2})\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{2\beta
C_{1,m}b_{u}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{3}$ $\displaystyle\leq(1-1.9\beta
b_{l}+\beta^{2}b_{u}^{2})\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}.$ (12.54)

Since we have $0.75b_{l}b_{u}^{-1}\geq\delta^{1/2}$, if we choose
$\beta\in[0.4b_{l}b_{u}^{-2},1.5b_{l}b_{u}^{-2}]$, we have $1-1.9\beta
b_{l}+\beta^{2}b_{u}^{2}\leq 1-\delta$.

So from (12.51) and (12.13), we get

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm
F}^{2}\leq(1+\frac{\delta}{2})(1-\delta)\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+(1+\frac{2}{\delta})\textsf{Err}_{2\mathbf{r}}^{2}$ (12.55)

where in the inequality we use the definition of $\textsf{Err}_{2\mathbf{r}}$
and that $\beta\leq 1$. Now from the upper bound for
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}$ and the
signal-to-noise ratio, we verified that
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm F}\leq\underline{\lambda}/8$
and thus
$\sigma_{\max}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l})\leq\underline{\lambda}/8$.

#### Step 1.2: Estimating
$\|\widehat{\bm{\mathcal{T}}}_{l+1}-\bm{\mathcal{T}}^{*}\|_{\rm F}$.

Now that we verified the condition of Lemma 13.2, from the Algorithm 5, we
have,

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l+1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}\leq\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm
F}^{2}+C_{m}\frac{\sqrt{\bar{r}}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm F}^{3}$ (12.56)

where $C_{m}>0$ is the constant depending only on $m$ as in Lemma 13.2. From
(12.55) and the assumption that
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\lesssim_{m}\frac{\delta}{\sqrt{\bar{r}}}\cdot\underline{\lambda}$ and
$\textsf{Err}_{2\mathbf{r}}\lesssim_{m}\frac{\delta^{2}}{\sqrt{\bar{r}}}\cdot\underline{\lambda}$,
we get

$\displaystyle
C_{m}\frac{\sqrt{\bar{r}}}{\underline{\lambda}}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm F}\leq\frac{\delta}{4}$ (12.57)

From (12.56), (12.55) and (12.57), we get

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l+1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}\leq(1+\frac{\delta}{4})\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}-\beta{\cal
P}_{\mathbb{T}_{l}}\bm{\mathcal{G}}_{l}\|_{\rm
F}^{2}\leq(1-\delta^{2})\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}+\frac{4}{\delta}\textsf{Err}_{2\mathbf{r}}^{2}$ (12.58)

Together with the assumption
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\lesssim_{m}\frac{\delta}{\sqrt{\bar{r}}}\cdot\underline{\lambda}$ and
$\textsf{Err}_{2\mathbf{r}}\lesssim_{m}\frac{\delta^{2}}{\sqrt{\bar{r}}}\cdot\underline{\lambda}$,
we get

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l+1}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq c_{1,m}\frac{\delta}{\sqrt{\bar{r}}}\cdot\underline{\lambda},$ (12.59)

which completes the induction and completes the proof.

##  13 Technical Lemmas

######  Lemma 13.1.

Suppose $\mathbb{T}_{l}$ is the tangent space at the point
$\widehat{\bm{\mathcal{T}}}_{l}$, then we have

$\displaystyle\|{\cal P}_{\mathbb{T}_{l}}^{\perp}\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{2^{m}-1}{\underline{\lambda}}\|\bm{\mathcal{T}}^{*}-\widehat{\bm{\mathcal{T}}}_{l}\|_{\rm
F}^{2}.$

###### Proof.

See (Cai et al. [2020], Lemma 5.2). ∎

######  Lemma 13.2.

Let
$\bm{\mathcal{T}}^{*}=\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\ldots,\mathbf{V}_{m}^{*})$
be the tensor with Tucker rank $\mathbf{r}=(r_{1},\ldots,r_{m})$. Let
$\bm{\mathcal{D}}\in\mathbb{R}^{d_{1}\times\ldots\times d_{m}}$ be a
perturbation tensor such that $\underline{\lambda}\geq
8\sigma_{\max}(\bm{\mathcal{D}})$, where
$\sigma_{\max}(\bm{\mathcal{D}})=\max_{i=1}^{m}\|\mathcal{M}_{i}(\bm{\mathcal{D}})\|$.
Then we have

$\|\mathscr{H}^{{\rm
HO}}_{\mathbf{r}}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{D}})-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\|\bm{\mathcal{D}}\|_{\rm
F}+C_{m}\frac{\sqrt{\bar{r}}\|\bm{\mathcal{D}}\|_{\rm
F}^{2}}{\underline{\lambda}}$

where $C_{m}>0$ is an absolute constant depending only on $m$.

###### Proof.

Without loss of generality, we only prove the Lemma in the case $m=3$. First
notice that

$\mathscr{H}^{{\rm
HO}}_{\mathbf{r}}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{D}})=(\bm{\mathcal{T}}^{*}+\bm{\mathcal{D}})\cdot\llbracket{\cal
P}_{\mathbf{U}_{1}},{\cal P}_{\mathbf{U}_{2}},{\cal
P}_{\mathbf{U}_{3}}\rrbracket,$

where $\mathbf{U}_{i}$ are leading $r_{i}$ left singular vectors of
$\mathcal{M}_{i}(\bm{\mathcal{T}}^{*}+\bm{\mathcal{D}})$ and ${\cal
P}_{\mathbf{U}_{i}}=\mathbf{U}_{i}\mathbf{U}_{i}^{\top}$.

First from (Xia [2019], Theorem 1), we have for all $i\in[m]$

${\cal P}_{\mathbf{U}_{i}}-{\cal
P}_{\mathbf{V}_{i}^{*}}=\mathcal{S}_{i,1}+\sum_{j\geq 2}\mathcal{S}_{i,j},$

where
$\mathcal{S}_{i,j}=\mathcal{S}_{\mathcal{M}_{i}(\bm{\mathcal{T}}^{*}),j}(\mathcal{M}_{i}(\bm{\mathcal{D}}))$
and specially
$\mathcal{S}_{i,1}=(\mathcal{M}_{i}(\bm{\mathcal{T}}^{*})^{\top})^{\dagger}(\mathcal{M}_{i}(\bm{\mathcal{D}}))^{\top}{\cal
P}_{\mathbf{V}_{i}^{*}}^{\perp}+{\cal
P}_{\mathbf{V}_{i}^{*}}^{\perp}\mathcal{M}_{i}(\bm{\mathcal{D}})(\mathcal{M}_{i}(\bm{\mathcal{T}}^{*}))^{\dagger}$.
The explicit form of $S_{i,j}$ can be found in [Xia, 2019, Theorem 1]. Here,
we denote $\mathbf{A}^{\dagger}$ the pseudo-inverse of $\mathbf{A}$, i.e.,
$\mathbf{A}^{\dagger}=\mathbf{R}\mathbf{\Sigma}^{-1}\mathbf{L}^{\top}$ if
$\mathbf{A}$ has a thin-SVD as
$\mathbf{A}=\mathbf{L}\mathbf{\Sigma}\mathbf{R}^{\top}$. With a little abuse
of notations, we write
$(\mathbf{A}^{\dagger})^{k}=\mathbf{R}\mathbf{\Sigma}^{-k}\mathbf{L}^{\top}$
for any positive integer $k\geq 1$.

For the sake of brevity, we denote $\mathbf{S}_{i}=\sum_{j\geq 1}{\cal
S}_{i,j}$. By the definition of ${\cal S}_{i,j}$, we have the bound
$\|\mathcal{S}_{i,j}\|\leq\left(\frac{4\sigma_{\max}(\bm{\mathcal{D}})}{\underline{\lambda}}\right)^{j}$.
We get the upper bound for $\|\mathbf{S}_{i}\|$ as follows,

$\displaystyle\|\mathbf{S}_{i}\|=\|\sum_{j\geq
1}\mathcal{S}_{i,j}\|\leq\frac{4{\sigma_{\max}(\bm{\mathcal{D}})}}{\underline{\lambda}-4\sigma_{\max}(\bm{\mathcal{D}})}\leq\frac{8\sigma_{\max}(\bm{\mathcal{D}})}{\underline{\lambda}}$
(13.1)

So we have,

$\displaystyle\bm{\mathcal{T}}^{*}\cdot$ $\displaystyle\llbracket{\cal
P}_{\mathbf{U}_{1}},{\cal P}_{\mathbf{U}_{2}},{\cal
P}_{\mathbf{U}_{3}}\rrbracket=\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}}+\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{\ast}}+\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}+\mathbf{S}_{3}\rrbracket$ $\displaystyle=$
$\displaystyle\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket$ (13.2)
$\displaystyle+\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket$
$\displaystyle+\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},\mathbf{S}_{3}\rrbracket+\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket$
$\displaystyle~{}~{}~{}~{}+\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},\mathbf{S}_{3}\rrbracket$
(13.3)

We now bound each of
$\|\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\|_{\rm F}$,
$\|\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},\mathbf{S}_{3}\rrbracket\|_{\rm F}$ and
$\|\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket\|_{\rm F}$. Without loss of
generality, we only prove the bound of the first term.

$\displaystyle{\cal
M}_{1}\big{(}\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\big{)}=\mathbf{S}_{1}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})\left({\cal
P}_{\mathbf{V}_{3}}^{*}\otimes\mathbf{S}_{2}\right)^{\top}$ (13.4)

Write

$\displaystyle\mathbf{S}_{1}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})$
$\displaystyle=\left({\cal S}_{1,1}+\sum_{j\geq 2}{\cal
S}_{1,j}\right)\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})$ $\displaystyle={\cal
P}_{\mathbf{V}_{1}^{*}}^{\perp}\mathcal{M}_{1}(\bm{\mathcal{D}})\left(\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})\right)^{\dagger}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})+\sum_{j\geq
2}{\cal S}_{1,j}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})$ $\displaystyle={\cal
M}_{1}\big{(}\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}}^{\perp},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\big{)}+\sum_{j\geq 2}{\cal
S}_{1,j}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})$ (13.5)

where we used the fact ${\cal P}_{\mathbf{V}_{1}^{*}}^{\perp}{\cal
M}_{1}(\bm{\mathcal{T}}^{*})={\bf 0}$.

Thus we obtain an upper bound for
$\|\mathbf{S}_{1}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})\|$ as follows

$\displaystyle\|\mathbf{S}_{1}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})\|\leq\sigma_{\max}(\bm{\mathcal{D}})+\underline{\lambda}\sum_{j\geq
2}\left(\frac{4\sigma_{\max}(\bm{\mathcal{D}})}{\underline{\lambda}}\right)^{j}\leq
4\sigma_{\max}(\bm{\mathcal{D}}),$ (13.6)

where the first inequality is due to the explicit form of ${\cal S}_{1,j}$.
See [Xia, 2019, Theorem 1].

So from (13.4) and (13.6), we get

$\displaystyle\|\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\|_{\rm F}$
$\displaystyle\leq\|\mathbf{S}_{1}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})\|_{\rm
F}\cdot\|{\cal P}_{\mathbf{V}_{3}}^{*}\otimes\mathbf{S}_{2}\|\leq
C_{1}\sqrt{\bar{r}}\frac{\sigma_{\max}(\bm{\mathcal{D}})^{2}}{\underline{\lambda}}$
(13.7)

where $C_{1}>0$ is an absolute constant.

Now we consider the linear terms
$\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},{\cal P}_{\mathbf{V}_{3}^{*}}\rrbracket$,
$\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket$ and
$\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal P}_{\mathbf{V}_{1}^{*}},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket$. Clearly, we have

$\displaystyle\mathcal{M}_{1}\left(\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},{\cal P}_{\mathbf{V}_{3}^{*}}\rrbracket\right)$
$\displaystyle=\mathbf{S}_{1}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})$
$\displaystyle\mathcal{M}_{2}\left(\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\right)$
$\displaystyle=\mathbf{S}_{2}\mathcal{M}_{2}(\bm{\mathcal{T}}^{\ast})$
$\displaystyle\mathcal{M}_{3}\left(\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket\right)$
$\displaystyle=\mathbf{S}_{3}\mathcal{M}_{3}(\bm{\mathcal{T}}^{\ast}),$ (13.8)

whose explicit representations are already studied in eq. (13). As a result,
we can write

$\displaystyle\bm{\mathcal{T}}^{*}\cdot\llbracket\mathbf{S}_{1},$
$\displaystyle{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{T}}^{*}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket$ $\displaystyle=$
$\displaystyle\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}}^{\perp},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal P}_{\mathbf{V}_{2}^{*}}^{\perp},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}^{\perp}\rrbracket$ $\displaystyle+\sum_{j\geq
2}\Big{(}\mathcal{M}_{1}(\bm{\mathcal{T}}^{*})\cdot\llbracket{\cal
S}_{1,j},{\cal P}_{\mathbf{V}_{2}^{\ast}},{\cal
P}_{\mathbf{V}_{3}^{\ast}}\rrbracket+\mathcal{M}_{2}(\bm{\mathcal{T}}^{*})\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{\ast}},{\cal S}_{2,j},{\cal
P}_{\mathbf{V}_{3}^{\ast}}\rrbracket+\mathcal{M}_{3}(\bm{\mathcal{T}}^{*})\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{\ast}},{\cal P}_{\mathbf{V}_{2}^{\ast}},{\cal
S}_{3,j}\rrbracket\Big{)}.$ (13.9)

Now we bound $\bm{\mathcal{D}}\cdot\llbracket{\cal P}_{\mathbf{U}_{1}},{\cal
P}_{\mathbf{U}_{2}},{\cal P}_{\mathbf{U}_{3}}\rrbracket$ as follows

$\displaystyle\bm{\mathcal{D}}\cdot\llbracket$ $\displaystyle{\cal
P}_{\mathbf{U}_{1}},{\cal P}_{\mathbf{U}_{2}},{\cal
P}_{\mathbf{U}_{3}}\rrbracket=\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}}+\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}}+\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}+\mathbf{S}_{3}\rrbracket$ $\displaystyle=$
$\displaystyle\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket$
$\displaystyle+\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket$
$\displaystyle+\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}},\mathbf{S}_{2},\mathbf{S}_{3}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},\mathbf{S}_{3}\rrbracket$
$\displaystyle~{}~{}~{}~{}+\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},\mathbf{S}_{3}\rrbracket$
(13.10)

Similarly as proving the bound (13.7), we can show

$\displaystyle\max\left\\{\|\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},{\cal
P}_{\mathbf{V}_{2}^{*}},{\cal P}_{\mathbf{V}_{3}^{*}}\rrbracket\|_{\rm
F},\|\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\|_{\rm
F},\|\bm{\mathcal{D}}\cdot\llbracket\mathbf{S}_{1},\mathbf{S}_{2},\mathbf{S}_{3}\rrbracket\|_{\rm
F}\right\\}\leq
C_{1}\sqrt{\bar{r}}\frac{\sigma_{\max}(\bm{\mathcal{D}})^{2}}{\underline{\lambda}}$
(13.11)

where $C_{1}>0$ is an absolute constant.

Finally, by (13), (13.7), (13) and (13.11), we have

$\displaystyle\big{\|}(\bm{\mathcal{T}}^{*}$
$\displaystyle+\bm{\mathcal{D}})\cdot\llbracket{\cal P}_{\mathbf{U}_{1}},{\cal
P}_{\mathbf{U}_{2}},{\cal
P}_{\mathbf{U}_{3}}\rrbracket-\bm{\mathcal{T}}^{*}\big{\|}_{\rm F}$
$\displaystyle\leq\big{\|}\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}_{1}^{*}}^{\perp},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}^{*}_{1}},{\cal P}_{\mathbf{V}_{2}^{*}}^{\perp},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}^{*}_{1}},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}^{\perp}\rrbracket+\bm{\mathcal{D}}\cdot\llbracket{\cal
P}_{\mathbf{V}^{*}_{1}},{\cal P}_{\mathbf{V}_{2}^{*}},{\cal
P}_{\mathbf{V}_{3}^{*}}\rrbracket\big{\|}_{\rm F}$
$\displaystyle~{}~{}~{}~{}+C_{1}\frac{\sqrt{\bar{r}}\sigma_{\max}(\bm{\mathcal{D}})^{2}}{\underline{\lambda}}$
$\displaystyle\leq\|\bm{\mathcal{D}}\|_{\rm
F}+C_{2}\frac{\sqrt{\bar{r}}\sigma_{\max}(\bm{\mathcal{D}})^{2}}{\underline{\lambda}}$
(13.12)

where $C_{1},C_{2}>0$ are absolute constants ($C_{2,m}=16m+2^{m+1}$ in the
case of general $m$). This finishes the proof of the lemma. ∎

######  Lemma 13.3.

Assume all the entries of
$\bm{\mathcal{Z}}\in\mathbb{R}^{d_{1}\times\ldots\times d_{m}}$ are
independent mean-zero random variables with bounded Orlicz-$\psi_{2}$ norm:

$\|[\bm{\mathcal{Z}}]_{\omega}\|_{\psi_{2}}=\sup_{q\geq
1}(\mathbb{E}|[\bm{\mathcal{Z}}]_{\omega}|^{q})^{1/q}/q^{1/2}\leq\sigma_{z}$

Then there exists some constants $C_{m},c_{m}>0$ depending only on $m$ such
that

$\sup_{\bm{\mathcal{M}}\in\mathbb{M}_{2\mathbf{r}},\|\bm{\mathcal{M}}\|_{F}\leq
1}\langle\bm{\mathcal{Z}},\bm{\mathcal{M}}\rangle\leq
C_{m}\sigma_{z}\left(r^{*}+\sum_{i=1}^{m}d_{i}r_{i}\right)^{1/2}$

with probability at least $1-\exp(-c_{m}\sum_{i=1}^{m}d_{i}r_{i})$, where
$r^{*}=r_{1}\ldots r_{m}$.

###### Proof.

See the proof of (Han et al. [2020], Lemma D.5). ∎

######  Lemma 13.4 (Maximum of sub-Gaussian).

Let $Z_{1},\ldots,Z_{N}$ be $N$ random variables such that
$\mathbb{E}\exp\\{tZ_{i}\\}\leq\exp\\{t^{2}\sigma_{z}^{2}/2\\}$ for all
$i\in[N]$. Then

$\mathbb{P}(\max_{1\leq i\leq N}|Z_{i}|>t)\leq
2N\exp(-\frac{t^{2}}{2\sigma_{z}^{2}}).$

###### Proof.

The claim follows from the following two facts:

$\mathbb{P}(\max_{1\leq i\leq N}Z_{i}>t)\leq\mathbb{P}(\cup_{1\leq i\leq
N}\\{Z_{i}>t\\})\leq N\mathbb{P}(Z_{i}>t)\leq
N\exp(-\frac{t^{2}}{2\sigma_{z}^{2}}),$

and

$\max_{1\leq i\leq N}|Z_{i}|=\max_{1\leq i\leq 2N}Z_{i}$

with $Z_{N+i}=-Z_{i}$ for $i\in[N]$. ∎

######  Lemma 13.5 (Spikiness implies incoherence).

Let $\bm{\mathcal{T}}^{*}\in\mathbb{M}_{\mathbf{r}}$ satisfies Assumption 1
with parameter $\mu_{1}$. Then we have:

$\mu(\bm{\mathcal{T}}^{*})\leq\mu_{1}\kappa_{0}.$

where $\mu(\bm{\mathcal{T}}^{*})$ is the incoherence parameter of
$\bm{\mathcal{T}}^{*}$ and $\kappa_{0}$ is the condition number of
$\bm{\mathcal{T}}^{*}$.

###### Proof.

Denote
$\bm{\mathcal{T}}^{*}=\bm{\mathcal{C}}^{*}\cdot\llbracket\mathbf{U}_{1},\ldots,\mathbf{U}_{m}\rrbracket$.
Now we check the incoherence condition of $\bm{\mathcal{T}}^{*}$. For all
$i\in[d_{j}]$ and $j\in[m]$,

$\|\mathbf{e}_{i}^{\top}\mathcal{M}_{j}(\bm{\mathcal{T}}^{*})\|_{\ell_{2}}=\|\mathbf{e}_{i}\mathbf{U}_{j}\mathcal{M}_{j}(\bm{\mathcal{C}}^{*})\|_{\ell_{2}}\geq\|\mathbf{e}_{i}^{\top}\mathbf{U}_{j}\|_{\ell_{2}}\cdot\underline{\lambda}\geq\|\mathbf{e}_{i}^{\top}\mathbf{U}_{j}\|_{\ell_{2}}\frac{\|\bm{\mathcal{T}}^{*}\|_{\rm
F}}{\sqrt{r_{j}}\kappa_{0}}.$

On the other hand, we have

$\|\mathbf{e}_{i}^{\top}\mathcal{M}_{j}(\bm{\mathcal{T}}^{*})\|_{\ell_{2}}\leq\sqrt{d_{j}^{-}}\|\bm{\mathcal{T}}^{*}\|_{\ell_{\infty}}\leq\mu_{1}\|\bm{\mathcal{T}}^{*}\|_{\rm
F}\frac{1}{\sqrt{d_{j}}},$

where the last inequality is due to the spikiness condition
$\bm{\mathcal{T}}^{*}$ satisfies. Together with these two inequalities, we
have

$\|\mathbf{e}_{i}^{\top}\mathbf{U}_{j}\|_{\ell_{2}}\leq\sqrt{\frac{r_{j}}{d_{j}}}\mu_{1}\kappa_{0}.$

And this finishes the proof of the lemma. ∎

######  Lemma 13.6.

Let $\bm{\mathcal{T}}^{*}\in\mathbb{M}_{\mathbf{r}}$ satisfies Assumption 1
with parameter $\mu_{1}$. Suppose that $\bm{\mathcal{W}}$ satisfies
$\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{\underline{\lambda}}{8}$, then we have
$\textsf{Trim}_{\zeta,\mathbf{r}}(\bm{\mathcal{W}})$ is
$(2\mu_{1}\kappa_{0})^{2}$-incoherent if we choose
$\zeta=\frac{16}{7}\mu_{1}\frac{\|\bm{\mathcal{W}}\|_{\rm F}}{\sqrt{d^{*}}}$.
Also, it satisfies

$\|\textsf{Trim}_{\zeta,\mathbf{r}}(\bm{\mathcal{W}})-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+\frac{C_{m}\sqrt{\bar{r}}\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}}{\underline{\lambda}},$

where $C_{m}>0$ depends only on $m$.

###### Proof.

Notice $\textsf{Trim}_{\zeta,\mathbf{r}}(\bm{\mathcal{W}})=\mathscr{H}^{{\rm
HO}}_{\mathbf{r}}(\widetilde{\bm{\mathcal{W}}})$, where
$\widetilde{\bm{\mathcal{W}}}$ is the entrywise truncation of
$\bm{\mathcal{W}}$ with the thresholding $\zeta/2$. To check the incoherence
of $\mathscr{H}^{{\rm HO}}_{\mathbf{r}}(\widetilde{\bm{\mathcal{W}}})$, denote
$\widetilde{}\mathbf{U}_{j}$ the top-$r_{j}$ left singular vectors of ${\cal
M}_{j}(\widetilde{\bm{\mathcal{W}}})$, and $\widetilde{}\mathbf{\Lambda}_{j}$
the $r_{j}\times r_{j}$ diagonal matrix containing the top-$r_{j}$ singular
values of ${\cal M}_{j}(\widetilde{\bm{\mathcal{W}}})$. Then, there exist a
$\widetilde{}\mathbf{V}_{j}\in\mathbb{R}^{d_{j}^{-}\times r_{j}}$ satisfying
$\widetilde{}\mathbf{V}_{j}^{\top}\widetilde{}\mathbf{V}_{j}=\mathbf{I}_{r_{j}}$
such that

$\widetilde{}\mathbf{U}_{j}\widetilde{}\mathbf{\Lambda}_{j}={\cal
M}_{j}(\widetilde{\bm{\mathcal{W}}})\widetilde{}\mathbf{V}_{j}.$

Now we can also bound the $\ell_{\infty}$-norm of $\bm{\mathcal{T}}^{*}$:

$\|\bm{\mathcal{T}}^{*}\|_{\ell_{\infty}}\leq\mu_{1}\frac{\|\bm{\mathcal{T}}^{*}\|_{\rm
F}}{\sqrt{d^{*}}}\leq\mu_{1}\frac{\|\bm{\mathcal{W}}\|_{\rm
F}+\|\bm{\mathcal{T}}^{*}-\bm{\mathcal{W}}\|_{\rm
F}}{\sqrt{d^{*}}}\leq\mu_{1}\frac{\|\bm{\mathcal{W}}\|_{\rm
F}+\|\bm{\mathcal{T}}^{*}\|_{\rm F}/8}{\sqrt{d^{*}}}.$

This together with the definition of $\zeta$, we have:

$\mu_{1}\frac{\|\bm{\mathcal{T}}^{*}\|_{\rm F}}{\sqrt{d^{*}}}\leq
8/7\cdot\mu_{1}\frac{\|\bm{\mathcal{W}}\|_{\rm F}}{\sqrt{d^{*}}}=\zeta/2.$

And thus $\|\bm{\mathcal{T}}^{*}\|_{\ell_{\infty}}\leq\zeta/2$. Then for all
$i\in[d_{j}]$,

$\|\mathbf{e}_{i}^{\top}\widetilde{}\mathbf{U}_{j}\|_{\ell_{2}}=\|\mathbf{e}_{i}^{\top}\mathcal{M}_{j}(\widetilde{\bm{\mathcal{W}}})\widetilde{}\mathbf{V}_{j}\widetilde{}\mathbf{\Lambda}_{j}^{-1}\|_{\ell_{2}}\leq\frac{\|\mathbf{e}_{i}^{\top}\mathcal{M}_{j}(\widetilde{\bm{\mathcal{W}}})\|_{\ell_{2}}}{\lambda_{r_{j}}(\widetilde{}\mathbf{\Lambda}_{j})}\leq\frac{\zeta/2\cdot(d_{j}^{-})^{1/2}}{7/8\cdot\lambda_{r_{j}}(\mathcal{M}_{j}(\bm{\mathcal{T}}^{*}))}.$

where the last inequality is due to
$\|\widetilde{\bm{\mathcal{W}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\underline{\lambda}/8$ since
$\|\bm{\mathcal{T}}^{*}\|_{\ell_{\infty}}\leq\zeta/2$ and
$\|\widetilde{\bm{\mathcal{W}}}\|_{\ell_{\infty}}\leq\zeta/2$. Meanwhile,

$\|\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\sqrt{r_{j}}\kappa_{0}\lambda_{r_{j}}(\mathcal{M}_{j}(\bm{\mathcal{T}}^{*})).$

There for the $\zeta=\frac{16}{7}\mu_{1}\frac{\|\bm{\mathcal{W}}\|_{\rm
F}}{\sqrt{d^{*}}}$, we have for all $j\in[m]$

$\max_{i\in[d_{j}]}\|\mathbf{e}_{i}\widetilde{}\mathbf{U}_{j}\|_{\ell_{2}}\leq\frac{64}{49}\mu_{1}\kappa_{0}\frac{\|\bm{\mathcal{T}}^{*}\|_{\rm
F}+\underline{\lambda}/8}{\|\bm{\mathcal{T}}^{*}\|_{\rm
F}}\sqrt{\frac{r_{j}}{d_{j}}}\leq
2\mu_{1}\kappa_{0}\sqrt{\frac{r_{j}}{d_{j}}}.$

where the second last inequality is from $\|\bm{\mathcal{W}}\|_{\rm
F}\leq\|\bm{\mathcal{T}}^{*}\|_{\rm
F}+\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm F}$ and the last inequality
is from $\|\bm{\mathcal{T}}^{*}\|_{\rm F}\geq\underline{\lambda}$.

The second claim follows from the fact that
$\|\widetilde{\bm{\mathcal{W}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\underline{\lambda}/8$, and from Lemma 13.2,

$\displaystyle\|\textsf{Trim}_{\zeta,\mathbf{r}}(\bm{\mathcal{W}})-\bm{\mathcal{T}}^{*}\|_{\rm
F}=\|\widetilde{\bm{\mathcal{W}}}-\bm{\mathcal{T}}^{*}\|_{\rm F}$
$\displaystyle\leq\|\widetilde{\bm{\mathcal{W}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+C_{m}\frac{\sqrt{\bar{r}}\|\widetilde{\bm{\mathcal{W}}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}}{\underline{\lambda}}$
$\displaystyle\leq\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}+C_{m}\frac{\sqrt{\bar{r}}\|\bm{\mathcal{W}}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}}{\underline{\lambda}}$

This finishes the proof of the lemma. ∎

We introduce some notations for the following lemmas. Denote by
$\widehat{\bm{\mathcal{T}}}_{l}=\bm{\mathcal{C}}_{l}\cdot(\mathbf{U}_{1},\ldots,\mathbf{U}_{m})$,
$\bm{\mathcal{T}}^{*}=\bm{\mathcal{C}}^{*}\cdot(\mathbf{U}_{1}^{*},\ldots,\mathbf{U}_{m}^{*})$.

$\displaystyle\mathbf{R}_{i}=\arg\min_{\mathbf{R}\in\mathbb{O}_{r_{i}}}\|\mathbf{U}_{i}-\mathbf{U}_{i}^{*}\mathbf{R}\|_{\rm
F},i\in[m]$ (13.13)

If we let
$\mathbf{U}_{i}^{*T}\mathbf{U}_{i}=\mathbf{L}_{i}\mathbf{S}_{i}\mathbf{W}_{i}^{\top}$
be the SVD of $\mathbf{U}_{i}^{*T}\mathbf{U}_{i}$, then the closed form of
$\mathbf{R}_{i}$ is given by
$\mathbf{R}_{i}=\mathbf{L}_{i}\mathbf{W}_{i}^{\top}$. And we rewrite

$\bm{\mathcal{T}}^{*}=\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\cdots,\mathbf{V}_{m}^{*})$

where
$\bm{\mathcal{S}}^{*}=\bm{\mathcal{C}}^{*}\cdot(\mathbf{R}_{1}^{\top},\cdots,\mathbf{R}_{m}^{\top})$
and $\mathbf{V}_{i}^{*}=\mathbf{U}_{i}^{*}\mathbf{R}_{i},i\in[m]$. So
$\mathbf{V}_{i}^{*}$ is also $\mu_{0}$-incoherent.

######  Lemma 13.7 (Entry-wise estimation of
$|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|$).

Suppose $\bm{\mathcal{T}}^{*}$ satisfies Assumption 1. Under the assumptions
that $\widehat{\bm{\mathcal{T}}}_{l}$ is $(2\mu_{1}\kappa_{0})^{2}$-incoherent
and $\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{\underline{\lambda}}{16m\bar{r}^{1/2}\kappa_{0}}$, then we have

$|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|^{2}\leq
C_{m}\bar{r}^{m}\underline{d}^{-(m-1)}(\mu_{1}\kappa_{0})^{4m}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2},$

where $C_{m}=2^{4m+1}(m+1)$.

###### Proof.

First we have

$\displaystyle\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}$
$\displaystyle=(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m})+\sum_{i=1}^{m}\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\ldots,\mathbf{V}_{i-1}^{*},\mathbf{U}_{i}-\mathbf{V}_{i}^{*},\mathbf{U}_{i+1},\ldots,\mathbf{U}_{m})$
(13.14)

From Lemma 13.5, we get $\bm{\mathcal{T}}^{*}$ is
$\mu_{1}^{2}\kappa_{0}^{2}$-incoherent. So we have for all
$\omega=(\omega_{1},\ldots,\omega_{m})\in[d_{1}]\times\ldots\times[d_{m}]$

$\displaystyle|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|$
$\displaystyle\leq\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}\prod_{i=1}^{m}\|(\mathbf{U}_{i})_{\omega_{i}:}\|+\sum_{i=1}^{m}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})_{\omega_{i}:}\|\prod_{k=1}^{i-1}\|(\mathbf{V}_{k}^{*})_{\omega_{k}:}\|\prod_{k=i+1}^{m}\|(\mathbf{U}_{k})_{\omega_{k}:}\|$
$\displaystyle\leq\sqrt{\frac{r^{*}}{d^{*}}}(2\mu_{1}\kappa_{0})^{2m}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}+(2\mu_{1}\kappa_{0})^{2m-2}\sqrt{\frac{\bar{r}^{m-1}}{\underline{d}^{m-1}}}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}\sum_{i=1}^{m}\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})_{\omega_{i}:}\|$

where $r^{*}=\prod_{i=1}^{m}r_{i},d^{*}=\prod_{i=1}^{m}d_{i}$ and
$\bar{r}=\max_{i=1}^{m}r_{i},\underline{d}=\min_{i=1}^{m}d_{i}$. From AG–GM
inequality, we have

$\displaystyle|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|^{2}$
$\displaystyle\leq(m+1)(2\mu_{1}\kappa_{0})^{4m}\frac{r^{*}}{d^{*}}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+(m+1)(2\mu_{1}\kappa_{0})^{4m-4}\frac{\bar{r}^{m-1}}{\underline{d}^{m-1}}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}\sum_{i=1}^{m}\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})_{\omega_{i}:}\|^{2}$
(13.15)
$\displaystyle\leq(m+1)\bar{r}^{m}\underline{d}^{-(m-1)}(2\mu_{1}\kappa_{0})^{4m}\left(\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+\underline{\lambda}^{2}\sum_{i=1}^{m}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}\right)$ $\displaystyle\leq
2(m+1)\bar{r}^{m}\underline{d}^{-(m-1)}(2\mu_{1}\kappa_{0})^{4m}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}$

where the last inequality is from Lemma 13.9, and this finishes the proof of
the lemma. ∎

######  Lemma 13.8 (Estimation of $\|{\cal
P}_{\Omega}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*})\|_{\rm
F}^{2}$).

Let $\Omega$ be the $\alpha$-fraction set. Suppose $\bm{\mathcal{T}}^{*}$
satisfies Assumption 1. Under the assumptions that
$\widehat{\bm{\mathcal{T}}}_{l}$ is $(2\mu_{1}\kappa_{0})^{2}$-incoherent and
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{\underline{\lambda}}{16m\bar{r}^{1/2}\kappa_{0}}$, we have

$\|{\cal
P}_{\Omega}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*})\|_{\rm
F}^{2}\leq
C_{m}(\mu_{1}\kappa_{0})^{4m}\bar{r}^{m}\alpha\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2},$

where $C_{m}=2^{4m+1}(m+1)$.

###### Proof.

First from (13.15) in Lemma 13.7, we have

$|[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}|^{2}\leq(m+1)(2\mu_{1}\kappa_{0})^{4m}\frac{r^{*}}{d^{*}}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+(m+1)(2\mu_{1}\kappa_{0})^{4m-4}\frac{\bar{r}^{m-1}}{\underline{d}^{m-1}}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}\sum_{i=1}^{m}\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})_{\omega_{i}:}\|^{2}.$

Since $\Omega$ is an $\alpha$-fraction set, we have

$\displaystyle\|{\cal
P}_{\Omega}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*})\|_{\rm
F}^{2}$
$\displaystyle=\sum_{\omega\in\Omega}[\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}]_{\omega}^{2}$
$\displaystyle\leq(m+1)(2\mu_{1}\kappa_{0})^{4m}\alpha
r^{*}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+(m+1)(2\mu_{1}\kappa_{0})^{4m-4}\alpha\bar{r}^{m-1}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}\sum_{i=1}^{m}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm F}^{2}$
$\displaystyle\leq(m+1)(2\mu_{1}\kappa_{0})^{4m}\alpha
r^{*}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+(m+1)(2\mu_{1}\kappa_{0})^{4m-4}\alpha\bar{r}^{m}\overline{\lambda}^{2}\sum_{i=1}^{m}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}$
$\displaystyle\leq(m+1)(2\mu_{1}\kappa_{0})^{4m}\bar{r}^{m}\alpha\left(\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+\underline{\lambda}^{2}\sum_{i=1}^{m}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}\right)$ (13.16)

Now we invoke Lemma 13.9, and we get

$\|{\cal
P}_{\Omega}(\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*})\|_{\rm
F}^{2}\leq
2(m+1)(2\mu_{1}\kappa_{0})^{4m}\bar{r}^{m}\alpha\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2},$

which finishes the proof of the lemma. ∎

######  Lemma 13.9 (Estimation of
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}^{2}$).

Let
$\widehat{\bm{\mathcal{T}}}_{l}=\bm{\mathcal{C}}_{l}\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m})$
be the $l$-th step value in Algorithm 2 and let
$\bm{\mathcal{T}}^{*}=\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\cdots,\mathbf{V}_{m}^{*})$.
Suppose $\widehat{\bm{\mathcal{T}}}_{l}$ satisfies
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{\underline{\lambda}}{16m\bar{r}^{1/2}\kappa_{0}}$. Then we have
the following estimation for
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}^{2}$:

$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm F}^{2}\geq
0.5\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+0.5\underline{\lambda}^{2}\sum_{i=1}^{m}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}.$

###### Proof.

First we have

$\displaystyle\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}$
$\displaystyle=(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m})+\sum_{i=1}^{m}\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\ldots,\mathbf{V}_{i-1}^{*},\mathbf{U}_{i}-\mathbf{V}_{i}^{*},\mathbf{U}_{i+1},\ldots,\mathbf{U}_{m})$
(13.17)

Notice that we have

$\displaystyle\|\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\ldots,\mathbf{V}_{i-1}^{*},\mathbf{U}_{i}-\mathbf{V}_{i}^{*},\mathbf{U}_{i+1},\ldots,\mathbf{U}_{m})\|_{\rm
F}^{2}=\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})\mathcal{M}_{i}(\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}$ (13.18)

Denote
$\bm{\mathcal{X}}_{i}=\bm{\mathcal{S}}^{*}\cdot(\mathbf{V}_{1}^{*},\ldots,\mathbf{V}_{i-1}^{*},\mathbf{U}_{i}-\mathbf{V}_{i}^{*},\mathbf{U}_{i+1},\ldots,\mathbf{U}_{m})$,
then we have

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}$ $\displaystyle=\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+\sum_{i=1}^{m}\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})\mathcal{M}_{i}(\bm{\mathcal{S}}^{*})\|_{\rm
F}^{2}+2\sum_{i<j}\langle\bm{\mathcal{X}}_{i},\bm{\mathcal{X}}_{j}\rangle+2\sum_{i=1}^{m}\langle(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m}),\bm{\mathcal{X}}_{i}\rangle$
$\displaystyle\geq\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+\sum_{i=1}^{m}\underline{\lambda}^{2}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}+2\sum_{i<j}\langle\bm{\mathcal{X}}_{i},\bm{\mathcal{X}}_{j}\rangle+2\sum_{i=1}^{m}\langle(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m}),\bm{\mathcal{X}}_{i}\rangle$

Notice that
$\mathcal{M}_{i}(\bm{\mathcal{X}}_{i})=(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})\mathcal{M}_{i}(\bm{\mathcal{S}}^{*})\big{(}\mathbf{U}_{m}\otimes\mathbf{U}_{i+1}\otimes\mathbf{V}_{i-1}\otimes\mathbf{V}_{1}\big{)}^{\top}$.
So we have the estimation of
$|\langle(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m}),\bm{\mathcal{X}}_{i}\rangle|$
is as follows:

$\displaystyle|\langle(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m}),\bm{\mathcal{X}}_{i}\rangle|$
$\displaystyle=|\langle\mathcal{M}_{i}\big{(}(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m})\big{)},\mathcal{M}_{i}(\bm{\mathcal{X}}_{i})\rangle|$
$\displaystyle\leq\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})^{\top}\mathbf{U}_{i}\|\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}\|\bm{\mathcal{S}}^{*}\|_{\rm F}$
$\displaystyle\leq\sqrt{\bar{r}}\bar{\lambda}\|\mathbf{U}_{i}^{\top}(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})\|_{\rm
F}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm F}$ (13.20)

Now we estimate
$\|\mathbf{U}_{i}^{\top}(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})\|_{\rm F}$ by
plugging in the closed form of $\mathbf{V}_{i}^{*}$ as in (13.13)

$\displaystyle\|\mathbf{U}_{i}^{\top}(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})\|_{\rm
F}=\|\mathbf{I}-\mathbf{S}_{i}\|_{\rm
F}\leq\|\mathbf{I}-\mathbf{S}_{i}^{2}\|_{\rm
F}=\|\mathbf{U}_{i\perp}^{*T}\mathbf{U}_{i}\|_{\rm
F}^{2}\leq\|\mathbf{U}_{i}-\mathbf{U}_{i}^{*}\mathbf{R}_{i}\|_{\rm F}^{2}$
(13.21)

From Wedin’ sin$\Theta$ Theorem, we have for $i\in[m]$

$\displaystyle\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}\leq\|\mathbf{U}_{i}-\mathbf{U}_{i}^{*}\|_{\rm F}$
$\displaystyle\leq\frac{\sqrt{2}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}}{\underline{\lambda}-\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|}\leq\frac{2\sqrt{2}\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}}{\underline{\lambda}}\leq\frac{1}{4m\bar{r}^{1/2}\kappa_{0}}$ (13.22)

where the second last inequality is from
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|\leq{\underline{\lambda}/2}$
and the last inequality is from
$\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}\leq\frac{\underline{\lambda}}{16m\bar{r}^{1/2}\kappa_{0}}$. Then from (13)
and (13.22), we have

$\displaystyle|\langle(\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*})\cdot(\mathbf{U}_{1},\cdots,\mathbf{U}_{m}),\bm{\mathcal{X}}_{i}\rangle|\leq\frac{1}{8m^{2}}\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+\frac{1}{8}\underline{\lambda}^{2}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}$ (13.23)

The estimation of
$|\langle\bm{\mathcal{X}}_{i},\bm{\mathcal{X}}_{j}\rangle|(i<j)$ is as
follows. From $\eqref{uj-vj}$, we have

$\displaystyle|\langle\bm{\mathcal{X}}_{i},\bm{\mathcal{X}}_{j}\rangle|$
$\displaystyle=|\langle\mathcal{M}_{i}(\bm{\mathcal{S}}^{*})\mathbf{M}_{i,j},(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})^{\top}\mathbf{V}_{i}^{*}\mathcal{M}_{i}(\bm{\mathcal{S}}^{*})\rangle|$
$\displaystyle\leq\bar{\lambda}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}\|\mathbf{M}_{i,j}\|\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})^{\top}\mathbf{V}_{i}^{*}\|_{\rm
F}$ $\displaystyle\leq\bar{\lambda}\|\bm{\mathcal{S}}^{*}\|_{\rm
F}\|(\mathbf{U}_{i}-\mathbf{V}_{i}^{*})^{\top}\mathbf{V}_{i}^{*}\|_{\rm
F}\|(\mathbf{U}_{j}-\mathbf{V}_{j}^{*})^{\top}\mathbf{V}_{j}^{*}\|_{\rm F}$
$\displaystyle\overset{(a)}{\leq}\sqrt{\bar{r}}\bar{\lambda}^{2}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}\|\mathbf{U}_{j}-\mathbf{V}_{j}^{*}\|_{\rm F}^{2}$
$\displaystyle\overset{(b)}{\leq}\frac{1}{16m^{2}}\underline{\lambda}^{2}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}\|\mathbf{U}_{j}-\mathbf{V}_{j}^{*}\|_{\rm F}$
$\displaystyle\leq\frac{1}{32m^{2}}\underline{\lambda}^{2}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}+\frac{1}{32m^{2}}\underline{\lambda}^{2}\|\mathbf{U}_{j}-\mathbf{V}_{j}^{*}\|_{\rm
F}^{2}$ (13.24)

where
$\mathbf{M}_{i,j}=\mathbf{I}\otimes\ldots\otimes\mathbf{I}\otimes\mathbf{U}_{j}^{\top}(\mathbf{U}_{j}-\mathbf{V}_{j}^{*})\otimes\mathbf{U}_{j-1}^{\top}\mathbf{V}_{j-1}^{*}\otimes\ldots\mathbf{U}_{i+1}^{\top}\mathbf{V}_{i+1}^{*}\otimes\mathbf{I}\otimes\ldots\otimes\mathbf{I}$,
$(a)$ holds because of (13.21), $(b)$ holds because of (13.22).

As a result of (13), (13.23) and (13), we have

$\displaystyle\|\widehat{\bm{\mathcal{T}}}_{l}-\bm{\mathcal{T}}^{*}\|_{\rm
F}^{2}\geq 0.5\|\bm{\mathcal{C}}_{l}-\bm{\mathcal{S}}^{*}\|_{\rm
F}^{2}+0.5\underline{\lambda}^{2}\sum_{i=1}^{m}\|\mathbf{U}_{i}-\mathbf{V}_{i}^{*}\|_{\rm
F}^{2}$

which finishes the proof of the lemma. ∎