$\displaystyle\lesssim\kappa_{o}\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right\|$
$\displaystyle\lesssim\kappa_{o}\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

∎

###### Proof of Lemma A.6.

Define

$\Delta^{\tau,(m)}\coloneqq\bar{Z}_{o}^{d,\tau,(m)}\left(\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}\right)^{-1}-Z_{o}\left(Z_{o}^{\top}Z_{o}\right)^{-1}$

where $\bar{Z}_{o}^{d,\tau,(m)}=Z_{o}^{d,\tau,(m)}H_{o}^{d,\tau,(m)}$. Then,

$\left\|e_{m}^{\top}\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})\left[\bar{Z}_{o}^{d,\tau,(m)}\left(\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}\right)^{-1}-Z_{o}\left(Z_{o}^{\top}Z_{o}\right)^{-1}\right]\right\|_{2}=\left\|\sum_{t=1}^{T_{o}}\omega_{mt}\epsilon_{mt}\Delta^{\tau,(m)}_{t,\cdot}\right\|_{2}.$

Note that
$\mathbb{E}[\omega_{mt}\epsilon_{mt}\Delta^{\tau,(m)}_{t,\cdot}|\Delta^{\tau,(m)}_{t,\cdot}]=0$
and $\\{\epsilon_{mt}\\}_{t\leq T_{o}}$ are independent across $t$
conditioning on $\\{\Delta^{\tau,(m)}_{t,\cdot}\\}_{t\leq T_{o}}$. Hence, we
have by the matrix Bernstein inequality with Claim A.7 that

$\displaystyle\left\|\sum_{t=1}^{T_{o}}\omega_{mt}\epsilon_{mt}\Delta^{\tau,(m)}_{t,\cdot}\right\|_{2}$
$\displaystyle\lesssim\sqrt{\sigma^{2}||\Delta^{\tau,(m)}||_{F}^{2}\max\\{\log
N_{o},\log
T_{o}\\}}+\sigma||\Delta^{\tau,(m)}||_{2,\infty}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\}$
$\displaystyle\lesssim\sigma\frac{\sqrt{r}}{\sqrt{\psi_{\min,o}}}\frac{\sigma}{\psi_{\min,o}}\sqrt{\kappa_{o}^{3}\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}}.$

######  Claim A.7.

With probability at least $1-O(\min\\{N_{o}^{-10},T_{o}^{-10}\\})$, we have
for all $0\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu$ and $1\leq m\leq
N_{o}$,

$\displaystyle||\Delta^{\tau,(m)}||$
$\displaystyle\lesssim\frac{1}{\sqrt{\psi_{\min,o}}}\frac{\sigma}{\psi_{\min,o}}\sqrt{\kappa_{o}^{3}\max\\{N_{o},T_{o}\\}},\
\ ||\Delta^{\tau,(m)}||_{2,\infty}$
$\displaystyle\lesssim\frac{1}{\sqrt{\psi_{\min,o}}}\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\kappa_{o}^{5}\mu_{o}r\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}}{\min\\{N_{o},T_{o}\\}}}.$

The proof for the part

$\left\|e_{m}^{\top}\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})^{\top}\left[\bar{X}_{o}^{d,\tau,(N_{o}+m)}\left(\bar{X}_{o}^{d,\tau,(N_{o}+m)\top}\bar{X}_{o}^{d,\tau,(N_{o}+m)}\right)^{-1}-X_{o}\left(X_{o}^{\top}X_{o}\right)^{-1}\right]\right\|_{2}$

is similar, and therefore omitted for brevity. ∎

###### Proof of Claim A.7.

By Lemma 12 of Chen et al., 2019b  with Lemma A.5, we have

$\displaystyle||\Delta^{\tau,(m)}||$
$\displaystyle\lesssim\max\Bigl{\\{}\left\|Z_{o}(Z_{o}^{\top}Z_{o})^{-1}\right\|^{2},\left\|\bar{Z}_{o}^{d,\tau,(m)}\left(\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}\right)^{-1}\right\|^{2}\Bigr{\\}}\left\|\bar{Z}_{o}^{d,\tau,(m)}-Z_{o}\right\|$
$\displaystyle\lesssim\frac{1}{\psi_{\min,o}}\frac{\kappa_{o}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\left\|X_{o}\right\|$
$\displaystyle\lesssim\frac{1}{\sqrt{\psi_{\min,o}}}\frac{\kappa_{o}^{\frac{3}{2}}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}.$

In addition, because

$\displaystyle\left\|\left(\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}\right)^{-1}-(Z_{o}^{\top}Z_{o})^{-1}\right\|$
$\displaystyle\leq\left\|\left(\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}\right)^{-1}\right\|\left\|\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}-Z_{o}^{\top}Z_{o}\right\|\left\|(Z_{o}^{\top}Z_{o})^{-1}\right\|$
$\displaystyle\lesssim\frac{1}{\psi_{\min,o}}\kappa_{o}^{2}\frac{\sigma}{\psi_{\min,o}}\sqrt{\max\\{N_{o},T_{o}\\}},$

we have from Lemma A.5 that

$\displaystyle\left\|\Delta^{\tau,(m)}\right\|_{2,\infty}$
$\displaystyle\leq\left\|\bar{Z}_{o}^{d,\tau,(m)}\right\|_{2,\infty}\left\|\left(\bar{Z}_{o}^{d,\tau,(m)\top}\bar{Z}_{o}^{d,\tau,(m)}\right)^{-1}-(Z_{o}^{\top}Z_{o})^{-1}\right\|+\left\|\bar{Z}_{o}^{d,\tau,(m)}-Z_{o}\right\|_{2,\infty}\left\|(Z_{o}^{\top}Z_{o})^{-1}\right\|$
$\displaystyle\lesssim\frac{1}{\sqrt{\psi_{\min,o}}}\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\kappa_{o}^{5}\mu_{o}r\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}}{\min\\{N_{o},T_{o}\\}}}.$

∎

###  A.5 Technical lemmas: Statistical properties of the nuclear norm
penalized estimators and the corresponding non-convex estimator

Lastly, we present the statistical properties of the non-convex estimator
$(\breve{X}_{o},\breve{Z}_{o})$. Since this estimator is very close to the
nuclear norm penalized estimator $\widetilde{M}_{o}$ as we will see in Lemma
A.9, we can derive the convergence rates of the nuclear norm penalized
estimator from this result. Besides, the statistical properties of the
debiased estimators in the previous section are largely based on the result of
the non-convex estimators in this section.

Basically, the result in this section is the modification of Chen et al.,
2020b  for the case where missing is not at random and occurs only at one
column. To save space, we omit the proofs of some lemmas if the proof is a
simple modification of that in Chen et al., 2020b . We are willing to provide
the full proofs upon request.

First, the following lemma shows the statistical properties of the nonconvex
estimator which are used for the proofs in the previous sections. Remind that

$\displaystyle\mathcal{F}_{o}^{\tau}\coloneqq\begin{bmatrix}X_{o}^{\tau}\\\
Z_{o}^{\tau}\end{bmatrix}\in\mathbb{R}^{(N_{o}+T_{o})\times
r},\quad\mathcal{F}_{o}^{\tau,(m)}\coloneqq\begin{bmatrix}X_{o}^{\tau,(m)}\\\
Z_{o}^{\tau,(m)}\end{bmatrix}\in\mathbb{R}^{(N_{o}+T_{o})\times
r},\quad\mathcal{F}_{o}\coloneqq\begin{bmatrix}X_{o}\\\
Z_{o}\end{bmatrix}\in\mathbb{R}^{(N_{o}+T_{o})\times r}.$

######  Lemma A.8.

Suppose that Assumptions A.1 \- A.4 hold. With probability at least
$1-O(\min\\{N_{o}^{-11},T_{o}^{-11}\\})$, the iterates
$\\{\mathcal{F}_{o}^{\tau}\\}_{0\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu}$ and
$\\{\mathcal{F}_{o}^{\tau,(m)}\\}_{0\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu}$ satisfy

$\displaystyle\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}\right\|_{F}\leq
C_{F}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{F},$
(A.18)
$\displaystyle\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}\right\|\leq
C_{op}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|,$
(A.19) $\displaystyle\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right\|_{F}\leq
C_{3}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
(A.20) $\displaystyle\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\left(\mathcal{F}_{o}^{\tau,(m)}H_{o}^{\tau,(m)}-\mathcal{F}_{o}\right)_{m,\cdot}\right\|_{2}\leq
C_{4}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
(A.21)
$\displaystyle\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}\right\|_{2,\infty}\leq
C_{\infty}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
(A.22)
$\displaystyle\left\|X_{o}^{\tau+1}H_{o}^{\tau+1}-X_{o}\right\|_{2,\infty}\leq
C_{\infty,X}r^{1/2}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty},$
(A.23)
$\displaystyle\left\|Z_{o}^{\tau+1}H_{o}^{\tau+1}-Z_{o}\right\|_{2,\infty}\leq
C_{\infty,Z}r^{1/2}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|Z_{o}\right\|_{2,\infty},$
(A.24)
$\displaystyle\left\|X_{o}^{\tau\top}X_{o}^{\tau}-Z_{o}^{\tau\top}Z_{o}^{\tau}\right\|_{F}\leq
C_{B}\kappa_{o}\eta_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\sqrt{r}\psi_{\max,o}^{2}\leq
C_{B}\frac{\psi_{\max,o}}{\max\\{N_{o}^{5},T_{o}^{5}\\}},$ (A.25)
$\displaystyle f(X_{o}^{\tau},Z_{o}^{\tau})\leq
f(X_{o}^{\tau-1},Z_{o}^{\tau-1})-\frac{\eta_{o}}{2}\left\|\nabla
f(X_{o}^{\tau-1},Z_{o}^{\tau-1})\right\|_{F}^{2},$ (A.26)
$\displaystyle\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}H_{o}^{\tau,(m)}\right\|_{F}\leq
5C_{3}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
(A.27) $\displaystyle\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\mathcal{F}_{o}^{\tau,(m)}H_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|\leq
2C_{op}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|,$
(A.28) $\displaystyle\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\ \
\leq(C_{\infty}\kappa_{o}+C_{3})\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
(A.29)

where $C_{F}$, $C_{op}$, $C_{3}$, $C_{4}$,
$C_{\infty}$,$C_{\infty,X}$,$C_{\infty,Z}$, $C_{B}>0$ are absolute constants,
provided that
$\eta_{o}\overset{c}{\asymp}\frac{1}{\max\\{N_{o}^{6},T_{o}^{6}\\}\kappa_{o}^{3}\psi_{\max,o}}$
and that $\mkern 2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern
2.0mu=\max\\{N_{o}^{23},T_{o}^{23}\\}$.

###### Proof.

Because the initial estimators, $(X_{o}^{0},Z_{o}^{0})$ and
$(X_{o}^{0,(m)},Z_{o}^{0,(m)})$, are set to $(X_{o},Z_{o})$, (A.18) - (A.25)
are satisfied when $\tau=0$. Then, by the mathematical induction, Lemmas D.16
\- D.20 with Lemmas D.8, D.14 show that the iterates
$\\{\mathcal{F}_{o}^{\tau}\\}_{o\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu}$ and
$\\{\mathcal{F}_{o}^{\tau,(m)}\\}_{o\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu}$ satisfy (A.18) -
(A.25) with probability at least $1-O(\min\\{N_{o}^{-11},T_{o}^{-11}\\})$. In
addition, (A.26) - (A.29) are derived from Lemmas D.21 and D.22. ∎

The technical lemmas used in this proof are relegated to Section D. The
following lemma shows the proximity between the non-convex estimator and the
nuclear norm penalized estimator.

######  Lemma A.9.

Let $\tau^{*}_{o}=\operatorname*{arg\,min}_{0\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu}||\nabla
f(X^{\tau}_{o},Z^{\tau}_{o})||_{F}$. Suppose that Assumptions A.1 \- A.4 hold.
Then, with probability at least $1-O(\min\\{N_{o}^{-11},T_{o}^{-11}\\})$, we
have

$\displaystyle||\nabla f(X^{\tau^{*}_{o}}_{o},Z^{\tau^{*}_{o}}_{o})||_{F}\leq
C_{gr}\frac{1}{\max\\{N_{o}^{5},T_{o}^{5}\\}}\lambda_{o}\sqrt{\psi_{\min,o}},$
(A.30)
$\displaystyle\max\Bigl{\\{}\left\|X^{\tau^{*}_{o}}_{o}Z^{\tau^{*}_{o}\top}_{o}-\widetilde{M}_{o}\right\|_{F},\left\|X^{\tau^{*}_{o}}_{o}Z^{\tau^{*}_{o}\top}_{o}-\mathcal{P}_{r}(\widetilde{M}_{o})\right\|_{F}\Bigr{\\}}\leq
4C_{cvx}C_{gr}\frac{\lambda_{o}}{\max\\{N_{o}^{5},T_{o}^{5}\\}},$ (A.31)

where $C_{cvx},C_{gr}>0$ are absolute constants.

###### Proof.

The inequality (A.30) comes from Lemma D.15. In addition, we have

$\left\|\mathcal{P}_{r}(\widetilde{M}_{o})-\widetilde{M}_{o}\right\|_{F}\leq\left\|X^{\tau^{*}_{o}}_{o}Z^{\tau^{*}_{o}\top}_{o}-\widetilde{M}_{o}\right\|_{F}\leq
2C_{cvx}C_{gr}\frac{\lambda_{o}}{\max\\{N_{o}^{5},T_{o}^{5}\\}}$

from Lemma D.3 with Lemmas A.8, D.4 and D.5, and the inequality (A.30) by
setting
$(\ddot{X}_{o},\ddot{Z}_{o})=(X^{\tau^{*}_{o}}_{o}H^{\tau^{*}_{o}}_{o},Z^{\tau^{*}_{o}}_{o}H^{\tau^{*}_{o}}_{o})$.
Besides, the inequality (A.31) comes from this inequality. ∎

##  Appendix B Proofs of theorems and corollaries in the main text

Using the tools from the previous section, we shall now prove the theorems and
corollaries in the main text.

###  B.1 Proofs for Section 2

Proof of Theorem 2.1.

Note that

$\widetilde{M}-M=(\widetilde{M}-\breve{X}\breve{Z}^{\top})+(\breve{X}\breve{Z}^{\top}-XZ^{\top}).$

Here, $(\breve{X},\breve{Z})$ are the nonconvex estimator introduced in
Section A.1 and $(X,Z)=(UD^{\frac{1}{2}},VD^{\frac{1}{2}})$ where $UDV^{\top}$
is the SVD of $M$. Note that Assumptions A.1 \- A.4 are satisfied since the
number of missing entries $\vartheta_{o}$ is $|\Omega^{c}|$ in this case.
Then, we have from Lemmas A.8 and A.9 that

$\displaystyle\left\|\widetilde{M}-M\right\|_{\infty}$
$\displaystyle=\left\|\widetilde{M}-\breve{X}\breve{Z}^{\top}\right\|_{\infty}+\left\|\breve{X}\breve{H}-X\right\|_{2,\infty}\left\|\breve{H}^{\top}\breve{Z}^{\top}\right\|_{2,\infty}+\left\|X\right\|_{2,\infty}\left\|\breve{Z}\breve{H}-Z\right\|_{2,\infty}$
$\displaystyle\lesssim\frac{\lambda}{\max\\{N^{5},T^{5}\\}}+\frac{\sigma\mu
r^{\frac{3}{2}}\kappa^{2}\sqrt{\max\\{\log N,\log
T\\}}}{\sqrt{\min\\{N,T\\}}}$ $\displaystyle\lesssim\frac{\sigma\mu
r^{\frac{3}{2}}\kappa^{2}\sqrt{\max\\{\log N,\log
T\\}}}{\sqrt{\min\\{N,T\\}}},$

where $\lambda=C_{\lambda}\sigma\sqrt{\max\\{N,T\\}}$ for some constant
$C_{\lambda}>0$, since we have by Lemma A.8

$\displaystyle\left\|X\right\|_{2,\infty}\left\|\breve{Z}\breve{H}-Z\right\|_{2,\infty},\left\|\breve{X}\breve{H}-X\right\|_{2,\infty}\left\|\breve{H}^{\top}\breve{Z}^{\top}\right\|_{2,\infty}$
$\displaystyle\lesssim\sqrt{r}\kappa\left(\frac{\sigma\sqrt{\max\\{N\log
N,T\log
T\\}}}{\psi_{\min}}+\frac{\lambda}{\psi_{\min}}\right)\left\|X\right\|_{2,\infty}\left\|Z\right\|_{2,\infty}$
$\displaystyle\lesssim\frac{\sigma\mu
r^{\frac{3}{2}}\kappa^{2}\sqrt{\max\\{\log N,\log
T\\}}}{\sqrt{\min\\{N,T\\}}}.\ \ \square$

Proofs of Corollaries 2.2 and 2.3.

First, we prove Corollary 2.2. By Assumption (iii), we know $N_{0}\leq
N_{l}=N_{0}+|\mathcal{G}_{l}|\leq 2N_{0}$. Then, we have by Assumptions (iii)
and (iv)

$\displaystyle\lambda_{\min}\left(\frac{1}{N_{l}}\sum_{i\leq
N_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)$
(B.1) $\displaystyle\ \ \geq\lambda_{\min}\left(\frac{1}{N_{l}}\sum_{i\leq
N_{0}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)-\left\|\frac{1}{N_{l}}\sum_{i\in\mathcal{G}_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right\|$
$\displaystyle\ \ \geq\frac{c}{2}-\frac{\mu
r|\mathcal{G}_{l}|}{N_{l}}\geq\frac{c}{4}.$

Similarly, we can have $\lambda_{\max}\left(\frac{1}{N_{l}}\sum_{i\leq
N_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq
4C$. Then, using Lemma B.3, we can have
$\mu_{l}\lesssim\mu\kappa^{\frac{1}{2}}$, $\kappa_{l}\lesssim\kappa$, and
$\psi_{O,\min}\asymp\psi_{l,\min}$, where $\mu_{l}$ and $\kappa_{l}$ are the
incoherence parameter and condition number of the submatrix $M_{l}$, and
$\psi_{l,\min}$ is the smallest nonzero singular value of $M_{l}$. Using these
relations, we can check that submatrix $M_{l}$ satisfies Assumptions A.1 \-
A.4 under the assumptions of Corollary 2.2. Then, we can derive the bound of
$\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$ by the same way as in the
proof of Theorem 2.1 from Lemmas A.8 and A.9. In addition, we replace
$\mu_{l}$ and $\kappa_{l}$ in the bound of
$\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$ with
$\mu\kappa^{\frac{1}{2}}$ and $\kappa$ using the above relations from Lemma
B.3, and replace $N_{l}$ with $N_{0}$ since $N_{0}\leq
N_{l}=N_{0}+|\mathcal{G}_{l}|\leq 2N_{0}$. Lastly, the bound of
$\left\|\widetilde{M}-M\right\|_{\infty}$ trivially follows from that of
$\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$ since any entry of $M$ is
included in at least one of $M_{l}$.

Symmetrically, we can prove Corollary 2.3 using the same way. So, we omit the
proof. $\square$

Proof of Corollary 2.4

It is a simple extension of Corollary 2.2 and the proof is same as that of
Corollary 2.2. The only difference is that the dimension of the submatrix
$M_{l}$ becomes $N_{l}\times T_{l}$ where $N_{l}=N_{0}+|\mathcal{G}_{l}|$ and
$T_{l}=T_{0}+1$. Here, we have from Assumption (iv) that

$\displaystyle\lambda_{\min}\left(\frac{1}{T_{l}}\sum_{t\leq
T_{l}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)$
$\displaystyle\geq\lambda_{\min}\left(\frac{1}{T_{l}}\sum_{t\leq
T_{0}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)-\left\|\frac{1}{T_{l}}\left(\sqrt{T}v_{t_{o}}\right)\left(\sqrt{T}v_{t_{o}}\right)^{\top}\right\|$
$\displaystyle\geq\frac{c}{2}-\frac{\mu r}{T_{l}}\geq\frac{c}{4}$ (B.2)

and $\lambda_{\max}\left(\frac{1}{T_{l}}\sum_{t\leq
T_{l}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq
4C$. Then, by (B.1) and (B.1), we can exploit Lemma B.3. In the bounds of
$\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$, we replace $\mu_{l}$ and
$\kappa_{l}$ with $\mu\kappa^{\frac{1}{2}}$ and $\kappa$ using the results of
Lemma B.3, and replace $N_{l}$ and $T_{l}$ with $N_{0}$ and $T_{0}$ since
$N_{0}\leq N_{l}=N_{0}+|\mathcal{G}_{l}|\leq 2N_{0}$ and $T_{l}=T_{0}+1$. In
addition, the bound of $\left\|\widetilde{M}-M\right\|_{\infty}$ trivially
follows from that of $\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$.
$\square$

Proof of Corollary 2.5

In the case of the estimation of missing entries in the matrix
$M_{d,d^{\prime}}$, the dimension of each submatrix is $N_{l}\times T_{l}$
where $N_{l}=N_{d^{\prime}}+|\mathcal{G}_{l}|$ and $T_{l}=T_{d}+1$. By the
similar way to (B.1) and (B.1), we can show

$\displaystyle\frac{c}{4}\leq\lambda_{\min}\left(\frac{1}{N_{l}}\sum_{i\leq
N_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq\lambda_{\max}\left(\frac{1}{N_{l}}\sum_{i\leq
N_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq
4C,$
$\displaystyle\frac{c}{4}\leq\lambda_{\min}\left(\frac{1}{T_{l}}\sum_{t\leq
T_{l}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq\lambda_{\max}\left(\frac{1}{T_{l}}\sum_{t\leq
T_{l}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq
4C.$

Hence, we can exploit Lemma B.3 to replace $\mu\kappa^{\frac{1}{2}}$,
$\kappa$, $\psi_{\min,O_{d,d^{\prime}}}$ with $\mu_{l}$, $\kappa_{l}$,
$\psi_{\min,l}$ and replace $N_{d}$ and $T_{d^{\prime}}$ with $N_{l}$ and
$T_{l}$ in our conditions and then, we can check that for each $l$,
Assumptions A.1 \- A.4 are satisfied. Then, we derive the bounds of
$\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$ by the same way as in the
proof of Theorem 2.1 using Lemmas A.8 and A.9. The bound of
$\left\|\widetilde{M}_{d,d^{\prime}}-M_{d,d^{\prime}}\right\|_{\infty}$
trivially follows from that of
$\left\|\widetilde{M}_{l}-M_{l}\right\|_{\infty}$. $\square$

###  B.2 Proofs for Section 3

Proof of Theorem 3.1

First of all, by using the fact from Lemma B.3 that
$\mu_{l}\lesssim\mu\kappa^{\frac{1}{2}}$, $\kappa_{l}\lesssim\kappa$,
$\psi_{\min,l}\asymp\psi_{\min,O}$ and the relations that $N_{0}\leq
N_{l}=N_{0}+|\mathcal{G}_{l}|\leq 2N_{0}$ and $T_{l}=T_{0}+1$ w.h.p., we can
check that Assumptions A.1 \- A.4 are satisfied for each submatrix. Denote by
$l(i)$ the group $0\leq l\leq L$ where the unit $i$ is included in. That is,
$i\in\mathcal{G}_{l(i)}$. Then, by Proposition A.4, we have the following
decomposition:

$\displaystyle\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}(\widehat{m}_{it_{0}}-m_{{it_{0}}})$
$\displaystyle=\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}X_{l(i),i}^{\top}\left(\sum_{j\leq
N_{0}}X_{l(i),j}X_{l(i),j}^{\top}\right)^{-1}\sum_{j\leq
N_{0}}\epsilon_{jt_{o}}X_{l(i),j}}_{\coloneqq A}$
$\displaystyle+\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}Z_{l(i),t_{o}}^{\top}\left(\sum_{s\leq
T_{0}}Z_{l(i),s}Z_{l(i),s}^{\top}\right)^{-1}\sum_{s\leq
T_{0}}\epsilon_{is}Z_{l(i),s}}_{\coloneqq B}$
$\displaystyle+\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}_{0}}Z_{0,t_{o}}^{\top}\left[\left(\sum_{s\leq
T_{0}}Z_{0,s}Z_{0,s}^{\top}+Z_{0,t_{0}}Z_{0,t_{0}}^{\top}\right)^{-1}\left(\sum_{s\leq
T_{0}}\epsilon_{is}Z_{0,s}+\epsilon_{it_{0}}Z_{0,t_{0}}\right)-\left(\sum_{s\leq
T_{0}}Z_{0,s}Z_{0,s}^{\top}\right)^{-1}\sum_{s\leq
T_{0}}\epsilon_{is}Z_{0,s}\right]}_{\coloneqq\mathcal{R}_{1}}$
$\displaystyle+\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\mathcal{R}_{l(i),i}^{M}}_{\coloneqq\mathcal{R}_{2}}.$

Here, $(X_{l},Z_{l})=(U_{l}D_{l}^{\frac{1}{2}},V_{l}D_{l}^{\frac{1}{2}})$
where $U_{l}D_{l}V_{l}^{\top}$ is the SVD of $M_{l}$. $X_{l,j}$ is the
transpose of the row of $X_{l}$ corresponding to the unit $j$ and $Z_{l,s}$ is
the transpose of the row of $Z_{l}$ corresponding to the time period $s$.
Because for each $0\leq 1\leq L$, there is an invertible matrix $H_{l}$ such
that $u_{j}=H_{l}X_{l,j}$, we have

$\displaystyle
A=\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}u_{i}^{\top}\left(\sum_{j\leq
N_{o}}u_{j}u_{j}^{\top}\right)^{-1}\sum_{j\leq N_{o}}\epsilon_{jt_{0}}u_{j}.$

Similarly, we can show that

$B=\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\sum_{s\leq T_{0}}\epsilon_{is}v_{s}.$

Note that

$\displaystyle\left\|a_{j}\right\|\coloneqq\left\|\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}u_{i}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}u_{j}\right\|\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\max_{i}||u_{i}||^{2}\psi_{\min}^{-1}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\frac{\mu
r}{N_{0}}.$

Hence, we have

$\left\|\sum_{j\leq
N_{0}}\mathbb{E}[a_{j}^{4}\epsilon_{jt_{0}}^{4}]\right\|=\left\|\sum_{j\leq
N_{0}}\mathbb{E}[\epsilon_{jt_{0}}^{4}]a_{j}^{4}\right\|\leq\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\frac{\mu^{4}r^{4}}{N_{0}^{3}}.$

Then, for any $q>0$, we have by Cauchy-Schwarz and Markov inequalities that

$\displaystyle\text{Var}(A)^{-1}\sum_{j\leq
N_{0}}\mathbb{E}[(a_{j}\epsilon_{jt_{0}})^{2}1_{\\{|a_{j}\epsilon_{jt_{0}}|>q\text{Var}(A)^{1/2}\\}}]$
$\displaystyle\leq\frac{1}{\text{Var}(A)q}\sqrt{\sum_{j\leq
N_{0}}\mathbb{E}[(a_{j}\epsilon_{jt_{0}})^{4}]}\lesssim\frac{\mu^{2}r^{2}}{N_{0}^{\frac{1}{2}}}=o_{p}(1)$

since

$\text{Var}(A)=\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}}\geq
c\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}N_{0}^{-1}$

for some constant $c>0$. Then, we have by Lindeberg theorem that

$\text{Var}(A)^{-1/2}A\overset{D}{\longrightarrow}\mathcal{N}(0,1).$

In the same way, we can derive

$\text{Var}(B)^{-1/2}B\overset{D}{\longrightarrow}\mathcal{N}(0,1)$

where
$\text{Var}(B)=\mathcal{V}_{\mathcal{G}}^{-1}\frac{\sigma^{2}}{|\mathcal{G}|}v_{t_{0}}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}v_{t_{0}}$. Then, because $A$ and $B$ are
independent, by using the similar assertion in the proof of Theorem 3 of Bai,
(2003), we have

$\displaystyle
A+B=\text{Var}(A)^{1/2}(\text{Var}(A)^{-1/2}A)+\text{Var}(B)^{1/2}(\text{Var}(B)^{-1/2}B)\overset{D}{\longrightarrow}\mathcal{N}\left(0,1\right)$

since $\text{Var}(A)+\text{Var}(B)=1$.

In addition, note that the difference between $\sum_{s\leq
T_{0}}Z_{0,s}Z_{0,s}^{\top}+Z_{0,t_{0}}Z_{0,t_{0}}^{\top}$ and $\sum_{s\leq
T_{0}}Z_{0,s}Z_{0,s}^{\top}$ is just one element
$Z_{0,t_{0}}Z_{0,t_{0}}^{\top}$, and that between $\sum_{s\leq
T_{0}}\epsilon_{is}Z_{0,s}+\epsilon_{it_{0}}Z_{0,t_{0}}$ and $\sum_{s\leq
T_{0}}\epsilon_{is}Z_{0,s}$ is just $\epsilon_{it_{0}}Z_{0,t_{0}}$. Hence,
without difficulty, we can show that
$\left\|\mathcal{R}_{1}\right\|=o_{p}(1)$. Moreover, note that since

$\mathcal{V}_{\mathcal{G}}=\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}}+\frac{\sigma^{2}}{|\mathcal{G}|}v_{t_{0}}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}v_{t_{0}}\geq
c\sigma^{2}\left(\frac{1}{N_{0}}+\frac{1}{|\mathcal{G}|T_{0}}\right)$

for some constant $c>0$, we have

$\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\lesssim\min\\{\sqrt{N_{0}},\sqrt{|\mathcal{G}|T_{0}}\\}/\sigma.$

Hence, by Proposition A.4, we have with probability at least
$1-O(\min\\{N_{0}^{-7},T_{0}^{-7}\\})$ that

$\displaystyle\left\|\mathcal{R}_{2}\right\|$
$\displaystyle\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\max_{0\leq l\leq
L}\max_{i\in\mathcal{G}_{l}}||\mathcal{R}_{l,i}^{M}||$ $\displaystyle\leq
C_{M}^{\prime}\left(\max_{0\leq l\leq
L}\frac{\sigma\kappa_{l}^{5}\mu_{l}r\min\\{\sqrt{N_{0}},\sqrt{|\mathcal{G}|T_{0}}\\}\max\\{N_{l}\log
N_{l},T_{l}\log T_{l}\\}}{\psi_{\min,l}\min\\{N_{l},T_{l}\\}}\right.$
$\displaystyle\quad+\max_{0\leq l\leq
L}\frac{\kappa_{l}^{4}\mu_{l}^{2}r^{2}\min\\{\sqrt{N_{0}},\sqrt{|\mathcal{G}|T_{0}}\\}\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log
T_{l}}\\}}{\min\\{N_{l}^{\frac{3}{2}},T_{l}^{\frac{3}{2}}\\}}$
$\displaystyle\quad+\left.\max_{l\in[L]}\frac{\mu_{l}^{2}r^{2}\kappa_{l}^{3}|\mathcal{G}_{l}|\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log T_{l}}\\}}{\sqrt{N_{l}}\min\\{N_{l},T_{l}\\}}\right)$

for an absolute constant $C_{M}^{\prime}>0$. Then, by Assumptions (i), (ii),
and (iii) with the relations that $\mu_{l}\lesssim\mu\kappa^{\frac{1}{2}}$,
$\kappa_{l}\lesssim\kappa$, $N_{0}\leq N_{l}\leq 2N_{0}$ and $T_{l}=T_{0}+1$
w.h.p., we have $\left\|\mathcal{R}_{2}\right\|=o_{p}(1)$. Therefore,

$\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\frac{1}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}(\widehat{m}_{it_{0}}-m_{{it_{0}}})\overset{D}{\longrightarrow}\mathcal{N}(0,1).\
\ \square$

Proof of Theorem 3.2

By using the fact from Lemma B.3 that
$\mu_{l}\lesssim\mu\kappa^{\frac{1}{2}}$, $\kappa_{l}\lesssim\kappa$,
$\psi_{\min,l}\asymp\psi_{\min,O_{d_{l}}}$, and the relations that $N_{0}\leq
N_{l}=N_{0}+|\mathcal{G}_{l}|\leq 2N_{0}$ and $T_{l}=T_{d_{l}}+1$ w.h.p., we
can check that Assumptions A.1 \- A.4 are satisfied for each $N_{l}\times
T_{l}$ submatrix $M_{l}$. Then, by Proposition A.4, we have the following
decomposition:

$\displaystyle\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}(\widehat{m}_{it_{o}}-m_{{it_{o}}})$
$\displaystyle=\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}X_{l(i),i}^{\top}\left(\sum_{j\leq
N_{0}}X_{l(i),j}X_{l(i),j}^{\top}\right)^{-1}\sum_{j\leq
N_{0}}\epsilon_{jt_{o}}X_{l(i),j}}_{\coloneqq A}$ $\displaystyle\ \
+\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}Z_{l(i),t_{o}}^{\top}\left(\sum_{s\leq
T_{d_{l(i)}}}Z_{l(i),s}Z_{l(i),s}^{\top}\right)^{-1}\sum_{s\leq
T_{d_{l(i)}}}\epsilon_{is}Z_{l(i),s}}_{\coloneqq
B}+\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\mathcal{R}_{l(i),i}^{M}$
$\displaystyle=\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}u_{i}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\sum_{j\leq
N_{0}}\epsilon_{jt_{o}}u_{j}}_{=A}$ $\displaystyle\ \
+\underbrace{\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{d_{l(i)}}}v_{s}v_{s}^{\top}\right)^{-1}\sum_{s\leq
T_{d_{l(i)}}}\epsilon_{is}v_{s}}_{=B}+\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\mathcal{R}_{l(i),i}^{M},$

with the convention that $d_{0}=0$. Then, we can represent $A+B$ as

$\displaystyle A+B=\sum_{j\leq N}\sum_{s\leq T}\underbrace{\left(P1_{\\{j\leq
N_{0},s=t_{o}\\}}+\sum_{0\leq l\leq L}Q_{l}1_{\\{j\in\mathcal{G}_{l},s\in
T_{d_{l}}\\}}\right)\epsilon_{js}}_{\coloneqq\mathcal{Y}_{js}},$
$\displaystyle\text{where}\ \
P=\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}u_{i}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}u_{j},\ \
Q_{l}=\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{d_{l}}}v_{s}v_{s}^{\top}\right)^{-1}v_{s}.$

Because $\\{\epsilon_{js}\\}_{j\leq N,s\leq T}$ is independent across $j$ and
$s$, $A+B$ is a sum of independent random variables and so, we can use
Lindeberg CLT. To check the Lindeberg condition, we first bound
$\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{4}]$. Note that

$\displaystyle\left\|P\right\|=\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\left\|\sum_{i\in\mathcal{G}}u_{i}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}u_{j}\right\|\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\max_{i}||u_{i}||^{2}\psi_{\min}^{-1}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)\lesssim\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\frac{\mu
r}{N_{0}}.$

Hence, we have

$\displaystyle\left\|\sum_{j\leq N}\sum_{s\leq T}\mathbb{E}[P^{4}1_{\\{j\leq
N_{0},s=t_{o}\\}}\epsilon_{js}^{4}]\right\|=\left\|\sum_{j\leq
N_{0}}\sum_{s=t_{o}}\mathbb{E}[\epsilon_{js}^{4}]P^{4}\right\|\lesssim\sigma^{4}N_{0}||P||^{4}\leq\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\frac{\mu^{4}r^{4}}{N_{0}^{3}}.$

In addition, because $1_{\\{j\in\mathcal{G}_{l^{\prime}},s\leq
T_{d_{l^{\prime}}}\\}}1_{\\{j\in\mathcal{G}_{l},s\leq T_{d_{l}}\\}}=0$ when
$l\neq l^{\prime}$, we have

$\displaystyle\sum_{j\leq N}\sum_{s\leq T}\mathbb{E}\left[\left(\sum_{0\leq
l\leq L}Q_{l}1_{\\{j\in\mathcal{G}_{l},s\leq
T_{d_{l}}\\}}\right)^{4}\epsilon_{js}^{4}\right]$ $\displaystyle=\sum_{j\leq
N}\sum_{s\leq T}\sum_{0\leq l\leq L}Q_{l}^{4}1_{\\{j\in\mathcal{G}_{l},s\leq
T_{d_{l}}\\}}\mathbb{E}\left[\epsilon_{js}^{4}\right]$
$\displaystyle=\sum_{0\leq l\leq L}\sum_{j\leq N}\sum_{s\leq
T}Q_{l}^{4}1_{\\{j\in\mathcal{G}_{l},s\leq
T_{d_{l}}\\}}\mathbb{E}\left[\epsilon_{js}^{4}\right].$

For each $l$, we have

$\sum_{j\in\mathcal{G}_{l}}\sum_{s\leq
T_{d_{l}}}Q_{l}^{4}\mathbb{E}\left[\epsilon_{js}^{4}\right]\lesssim\frac{|\mathcal{G}_{l}|}{|\mathcal{G}|}\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\frac{1}{|\mathcal{G}|^{3}}\frac{\mu^{4}r^{4}}{T_{d_{l}}^{3}}\leq\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\frac{1}{(L+1)^{3}}\frac{\mu^{4}r^{4}}{T_{d_{l}}^{3}}$

because

$||Q_{l}||\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\frac{1}{|\mathcal{G}|}\max_{t}||v_{t}||^{2}\psi_{\min}^{-1}\left(\sum_{s\leq
T_{d_{l}}}v_{s}v_{s}^{\top}\right)\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\frac{1}{|\mathcal{G}|}\frac{\mu
r}{T_{d_{l}}}.$

Then, we have

$\displaystyle\sum_{0\leq l\leq L}\sum_{j\in\mathcal{G}_{l}}\sum_{s\leq
T_{d_{l}}}Q_{l}^{4}\mathbb{E}\left[\epsilon_{js}^{4}\right]$
$\displaystyle\lesssim\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\mu^{4}r^{4}\frac{1}{(L+1)^{3}}\sum_{0\leq
l\leq L}\frac{1}{T_{d_{l}}^{3}}$
$\displaystyle\leq\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\mu^{4}r^{4}\left(\frac{1}{L+1}\sum_{0\leq
l\leq L}\frac{1}{T_{d_{l}}}\right)^{3}$
$\displaystyle\lesssim\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\mu^{4}r^{4}\bar{T}^{-3}$

where $\bar{T}^{-1}\coloneqq\frac{1}{L+1}\sum_{0\leq l\leq
L}{T_{d_{l}}}^{-1}$. Therefore, we can reach

$\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{4}]\lesssim\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\frac{\mu^{4}r^{4}}{N_{0}^{3}}+\mathcal{V}_{\mathcal{G}}^{-2}\sigma^{4}\mu^{4}r^{4}\bar{T}^{-3}.$

Then, for any $q>0$, we have by Cauchy-Schwarz and Markov inequalities with
Claim B.1,

$\displaystyle\text{Var}(A+B)^{-1}\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{2}1_{\\{|\mathcal{Y}_{js}|>q\text{Var}(A+B)^{1/2}\\}}]\leq\frac{1}{\text{Var}(A+B)q}\sqrt{\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{4}]}\lesssim\frac{\mu^{2}r^{2}}{N_{0}^{\frac{1}{2}}}+\frac{\mu^{2}r^{2}N_{0}}{\bar{T}^{\frac{3}{2}}}.$

Because $\bar{T}\geq\min_{l}T_{d_{l}}\coloneqq T_{\min}$, we have
$\frac{\mu^{2}r^{2}}{N_{0}^{1/2}}+\frac{\mu^{2}r^{2}N_{0}}{\bar{T}^{3/2}}=o_{p}(1)$
by the Assumption (ii). Hence, the Lindeberg condition is satisfied.

######  Claim B.1.

(i) $\mathcal{V}_{\mathcal{G}}^{-1}\lesssim\frac{N_{0}}{\sigma^{2}}$ and (ii)
$\text{Var}(A+B)\overset{\mathbb{P}}{\longrightarrow}1$.

Therefore, by using the Lindeberg CLT with Claim B.1 (ii), we have
$A+B\overset{D}{\longrightarrow}\mathcal{N}(0,1)$. Next, we show that
$\left\|\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\mathcal{R}_{l(i),i}^{M}\right\|=o_{p}(1)$.
Since
$\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\lesssim\frac{\sqrt{N_{0}}}{\sigma}\asymp\frac{\sqrt{N_{l}}}{\sigma}$
for all $l$, we have by Proposition A.4 with probability at least
$1-O(\min\\{N_{0}^{-7},T_{\min}^{-7}\\})$ that

$\displaystyle\left\|\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\mathcal{R}_{l(i),i}^{M}\right\|$
$\displaystyle\leq\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\max_{0\leq l\leq
L}\max_{i\in\mathcal{G}_{l}}||\mathcal{R}_{l,i}^{M}||$ $\displaystyle\leq
C_{M}^{\prime}\left(\max_{0\leq l\leq
L}\frac{\sigma\kappa_{l}^{5}\mu_{l}r\sqrt{N_{l}}\max\\{N_{l}\log
N_{l},T_{l}\log T_{l}\\}}{\psi_{\min,l}\min\\{N_{l},T_{l}\\}}\right.$
$\displaystyle\qquad\qquad+\max_{0\leq l\leq
L}\frac{\kappa_{l}^{4}\mu_{l}^{2}r^{2}\sqrt{N_{l}}\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log
T_{l}}\\}}{\min\\{N_{l}^{\frac{3}{2}},T_{l}^{\frac{3}{2}}\\}}$
$\displaystyle\left.\qquad\qquad+\max_{1\leq l\leq
L}\frac{\mu_{l}^{2}r^{2}\kappa_{l}^{3}|\mathcal{G}_{l}|\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log T_{l}}\\}}{\sqrt{N_{l}}\min\\{N_{l},T_{l}\\}}\right)$

for an absolute constant $C_{M}^{\prime}>0$. Then, by Assumptions (i), (ii),
and (iii) with the relations that $\mu_{l}\lesssim\mu\kappa^{\frac{1}{2}}$,
$\kappa_{l}\lesssim\kappa$, $N_{0}\leq N_{l}\leq 2N_{0}$ and
$T_{l}=T_{d_{l}}+1$, we have
$\left\|\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\mathcal{R}_{l(i),i}^{M}\right\|=o_{p}(1)$.
Therefore,

$\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}\frac{1}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}(\widehat{m}_{it_{o}}-m_{{it_{o}}})\overset{D}{\longrightarrow}\mathcal{N}(0,1).\
\ \square$

###### Proof of Claim B.1.

(i) We have $\mathcal{V}_{\mathcal{G}}^{-1}\lesssim\frac{N_{0}}{\sigma^{2}}$,
because for some constant $c>0$,

$\displaystyle\mathcal{V}_{\mathcal{G}}$
$\displaystyle\geq\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}}\geq\sigma^{2}\left\|\bar{u}_{\mathcal{G}}\right\|^{2}\psi_{\min}\left(\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\right)\geq c\frac{\sigma^{2}}{N_{0}}.$

(ii) A simple calculation shows that

$\displaystyle\text{Var}(A)=\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}},\ \
\text{Var}(B)=\mathcal{V}_{\mathcal{G}}^{-1}\frac{\sigma^{2}}{|\mathcal{G}|}\sum_{0\leq
l\leq L}\alpha_{l}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{d_{l}}}v_{s}v_{s}^{\top}\right)^{-1}v_{t_{o}}$

where $\alpha_{l}=\frac{|\mathcal{G}_{l}|}{|\mathcal{G}|}$. Hence, we have
$\text{Var}(A)+\text{Var}(B)=1$. In addition, note that
$\text{Cov}(A,B)=\text{Cov}(A,B^{(t_{o})})$ where

$B^{(t_{o})}\coloneqq\frac{\mathcal{V}_{\mathcal{G}}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{j\in\mathcal{G}_{0}}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\epsilon_{jt_{o}}v_{t_{o}}.$

Then, we have

$\displaystyle\left\|\text{Cov}(A,B^{(t_{o})})\right\|$
$\displaystyle=\left\|\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}v_{t_{o}}\bar{u}_{G}^{\top}\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\frac{1}{|\mathcal{G}|}\sum_{j\in\mathcal{G}_{0}}u_{j}\right\|$
$\displaystyle\leq\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}\max_{s}\left\|v_{s}\right\|^{2}\max_{j}\left\|u_{j}\right\|^{2}\left\|\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\right\|\left\|\left(\sum_{j\leq
N_{0}}u_{j}u_{j}^{\top}\right)^{-1}\right\|$
$\displaystyle\leq\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}\frac{\mu^{2}r^{2}}{N_{0}T_{0}}\overset{\mathbb{P}}{\longrightarrow}0.$

Hence, we have
$\text{Var}(A+B)=\text{Var}(A)+\text{Var}(B)+2\text{Cov}(A,B)\overset{\mathbb{P}}{\longrightarrow}1$.
∎

Proof of Corollary 3.3

From the proof of Claim B.1 (ii), we know that
$\mathcal{V}_{\mathcal{G}}=\text{Var}(\tilde{A})+\text{Var}(\tilde{B})$ where
$\widetilde{A}=\mathcal{V}_{\mathcal{G}}^{\frac{1}{2}}A$ and
$\widetilde{B}=\mathcal{V}_{\mathcal{G}}^{\frac{1}{2}}B$. Note that

$\displaystyle\widetilde{A}$ $\displaystyle=\sum_{j\leq
N_{0}}\epsilon_{jt_{o}}\left(\frac{1}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}u_{i}^{\top}\left(\sum_{k\leq
N_{0}}u_{k}u_{k}^{\top}\right)^{-1}u_{j}\right)=\sum_{j\leq
N_{0}}\epsilon_{jt_{o}}\left(\sum_{0\leq l\leq
L}\frac{|\mathcal{G}_{l}|}{|\mathcal{G}|}\frac{1}{|\mathcal{G}_{l}|}\sum_{i\in\mathcal{G}_{l}}u_{i}^{\top}\left(\sum_{k\leq
N_{0}}u_{k}u_{k}^{\top}\right)^{-1}u_{j}\right).$

Hence, we have

$\displaystyle\text{Var}(\tilde{A})$ $\displaystyle=\sigma^{2}\sum_{j\leq
N_{0}}\left(\sum_{0\leq l\leq
L}\alpha_{l}\bar{u}_{\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}u_{k}u_{k}^{\top}\right)^{-1}u_{j}\right)^{2}=\sigma^{2}\sum_{j\leq
N_{0}}\left(\sum_{0\leq l\leq
L}\alpha_{l}\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)^{2},$

where
$\bar{X}_{l,\mathcal{G}_{l}}=\frac{1}{|\mathcal{G}_{l}|}\sum_{i\in\mathcal{G}_{l}}X_{l,i}$.
In addition, as noted in the proof of Claim B.1 (ii), we have

$\text{Var}(\tilde{B})=\frac{\sigma^{2}}{|\mathcal{G}|}\sum_{0\leq l\leq
L}\alpha_{l}Z_{l,t_{o}}^{\top}\left(\sum_{s\in
T_{d_{l}}}Z_{l,s}Z_{l,s}^{\top}\right)^{-1}Z_{l,t_{o}}.$

First, we show that

$\mathcal{V}_{\mathcal{G}}^{-1}\left\|\widehat{\text{Var}}(\tilde{A})-\text{Var}(\tilde{A})\right\|=o_{p}(1)$

where

$\widehat{\text{Var}}(\tilde{A})=\widehat{\sigma}^{2}\sum_{j\leq
N_{0}}\left(\sum_{0\leq l\leq
L}\alpha_{l}\widehat{\bar{X}}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\right)^{-1}\widehat{X}_{l,j}\right)^{2}.$

Note that

$\displaystyle\left\|\widehat{\text{Var}}(\tilde{A})-\text{Var}(\tilde{A})\right\|$
$\displaystyle\lesssim\left|\widehat{\sigma}^{2}-\sigma^{2}\right|\sum_{j\leq
N_{0}}\left(\sum_{0\leq l\leq
L}\alpha_{l}\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)^{2}$ $\displaystyle\ \
+\sigma^{2}\sum_{j\leq N_{0}}\left\|\sum_{0\leq l\leq
L}\alpha_{l}\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right\|$
$\displaystyle\qquad\times\left\|\sum_{0\leq l\leq
L}\alpha_{l}\left(\widehat{\bar{X}}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\right)^{-1}\widehat{X}_{l,j}-\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)\right\|.$

Because

$\left\|\sum_{0\leq l\leq
L}\alpha_{l}\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right\|\leq\max_{l}\left\|\bar{u}_{\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}u_{k}u_{k}^{\top}\right)^{-1}u_{j}\right\|\leq\frac{\mu r}{N_{0}},$

we know by Claims B.1 and B.2 that

$\displaystyle\mathcal{V}_{\mathcal{G}}^{-1}\left|\widehat{\sigma}^{2}-\sigma^{2}\right|\sum_{j\leq
N_{0}}\left(\sum_{0\leq l\leq
L}\alpha_{l}\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)^{2}$
$\displaystyle\quad\lesssim\frac{\kappa^{5/2}\mu^{3}r^{2}\max\\{\sqrt{N_{0}\log
N_{0}},\sqrt{T_{0}\log T_{0}}\\}}{\min\\{N_{0},T_{0}\\}}=o_{p}(1).$

######  Claim B.2.

$\left|\widehat{\sigma}^{2}-\sigma^{2}\right|\lesssim\sigma^{2}\frac{\kappa^{5/2}\mu
r\max\\{\sqrt{N_{0}\log N_{0}},\sqrt{T_{0}\log
T_{0}}\\}}{\min\\{N_{0},T_{0}\\}}.$

Next, we want to bound the following term:

$\displaystyle\left\|\sum_{0\leq l\leq
L}\alpha_{l}\left(\widehat{\bar{X}}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\right)^{-1}\widehat{X}_{l,j}-\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)\right\|$ $\displaystyle\
\
\leq\max_{l}\left\|\widehat{\bar{X}}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\right)^{-1}\widehat{X}_{l,j}-\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right\|$ $\displaystyle\ \
\leq\max_{l}\left\|\widehat{X}_{l}\widehat{H}_{l}-X_{l}\right\|_{2,\infty}\left\|\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right\|$
$\displaystyle\quad+\max_{l}\left\|X_{l}\right\|_{2,\infty}^{2}\left\|\left(\sum_{k\leq
N_{0}}\widehat{H}_{l}^{\top}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\widehat{H}_{l}\right)^{-1}-\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}\right\|.$

As noted in the proof of Proposition A.4, we have

$\left\|\widehat{X}_{l}\widehat{H}_{l}-X_{l}\right\|_{2,\infty}\left\|X_{l}\right\|_{2,\infty}\lesssim\sigma\frac{\kappa_{l}^{2}\mu_{l}r\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log T_{l}}\\}}{\min\\{N_{l},T_{l}\\}}.$

In addition, because

$\left\|\left(\sum_{k\leq
N_{0}}u_{l,k}u_{l,k}^{\top}\right)^{-1}\right\|\leq\left\|\left(\sum_{k\leq
N_{0}}u_{l,k}u_{l,k}^{\top}\right)^{-1}-I_{r}\right\|+1=\left\|\left(\sum_{k\leq
N_{0}}u_{l,k}u_{l,k}^{\top}\right)^{-1}-(U_{l}^{\top}U_{l})^{-1}\right\|+1$

and

$\left\|\left(\sum_{k\leq
N_{0}}u_{l,k}u_{l,k}^{\top}\right)^{-1}-(U_{l}^{\top}U_{l})^{-1}\right\|\lesssim\left\|\sum_{k\in\mathcal{G}_{l}}u_{l,k}u_{l,k}^{\top}\right\|\leq|\mathcal{G}_{l}|\frac{\mu_{l}r}{N_{l}}\ll
1,$

we have

$\left\|\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}\right\|\leq\psi_{\min,l}^{-1}\left\|\left(\sum_{k\leq
N_{0}}u_{l,k}u_{l,k}^{\top}\right)^{-1}\right\|\lesssim\psi_{\min,l}^{-1}.$

Here, $U_{l}$ is the left singular vector of $M_{l}$ and $u_{l,k}^{\top}$ is
the $k$-th row of it. Hence, we obtain

$\displaystyle\left\|\left(\sum_{k\leq
N_{0}}\widehat{H}_{l}^{\top}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\widehat{H}_{l}\right)^{-1}-\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}\right\|$ $\displaystyle\ \
\lesssim\left\|\sum_{k\leq
N_{0}}\widehat{H}_{l}^{\top}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\widehat{H}_{l}-\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right\|\left\|\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}\right\|^{2}$ $\displaystyle\ \
\lesssim\sigma\frac{\kappa_{l}^{2}\mu_{l}rN_{0}\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log T_{l}}\\}}{\psi_{\min,l}^{2}\min\\{N_{l},T_{l}\\}},$

and

$\displaystyle\left\|\sum_{0\leq l\leq
L}\alpha_{l}\left(\widehat{\bar{X}}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\right)^{-1}\widehat{X}_{l,j}-\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)\right\|$ $\displaystyle\
\ \lesssim\max_{0\leq l\leq
L}\sigma\frac{\kappa_{l}^{3}\mu_{l}^{2}r^{2}N_{0}\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log T_{l}}\\}}{N_{l}\min\\{N_{l},T_{l}\\}\psi_{\min,l}}.$

Then, we have

$\displaystyle\mathcal{V}_{\mathcal{G}}^{-1}\sigma^{2}\sum_{j\leq
N_{0}}\left\|\sum_{0\leq l\leq
L}\alpha_{l}\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right\|$
$\displaystyle\qquad\qquad\qquad\times\left\|\sum_{0\leq l\leq
L}\alpha_{l}\left(\widehat{\bar{X}}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}\widehat{X}_{l,k}\widehat{X}_{l,k}^{\top}\right)^{-1}\widehat{X}_{l,j}-\bar{X}_{l,\mathcal{G}_{l}}^{\top}\left(\sum_{k\leq
N_{0}}X_{l,k}X_{l,k}^{\top}\right)^{-1}X_{l,j}\right)\right\|$ $\displaystyle\
\ \lesssim\max_{0\leq l\leq
L}\frac{\sigma}{\psi_{\min,l}}\frac{\kappa_{l}^{3}\mu_{l}^{3}r^{3}N_{l}\max\\{\sqrt{N_{l}\log
N_{l}},\sqrt{T_{l}\log T_{l}}\\}}{\min\\{N_{l},T_{l}\\}}=o_{p}(1)$

by Assumptions (i), (ii), and (iii) with the relations that
$\mu_{l}\lesssim\mu\kappa^{\frac{1}{2}}$, $\kappa_{l}\lesssim\kappa$,
$N_{0}\leq N_{l}\leq 2N_{0}$ and $T_{l}=T_{d_{l}}+1$. In the same token, we
can also show that

$\mathcal{V}_{\mathcal{G}}^{-1}\left\|\widehat{\text{Var}}(\tilde{B})-\text{Var}(\tilde{B})\right\|=o_{p}(1)$

where
$\widehat{\text{Var}}(\tilde{B})=\frac{\widehat{\sigma}^{2}}{|\mathcal{G}|}\sum_{0\leq
l\leq L}\alpha_{l}\widehat{Z}_{l,t_{o}}^{\top}\left(\sum_{s\in
T_{d_{l}}}\widehat{Z}_{l,s}\widehat{Z}_{l,s}^{\top}\right)^{-1}\widehat{Z}_{l,t_{o}}$.
Then, we have
$\frac{\widehat{\mathcal{V}}_{\mathcal{G}}-\mathcal{V}_{\mathcal{G}}}{\mathcal{V}_{\mathcal{G}}}=o_{p}(1)$
and it implies that
$\frac{\mathcal{V}_{\mathcal{G}}}{\widehat{\mathcal{V}}_{\mathcal{G}}}\overset{\mathbb{P}}{\longrightarrow}1$.
Then, by the Slutsky’s theorem with Theorem 3.2, we have the desired result.
$\square$

###### Proof of Claim B.2.

Note that

$\left|\widehat{\sigma}^{2}-\sigma^{2}\right|\leq\left|\frac{1}{N_{0}T_{0}}\sum_{i\leq
N_{0},t_{\leq}T_{0}}\widehat{\epsilon}_{it}^{2}-\epsilon_{it}^{2}\right|+\left|\frac{1}{N_{0}T_{0}}\sum_{i\leq
N_{0},t_{\leq}T_{0}}\epsilon_{it}^{2}-\sigma^{2}\right|$

where
$\widehat{\epsilon}_{it}^{2}=\epsilon_{it}^{2}+(m_{it}-\widehat{m}_{it})^{2}+2\epsilon_{it}(m_{it}-\widehat{m}_{it})$.
As noted in the proof of Proposition A.4, we have

$\displaystyle\max_{i\leq
N_{0},t_{\leq}T_{0}}\left\|\widehat{m}_{it}-m_{it}\right\|$
$\displaystyle\leq\max_{i\leq
N_{0},t_{\leq}T_{0}}\left\|\widehat{m}_{it}-\widehat{X}_{0,i}^{\top}\widehat{Z}_{0,t}\right\|+\max_{i\leq
N_{0},t_{\leq}T_{0}}\left\|\widehat{X}_{0,i}^{\top}\widehat{Z}_{0,t}-m_{it}\right\|$
$\displaystyle\lesssim\left\|\widehat{X}_{0}\widehat{H}_{0}-X_{0}\right\|_{2,\infty}\left\|Z_{0}\right\|_{2,\infty}+\left\|\widehat{Z}_{0}\widehat{H}_{0}-Z_{0}\right\|_{2,\infty}\left\|X_{0}\right\|_{2,\infty}$
$\displaystyle\lesssim\sigma\frac{\kappa_{0}^{2}\mu_{0}r\max\\{\sqrt{N_{0}\log
N_{0}},\sqrt{T_{0}\log T_{0}}\\}}{\min\\{N_{0},T_{0}\\}}.$

Hence, we get

$\left|\frac{1}{N_{0}T_{0}}\sum_{i\leq
N_{0},t_{\leq}T_{0}}\widehat{\epsilon}_{it}^{2}-\epsilon_{it}^{2}\right|\lesssim\sigma\max_{i\leq
N_{0},t_{\leq}T_{0}}\left\|\widehat{m}_{it}-m_{it}\right\|\lesssim\sigma^{2}\frac{\kappa_{0}^{2}\mu_{0}r\max\\{\sqrt{N_{0}\log
N_{0}},\sqrt{T_{0}\log T_{0}}\\}}{\min\\{N_{0},T_{0}\\}}.$

Moreover, we have by concentration inequalities that

$\left|\frac{1}{N_{0}T_{0}}\sum_{i\leq
N_{0},t_{\leq}T_{0}}\epsilon_{it}^{2}-\sigma^{2}\right|\lesssim\sigma^{2}\left(N_{0}T_{0}\right)^{-\frac{1}{2}}\log(N_{0}T_{0})^{1/2}.$

Since the first term dominates the second term using the relations that
$\mu_{0}\lesssim\mu\kappa^{\frac{1}{2}}$, $\kappa_{0}\lesssim\kappa$, we have
the desired result. ∎

###  B.3 Relations about eigenvalue and eigenvector between the full matrix
and its submatrix

Lastly, we present one lemma which shows the relations about eigenvalue and
eigenvector between the full matrix and its submatrix.

######  Lemma B.3.

(i) Let $M=(m_{it})_{1\leq i\leq N,1\leq t\leq T}$ be a $N\times T$ matrix of
rank $r$ and $M_{o}=(m_{it})_{i\in\mathcal{I}_{o},t\in\mathcal{T}_{o}}$ be a
submatrix of $M$ where $|\mathcal{I}_{o}|=N_{o}$ and
$|\mathcal{T}_{o}|=T_{o}$. The SVD of $M$ is $UDV^{\top}$, and the $i$-th row
of $U$ is $u_{i}^{\top}$ and the $t$-th row of $V$ is $v_{t}^{\top}$. In
addition, $\mu$, $\kappa$ denote the incoherence parameter and the condition
number of $M$, and $\mu_{o},\kappa_{o}$ denote those of $M_{o}$. If there are
constants $C,c>0$ such that

$\displaystyle
c\leq\psi_{r}\left(\frac{1}{N_{o}}\sum_{i\in\mathcal{I}_{o}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq\psi_{1}\left(\frac{1}{N_{o}}\sum_{i\in\mathcal{I}_{o}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq
C,$ $\displaystyle
c\leq\psi_{r}\left(\frac{1}{T_{o}}\sum_{t\in\mathcal{T}_{o}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq\psi_{1}\left(\frac{1}{T_{o}}\sum_{t\in\mathcal{T}_{o}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq
C,$

we have $\mu_{o}\lesssim\mu\kappa^{1/2}$ and $\kappa_{o}\lesssim\kappa$.
(ii) Let $M_{1}=(m_{it})_{i\in\mathcal{I}_{1},t\in\mathcal{T}_{1}}$ and
$M_{2}=(m_{it})_{i\in\mathcal{I}_{2},t\in\mathcal{T}_{2}}$ be submatrices of
$M$ where $|\mathcal{I}_{1}|=N_{1}$, $|\mathcal{I}_{2}|=N_{2}$,
$|\mathcal{T}_{1}|=T_{1}$, and $|\mathcal{T}_{2}|=T_{2}$. If there are
constants $C,c>0$ such that for all $l\in\\{1,2\\}$,

$\displaystyle
c\leq\psi_{r}\left(\frac{1}{N_{l}}\sum_{i\in\mathcal{I}_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq\psi_{1}\left(\frac{1}{N_{l}}\sum_{i\in\mathcal{I}_{l}}\left(\sqrt{N}u_{i}\right)\left(\sqrt{N}u_{i}\right)^{\top}\right)\leq
C,$ $\displaystyle
c\leq\psi_{r}\left(\frac{1}{T_{l}}\sum_{t\in\mathcal{T}_{l}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq\psi_{1}\left(\frac{1}{T_{l}}\sum_{t\in\mathcal{T}_{l}}\left(\sqrt{T}v_{t}\right)\left(\sqrt{T}v_{t}\right)^{\top}\right)\leq
C,$

we have
$\frac{\sqrt{N_{1}T_{1}}}{\psi_{1,\min}}\asymp\frac{\sqrt{N_{2}T_{2}}}{\psi_{2,\min}}$
where $\psi_{l,\min}$ is the smallest singular value of $M_{l}$.

###### Proof of Lemma B.3.

(i) Without loss of generality, assume that
$\mathcal{I}_{o}=\\{1,\cdots,N_{o}\\}$ and
$\mathcal{T}_{o}=\\{1,\cdots,T_{o}\\}$. Let the SVD of $M_{o}$ be
$U_{o}D_{o}V_{o}^{\top}$. Then, we can say

$M_{it}=u_{i}^{\top}Dv_{t}=u_{o,i}^{\top}D_{o}v_{o,t}$

for $i\leq N_{o}$ and $t\leq T_{o}$. In addition, let $B_{sub}=U_{sub}D^{1/2}$
where $U_{sub}=[u_{1},\dots,u_{N_{o}}]^{\top}$ and $F_{sub}=V_{sub}D^{1/2}$
where $V_{sub}=[v_{1},\dots,v_{T_{o}}]^{\top}$. Then, we have
$M_{o}=B_{sub}F_{sub}^{\top}$. Define

$\displaystyle L^{*}$
$\displaystyle=\left(B_{sub}^{\top}B_{sub}\right)^{1/2}\left(F_{sub}^{\top}F_{sub}\right)\left(B_{sub}^{\top}B_{sub}\right)^{1/2}$
$\displaystyle=D^{1/4}\left(U_{sub}^{\top}U_{sub}\right)^{1/2}D^{1/4}D^{1/2}\left(V_{sub}^{\top}V_{sub}\right)D^{1/2}D^{1/4}\left(U_{sub}^{\top}U_{sub}\right)^{1/2}D^{1/4}.$

Let $G_{L^{*}}$ be a $K\times K$ matrix whose columns are the eigenvectors of
$L^{*}$ such that $\Lambda_{L^{*}}=G_{L^{*}}^{\top}L^{*}G_{L^{*}}$ is a
descending order diagonal matrix of the eigenvalues of $L^{*}$. Define

$H_{u}=\left(B_{sub}^{\top}B_{sub}\right)^{-1/2}G_{L^{*}}=D^{-1/4}\left(U_{sub}^{\top}U_{sub}\right)^{-1/2}D^{-1/4}G_{L^{*}}.$

Note that

$\displaystyle\left(B_{sub}F_{sub}^{\top}F_{sub}B_{sub}^{\top}\right)B_{sub}H_{u}$
$\displaystyle=B_{sub}\left(B_{sub}^{\top}B_{sub}\right)^{-1/2}\left(B_{sub}^{\top}B_{sub}\right)^{1/2}\left(F_{sub}^{\top}F_{sub}\right)\left(B_{sub}^{\top}B_{sub}\right)^{1/2}\left(B_{sub}^{\top}B_{sub}\right)^{1/2}H_{u}$
$\displaystyle=B_{sub}\left(B_{sub}^{\top}B_{sub}\right)^{-1/2}L^{*}G_{L^{*}}$
$\displaystyle=B_{sub}\left(B_{sub}^{\top}B_{sub}\right)^{-1/2}G_{L^{*}}\Lambda_{L^{*}}$
$\displaystyle=B_{sub}H_{u}\Lambda_{L^{*}}.$

In addition, we have

$\displaystyle(B_{sub}H_{u})^{\top}B_{sub}H_{u}$
$\displaystyle=H_{u}^{\top}B_{sub}^{\top}B_{sub}H_{u}=G_{L^{*}}^{\top}\left(B_{sub}^{\top}B_{sub}\right)^{-1/2}B_{sub}^{\top}B_{sub}\left(B_{sub}^{\top}B_{sub}\right)^{-1/2}G_{L^{*}}=I_{r}.$

Hence, the column of $B_{sub}H_{u}$ are the eigenvector of
$\left(B_{sub}F_{sub}^{\top}F_{sub}B_{sub}^{\top}\right)=M_{o}M_{o}^{\top}$
corresponding to the eigenvalue $\Lambda_{L^{*}}$. Hence, $B_{sub}H_{u}$ is
the left singular vector of $M_{o}$, that is, $U_{o}$. Then, since

$\displaystyle
U_{o}=B_{sub}H_{u}=U_{sub}D^{1/2}D^{-1/4}\left(U_{sub}^{\top}U_{sub}\right)^{-1/2}D^{-1/4}G_{L^{*}}=U_{sub}D^{1/4}\left(U_{sub}^{\top}U_{sub}\right)^{-1/2}D^{-1/4}G_{L^{*}},$
(B.3)

we have the following incoherence condition for the submatrix:

$\displaystyle\max_{i}\left\|u_{o,i}\right\|=\max_{i}\left\|e_{i}^{\top}U_{o}\right\|\leq\max_{i}\left\|e_{i}^{\top}U_{sub}\right\|\left\|D^{1/4}\right\|\left\|D^{-1/4}\right\|\left\|\left(U_{sub}^{\top}U_{sub}\right)^{-1/2}\right\|\leq\frac{\mu_{o}^{1/2}r^{1/2}}{\sqrt{N_{o}}}$

where $\mu_{o}=C\mu\kappa^{1/2}$ for some constant $C>0$. Similarly, we can
have
$\max_{t}\left\|v_{o,t}\right\|\leq\frac{\mu_{o}^{1/2}r^{1/2}}{\sqrt{T_{o}}}$
where $\mu_{o}=C\mu\kappa^{1/2}$ for some constant $C>0$. Hence, the
incoherence parameter for the submatrix $M_{o}$ is $C\mu\kappa^{1/2}$ for some
constant $C>0$.
Note that

$M_{o}=U_{o}D_{o}V_{o}^{\top}=U_{sub}DV_{sub}^{\top}\Longrightarrow
D_{o}=U_{o}^{\top}U_{sub}DV_{sub}^{\top}V_{o}.$

Then, by using the relation (B.3), we have

$\displaystyle D_{o}$
$\displaystyle=U_{o}^{\top}(U_{o}G_{L^{*}}^{\top}D^{1/4}\left(U_{sub}^{\top}U_{sub}\right)^{1/2}D^{-1/4})D(D^{-1/4}\left(V_{sub}^{\top}V_{sub}\right)^{1/2}D^{1/4}G_{R^{*}}V_{o}^{\top})V_{o}$
$\displaystyle=G_{L^{*}}^{\top}D^{1/4}\left(U_{sub}^{\top}U_{sub}\right)^{1/2}D^{1/2}\left(V_{sub}^{\top}V_{sub}\right)^{1/2}D^{1/4}G_{R^{*}},$

where $G_{R^{*}}$ is a $K\times K$ eigenvector matrix of
$R^{*}=\left(F_{sub}^{\top}F_{sub}\right)^{1/2}\left(B_{sub}^{\top}B_{sub}\right)\left(F_{sub}^{\top}F_{sub}\right)^{1/2}$.
Then, we have

$\displaystyle\psi_{1}(D_{o})\leq\left\|D^{1/4}\right\|^{2}\left\|D^{1/2}\right\|\left\|\left(U_{sub}^{\top}U_{sub}\right)^{1/2}\right\|\left\|\left(V_{sub}^{\top}V_{sub}\right)^{1/2}\right\|\lesssim\psi_{1}(D)\frac{\sqrt{N_{o}T_{o}}}{\sqrt{NT}},$
(B.4)
$\displaystyle\psi_{r}(D_{o})\geq\lambda^{2}_{\min}(D^{1/4})\lambda_{\min}(D^{1/2})\lambda_{\min}\left(\left(U_{sub}^{\top}U_{sub}\right)^{1/2}\right)\lambda_{\min}\left(\left(V_{sub}^{\top}V_{sub}\right)^{1/2}\right)\gtrsim\psi_{r}(D)\frac{\sqrt{N_{o}T_{o}}}{\sqrt{NT}}.$

So, the condition number of the submatrix can be bounded like
$\kappa_{o}=\frac{\psi_{1}(D_{o})}{\psi_{r}(D_{o})}\lesssim\frac{\psi_{1}(D)}{\psi_{r}(D)}=\kappa$.
(ii) By using the relation (B.4) with the fact that
$\kappa_{2}\lesssim\kappa$, we know

$\psi_{1,\min}^{-1}\lesssim\psi_{\min}^{-1}\frac{\sqrt{NT}}{\sqrt{N_{1}T_{1}}}=\kappa^{-1}\psi_{\max}^{-1}\frac{\sqrt{NT}}{\sqrt{N_{1}T_{1}}}\lesssim\kappa^{-1}\psi_{2,\max}^{-1}\frac{\sqrt{N_{2}T_{2}}}{\sqrt{N_{1}T_{1}}}\lesssim\kappa_{2}^{-1}\psi_{2,\max}^{-1}\frac{\sqrt{N_{2}T_{2}}}{\sqrt{N_{1}T_{1}}}=\psi_{2,\min}^{-1}\frac{\sqrt{N_{2}T_{2}}}{\sqrt{N_{1}T_{1}}}.$

Similarly, we can show
$\psi_{2,\min}^{-1}\lesssim\psi_{1,\min}^{-1}\frac{\sqrt{N_{1}T_{1}}}{\sqrt{N_{2}T_{2}}}$.
Hence, we have that
$\frac{\sqrt{N_{1}T_{1}}}{\psi_{1,\min}}\asymp\frac{\sqrt{N_{2}T_{2}}}{\psi_{2,\min}}$.

∎

##  Appendix C Formal inferential theory for the treatment effect estimation
in Section 4

This section provides the formal inferential theory for the group averaged
treatment effects, $\mu_{t_{0}}^{(d)}$ and $\theta_{t_{0}}^{(d)}$ in Section
4. The assumption on the noise is the same as that in Section 2, and the
singular vectors of $M$ are incoherent in that there is a $\mu\geq 1$ such
that $||U||_{2,\infty}\leq\sqrt{{\mu r}/{N}}$, $||V||_{2,\infty}\leq\sqrt{{\mu
r}/{(T+3T_{1})}}$.

Denote by $M_{O_{(d)}}=(m^{(0)}_{it})_{i\in\mathcal{I}_{d},t\leq T_{0}}$, and
the smallest nonzero singular value of it by $\psi_{\min,O_{(d)}}$. In
addition, denote $\\{\mathcal{G}_{(d),l}\\}_{0\leq l\leq L_{d}}$ by the
subgroups of $\mathcal{G}$ for the estimation of
$\\{m^{(d)}_{it_{0}}\\}_{i\in\mathcal{G}}$. Then, we have the following
asymptotic normality of the group averaged estimator.

######  Theorem C.1.

Assume that for any $0\leq d\leq 3$ and $l=1,\cdots,L_{d}$,

  * (i)

$\sigma\kappa^{\frac{23}{4}}\mu^{\frac{3}{2}}r^{\frac{3}{2}}\sqrt{N_{d}}\max\\{{N_{d}\sqrt{\log{N_{d}}}},{T_{0}\sqrt{\log{T_{0}}}}\\}=o_{p}\left(\psi_{\min,O_{(d)}}\min\\{N_{d},T_{0}\\}\right)$;

  * (ii)

$\kappa^{\frac{11}{2}}\mu^{3}r^{3}\sqrt{N_{d}}\max\\{{\sqrt{N_{d}\log^{3}{N_{d}}}},{\sqrt{T_{0}\log^{3}{T_{0}}}}\\}=o_{p}\left(\min\\{N_{d}^{\frac{3}{2}},T_{0}^{\frac{3}{2}}\\}\right)$;

  * (iii)

$|\mathcal{G}_{(d),l}|\kappa^{\frac{17}{4}}\mu^{\frac{5}{2}}r^{\frac{5}{2}}\max\\{\sqrt{N_{d}\log{N_{d}}},\sqrt{T_{0}\log{T_{0}}}\\}=o_{p}\left(\sqrt{N_{d}}\min\\{N_{d},T_{0}\\}\right)$;

  * (iv)

There are constants $C,c>0$ such that

$\displaystyle
c\leq\lambda_{\min}\left(\frac{N}{N_{d}}\sum_{i\in\mathcal{I}_{d}}u_{i}u_{i}^{\top}\right)\leq\lambda_{\max}\left(\frac{N}{N_{d}}\sum_{i\in\mathcal{I}_{d}}u_{i}u_{i}^{\top}\right)\leq
C,$ $\displaystyle c\leq\lambda_{\min}\left(\frac{T_{M}}{T_{0}}\sum_{t\leq
T_{0}}v_{t}v_{t}^{\top}\right)\leq\lambda_{\max}\left(\frac{T_{M}}{T_{0}}\sum_{t\leq
T_{0}}v_{t}v_{t}^{\top}\right)\leq C,$

where $T_{M}=T+3T_{1}$ is the number of columns of $M$;

  * (v)

$\sqrt{N}\left\|\bar{u}_{\mathcal{G}}\right\|\geq c$ for some constant $c>0$
where $\bar{u}_{\mathcal{G}}=|\mathcal{G}|^{-1}\sum_{i\in\mathcal{G}}u_{i}$.

Then, we have

$\displaystyle\mathcal{V}_{\mu}^{-\frac{1}{2}}\left(\widehat{\mu}^{(d)}_{t_{0}}-\mu^{(d)}_{t_{0}}\right)\overset{D}{\longrightarrow}\mathcal{N}(0,1),\
\
\mathcal{V}_{\theta}^{-\frac{1}{2}}\left(\widehat{\theta}^{(d)}_{t_{0}}-\theta^{(d)}_{t_{0}}\right)\overset{D}{\longrightarrow}\mathcal{N}(0,1),$

$\mathcal{V}_{\mu}=\mathcal{V}_{\mathcal{G}}(d,0)$ and
$\mathcal{V}_{\theta}=\mathcal{V}_{\mathcal{G}}(d,d-1)$ where

$\displaystyle\mathcal{V}_{\mathcal{G}}(d,d^{\prime})=$
$\displaystyle\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{d}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}}+\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{d^{\prime}}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}}$
$\displaystyle\ \ +\frac{\sigma^{2}}{|\mathcal{G}|}\left(v_{(d\cdot
T_{1}+t_{0})}-v_{(d^{\prime}\cdot T_{1}+t_{0})}\right)^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\left(v_{(d\cdot
T_{1}+t_{0})}-v_{(d^{\prime}\cdot T_{1}+t_{0})}\right).$

For completeness, we provide the variance estimator. For each $0\leq d\leq 3$
and $0\leq l\leq L_{d}$, denote by
$\left(\widehat{X}^{(d)}_{l},\widehat{Z}^{(d)}_{l}\right)$ the debiased
estimators derived from $\tilde{Y}^{(d)}_{l}$ which is the submatrix of
$\tilde{Y}^{(d)}$ constructed for the estimation of
$\\{m^{(d)}_{it_{0}}\\}_{i\in\mathcal{G}_{(d),l}}$. In addition,
$\widehat{X}^{(d)}_{l,j}$ denotes a row of $\widehat{X}^{(d)}_{l}$ which
corresponds to the unit $j$ and $\widehat{Z}^{(d)}_{l,s}$ denotes a row of
$\widehat{Z}^{(d)}_{l}$ which corresponds to the $s$-th column of $M$.

######  Corollary C.2 (Feasible CLT of Theorem C.1).

Suppose the assumptions in Theorem C.1 hold. In addition, we have for all
$0\leq d\leq 3$,
$\frac{\sigma}{\psi_{\min,O_{(d)}}}\frac{\kappa^{5}\mu^{4}r^{4}N_{d}\max\\{\sqrt{N_{d}\log
N_{d}},\sqrt{T_{0}\log
T_{0}}\\}}{\min\\{N_{d},T_{0}\\}}\overset{\mathbb{P}}{\longrightarrow}0$.
Then,

$\displaystyle\widehat{\mathcal{V}}_{\mu}^{-\frac{1}{2}}\left(\widehat{\mu}^{(d)}_{t_{0}}-\mu^{(d)}_{t_{0}}\right)\overset{D}{\longrightarrow}\mathcal{N}(0,1),\
\
\widehat{\mathcal{V}}_{\theta}^{-\frac{1}{2}}\left(\widehat{\theta}^{(d)}_{t_{0}}-\theta^{(d)}_{t_{0}}\right)\overset{D}{\longrightarrow}\mathcal{N}(0,1),$

$\widehat{\mathcal{V}}_{\mu}=\widehat{\mathcal{V}}_{\mathcal{G}}(d,0)$ and
$\widehat{\mathcal{V}}_{\theta}=\widehat{\mathcal{V}}_{\mathcal{G}}(d,d-1)$
where

$\displaystyle\widehat{\mathcal{V}}_{\mathcal{G}}(d,d^{\prime})$
$\displaystyle=\sum_{\delta\in\\{d,d^{\prime}\\}}\widehat{\sigma}^{2}\sum_{i\in\mathcal{I}_{\delta}}\left(\sum_{0\leq
l\leq
L_{\delta}}\alpha^{(\delta)}_{l}\widehat{\bar{X}}_{\mathcal{G}_{(\delta),l}}^{\top}\left(\sum_{j\in\mathcal{I}_{\delta}}\widehat{X}_{l,j}^{(\delta)}\widehat{X}_{l,j}^{(\delta)\top}\right)^{-1}\widehat{X}_{l,i}^{(\delta)}\right)^{2}$
$\displaystyle\quad+\sum_{\delta\in\\{d,d^{\prime}\\}}\frac{\widehat{\sigma}^{2}}{|\mathcal{G}|}\widehat{Z}_{0,(\delta\cdot
T_{1}+t_{o})}^{(\delta)\top}\left(\sum_{s\leq
T_{0}}\widehat{Z}^{(\delta)}_{0,s}\widehat{Z}_{0,s}^{(\delta)\top}\right)^{-1}\widehat{Z}_{0,(\delta\cdot
T_{1}+t_{o})}^{(\delta)}$
$\displaystyle\quad-2\frac{\widehat{\sigma}^{2}}{|\mathcal{G}|}\sum_{s\leq
T_{0}}\left(\widehat{Z}_{0,(d\cdot T_{1}+t_{o})}^{(d)\top}\left(\sum_{s\leq
T_{0}}\widehat{Z}_{0,s}^{(d)}\widehat{Z}_{0,s}^{(d)\top}\right)^{-1}\widehat{Z}^{(d)}_{0,s}\right)\left(\widehat{Z}_{0,s}^{(d^{\prime})\top}\left(\sum_{s\leq
T_{0}}\widehat{Z}_{0,s}^{(d^{\prime})}\widehat{Z}_{0,s}^{(d^{\prime})\top}\right)^{-1}\widehat{Z}^{(d^{\prime})}_{0,(d^{\prime}\cdot
T_{1}+t_{o})}\right),$

$\alpha_{l}^{(d)}=\frac{|\mathcal{G}_{(d),l}|}{|\mathcal{G}|}$,
$\widehat{\sigma}^{2}=\frac{1}{NT_{0}}\sum_{i\leq N,t\leq
T_{0}}\widehat{\epsilon}_{it}^{2}$,
$\widehat{\epsilon}_{it}=y_{it}-x_{it}^{\top}\beta-\widehat{m}^{(0)}_{it}$. In
addition,
$\widehat{\bar{X}}_{\mathcal{G}_{(d),l}}=\frac{1}{|\mathcal{G}_{(d),l}|}\sum_{i\in\mathcal{G}_{(d),l}}\widehat{X}_{l,i}^{(d)}$.

Proof of Theorem C.1

(i) Case 1 $(\widehat{\mu}_{t_{0}}^{(d)})$: Following the proof of Theorem
3.1, we have the decomposition:

$\displaystyle\frac{\mathcal{V}_{\mu}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\left(\widehat{m}_{it_{o}}^{(d)}-m_{it_{o}}^{(d)}\right)-\frac{\mathcal{V}_{\mu}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}\left(\widehat{m}_{it_{o}}^{(0)}-m_{it_{o}}^{(0)}\right)$
$\displaystyle=\underbrace{\mathcal{V}_{\mu}^{-\frac{1}{2}}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{d}}u_{j}u_{j}^{\top}\right)^{-1}\sum_{j\in\mathcal{I}_{d}}u_{j}\epsilon_{jt_{o}}}_{\coloneqq
A^{(d)}}+\underbrace{\frac{\mathcal{V}_{\mu}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}v_{(d\cdot
T_{1}+t_{o})}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\sum_{s\leq
T_{0}}v_{s}\epsilon_{is}}_{\coloneqq B^{(d)}}$ $\displaystyle\ \
-\underbrace{\mathcal{V}_{\mu}^{-\frac{1}{2}}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{0}}u_{j}u_{j}^{\top}\right)^{-1}\sum_{j\in\mathcal{I}_{0}}u_{j}\epsilon_{jt_{o}}}_{\coloneqq
A^{(0)}}-\underbrace{\frac{\mathcal{V}_{\mu}^{-\frac{1}{2}}}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}v_{t_{o}}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\sum_{s\leq
T_{0}}v_{s}\epsilon_{is}}_{\coloneqq
B^{(0)}}+\mathcal{V}_{\mu}^{-\frac{1}{2}}\mathcal{R}$ (C.1)

where $\mathcal{R}$ is a residual term. First, we want to show the Lindeberg
condition. Note that

$\displaystyle A^{(d)}+B^{(d)}=\sum_{j\leq N}\sum_{s\leq
T}\underbrace{\left(P1_{\\{j\in\mathcal{I}_{d},s=t_{o}\\}}+\sum_{0\leq l\leq
L_{d}}Q_{l}1_{\\{j\in\mathcal{G}_{(d),l},s\leq
T_{0}\\}}\right)\epsilon_{js}}_{\coloneqq\mathcal{Y}^{(d)}_{js}},$
$\displaystyle\text{where }\ \
P=\mathcal{V}_{\mu}^{-\frac{1}{2}}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{d}}u_{j}u_{j}^{\top}\right)^{-1}u_{j},\
\
Q_{l}=\frac{\mathcal{V}_{\mu}^{-\frac{1}{2}}}{|\mathcal{G}|}v_{(d\cdot\mathcal{I}_{d}+t_{o})}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\sum_{s\leq T_{0}}v_{s}.$

Using the same way in the proof of Theorem 3.2, we have
$\left\|P\right\|\leq\mathcal{V}_{\mu}^{-\frac{1}{2}}\frac{\mu r}{N_{d}}$ and
$\left\|Q_{l}\right\|\leq\frac{\mathcal{V}_{\mu}^{-\frac{1}{2}}}{|\mathcal{G}|}\frac{\mu
r}{T_{0}}$. Then, by the same token as the proof of Theorem 3.2, we have

$\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{(d)4}]\lesssim\mathcal{V}_{\mu}^{-2}\sigma^{4}\frac{\mu^{4}r^{4}}{N_{d}^{3}}+\mathcal{V}_{\mu}^{-2}\sigma^{4}\mu^{4}r^{4}T_{0}^{-3}.$

Similarly, we have

$\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{(0)4}]\lesssim\mathcal{V}_{\mu}^{-2}\sigma^{4}\frac{\mu^{4}r^{4}}{N_{0}^{3}}+\mathcal{V}_{\mu}^{-2}\sigma^{4}\mu^{4}r^{4}T_{0}^{-3}$

where $A^{(0)}+B^{(0)}=\sum_{j\leq N}\sum_{s\leq T}\mathcal{Y}^{(0)}_{js}$.
Then, for any $q>0$, we have by Cauchy-Schwarz and Markov inequalities with
Claim C.3,

$\displaystyle\text{Var}(A+B)^{-1}\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{2}1_{\\{|\mathcal{Y}_{js}|>q\text{Var}(A+B)^{1/2}\\}}]$
$\displaystyle\leq
2\text{Var}(A+B)^{-1}\left(\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{(d)2}1_{\\{|\mathcal{Y}_{js}|>q\text{Var}(A+B)^{1/2}\\}}]+\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{(0)2}1_{\\{|\mathcal{Y}_{js}|>q\text{Var}(A+B)^{1/2}\\}}]\right)$
$\displaystyle\leq\frac{2}{\text{Var}(A+B)q}\sqrt{\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{(d)4}]}+\frac{2}{\text{Var}(A+B)q}\sqrt{\sum_{j,s}\mathbb{E}[\mathcal{Y}_{js}^{(0)4}]}$
$\displaystyle\lesssim\frac{\mu^{3}r^{3}}{N_{d}^{\frac{1}{2}}}+\frac{\mu^{3}r^{3}N_{d}}{T_{0}^{\frac{3}{2}}}+\frac{\mu^{3}r^{3}}{N^{\frac{1}{2}}_{0}}+\frac{\mu^{3}r^{3}N_{0}}{T_{0}^{\frac{3}{2}}},$

where $A=A^{(d)}-A^{(0)}$, $B=B^{(d)}-B^{(0)}$, and
$\mathcal{Y}_{js}=\mathcal{Y}_{js}^{(d)}-\mathcal{Y}_{js}^{(0)}$. Because the
last term is $o_{p}(1)$, the Lindeberg condition is satisfied.

######  Claim C.3.

(i) $\text{Var}(A+B)=1$ and (ii) $\mathcal{V}_{\mu}^{-1}\lesssim\ \frac{\mu
r\min\\{N_{0},N_{d}\\}}{\sigma^{2}}$.

Therefore, by Lindeberg CLT, we have
$A+B\overset{D}{\longrightarrow}\mathcal{N}(0,1)$. In addition, by the same
token as in the proof of Theorem 3.1, we can show
$\left\|\mathcal{V}_{\mu}^{-\frac{1}{2}}\mathcal{R}\right\|=o_{p}(1)$.
Therefore,

$\mathcal{V}_{\mu}^{-\frac{1}{2}}\left(\frac{1}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}(\widehat{m}^{(d)}_{it_{o}}-\widehat{m}^{(0)}_{it_{o}})-\frac{1}{|\mathcal{G}|}\sum_{i\in\mathcal{G}}(m^{(d)}_{{it_{o}}}-m^{(0)}_{{it_{o}}})\right)\overset{D}{\longrightarrow}\mathcal{N}(0,1).$

(ii) Case 2 $(\widehat{\theta}_{t_{0}}^{(d)})$: The proof is the same as that
of Case 1 if we change $A^{(0)},B^{(0)}$ to $A^{(d-1)},B^{(d-1)}$. Since it is
a simple extension of the proof of Case 1, we omit it. $\square$

###### Proof of Claim C.3.

(i) Since $t_{o}>T_{0}$ and $\mathcal{I}_{d}$ is disjoint with
$\mathcal{I}_{0}$, we have

$\text{Var}(A+B)=\text{Var}(A^{(d)})+\text{Var}(A^{(0)})+\text{Var}(B).$

A Simple calculations show that

$\displaystyle\text{Var}(A^{(d)})=\mathcal{V}_{\mu}^{-1}\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{d}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}},\
\
\text{Var}(A^{(0)})=\mathcal{V}_{\mu}^{-1}\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{0}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}},$
$\displaystyle\text{Var}(B)=\mathcal{V}_{\mu}^{-1}\frac{\sigma^{2}}{|\mathcal{G}|}\left(v_{(d\cdot
T_{1}+t_{o})}-v_{t_{o}}\right)^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}\left(v_{(d\cdot
T_{1}+t_{o})}-v_{t_{o}}\right).$

Hence, we have $\text{Var}(A+B)=1$.
(ii) Note that

$\displaystyle\mathcal{V}_{\mu}=\mathcal{V}_{\mu}\text{Var}(A)+\mathcal{V}_{\mu}\text{Var}(B)\geq\mathcal{V}_{\mu}\text{Var}(A)\geq\max\\{\mathcal{V}_{\mu}\text{Var}(A^{(d)}),\mathcal{V}_{\mu}\text{Var}(A^{(0)})\\},$

since $\text{Var}(A)=\text{Var}(A^{(d)})+\text{Var}(A^{(0)})$. In addition, we
have

$\mathcal{V}_{\mu}\text{Var}(A^{(d)})=\sigma^{2}\bar{u}_{\mathcal{G}}^{\top}\left(\sum_{j\in\mathcal{I}_{d}}u_{j}u_{j}^{\top}\right)^{-1}\bar{u}_{\mathcal{G}}\geq\sigma^{2}\left\|\bar{u}_{\mathcal{G}}\right\|^{2}\lambda_{\min}\left(\left(\sum_{j\in\mathcal{I}_{d}}u_{j}u_{j}^{\top}\right)^{-1}\right)\geq
c\frac{\sigma^{2}}{\mu rN_{d}}$

for some constant $c>0$. Similarly, we have
$\mathcal{V}_{\mu}\text{Var}(A^{(0)})\geq c\frac{\sigma^{2}}{\mu rN_{0}}$ for
some constant $c>0$. Therefore, we reach $\mathcal{V}_{\mu}^{-1}\leq
C\frac{\mu r\min\\{N_{0},N_{d}\\}}{\sigma^{2}}$. ∎

Proof of Corollary C.2

(i) Case 1 $(\widehat{\mu}_{t_{0}}^{(d)})$: From the proof of Claim C.3, we
know

$\mathcal{V}_{\mu}=\text{Var}(\tilde{A}^{(d)})+\text{Var}(\tilde{A}^{(0)})+\text{Var}(\tilde{B}^{(d)})+\text{Var}(\tilde{B}^{(0)})-2\text{Var}(\tilde{B}^{(0)})$

where $\tilde{A}^{(\delta)}=\mathcal{V}_{\mu}^{\frac{1}{2}}A^{(\delta)}$ and
$\tilde{B}^{(\delta)}=\mathcal{V}_{\mu}^{\frac{1}{2}}B^{(\delta)}$. Following
the similar argument in the proof of Corollary 3.3 with the definitions in
(C), we have

$\text{Var}(\tilde{A}^{(d)})=\sigma^{2}\sum_{i\in\mathcal{I}_{d}}\left(\sum_{0\leq
l\leq
L_{d}}\alpha^{(d)}_{l}\bar{X}_{\mathcal{G}_{(d),l}}^{\top}\left(\sum_{j\in\mathcal{I}_{d}}X_{l,j}^{(d)}X_{l,j}^{(d)\top}\right)^{-1}X_{l,i}^{(d)}\right)^{2},$

where $\alpha^{(d)}_{l}=\frac{|\mathcal{G}_{(d),l}|}{|\mathcal{G}|}$,
$\bar{X}_{\mathcal{G}_{(d),l}}=\frac{1}{|\mathcal{G}_{(d),l}|}\sum_{i\in\mathcal{G}_{(d),l}}X_{l,i}^{(d)}$,
and $X_{l}^{(d)}=U_{l}^{(d)}D_{l}^{(d)\frac{1}{2}}$. Here,
$U_{l}^{(d)}D_{l}^{(d)}V_{l}^{(d)\top}$ are the SVD of $\tilde{M}^{(d)}_{l}$
which is the submatrix of $\tilde{M}^{(d)}$ constructed for the estimation of
$\\{m_{it_{0}}^{(d)}\\}_{i\in\mathcal{G}_{(d),l}}$. In addition, we have

$\text{Var}(\tilde{B}^{(d)})=\frac{\sigma^{2}}{|\mathcal{G}|}Z_{0,(d\cdot
T_{1}+t_{o})}^{(d)\top}\left(\sum_{s\leq
T_{0}}Z^{(d)}_{0,s}Z_{0,s}^{(d)\top}\right)^{-1}Z_{0,(d\cdot
T_{1}+t_{o})}^{(d)},$

where $Z_{l}^{(d)}=V_{l}^{(d)}D_{l}^{(d)\frac{1}{2}}$. Note that for all
$\delta\in\\{0,d\\}$, $\mathcal{V}_{\mu}^{-1}\lesssim\frac{\mu
rN_{\delta}}{\sigma^{2}}$ by Claim C.3. Then, by the same way as the proof of
Corollary 3.3, we have

$\mathcal{V}_{\mu}^{-1}\left\|\widehat{\text{Var}}(\tilde{A}^{(\delta)})-\text{Var}(\tilde{A}^{(\delta)})\right\|=o_{p}(1),\
\
\mathcal{V}_{\mu}^{-1}\left\|\widehat{\text{Var}}(\tilde{B}^{(\delta)})-\text{Var}(\tilde{B}^{(\delta)})\right\|=o_{p}(1).$

Similarly, we can show that

$\mathcal{V}_{\mu}^{-1}\left\|\widehat{\text{Cov}}(\tilde{B}^{(d)},\tilde{B}^{(0)})-\text{Cov}(\tilde{B}^{(d)},\tilde{B}^{(0)})\right\|=o_{p}(1)$

where

$\displaystyle\text{Cov}(\tilde{B}^{(d)},\tilde{B}^{(0)})$
$\displaystyle=\frac{\sigma^{2}}{|\mathcal{G}|}v_{(d\cdot
T_{1}+t_{o})}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}v_{t_{o}}^{\top}$
$\displaystyle=\frac{\sigma^{2}}{|\mathcal{G}|}\sum_{s\leq T_{0}}v_{(d\cdot
T_{1}+t_{o})}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}v_{s}v_{s}^{\top}\left(\sum_{s\leq
T_{0}}v_{s}v_{s}^{\top}\right)^{-1}v_{t_{o}}^{\top}$
$\displaystyle=\frac{\sigma^{2}}{|\mathcal{G}|}\sum_{s\leq T_{0}}Z_{0,(d\cdot
T_{1}+t_{o})}^{(d)\top}\left(\sum_{s\leq
T_{0}}Z_{0,s}^{(d)}Z_{0,s}^{(d)\top}\right)^{-1}Z^{(d)}_{0,s}Z_{0,s}^{(0)\top}\left(\sum_{s\leq
T_{0}}Z_{0,s}^{(0)}Z_{0,s}^{(0)\top}\right)^{-1}Z_{0,t_{o}}^{(0)\top}.$

Hence, we have
$\frac{\widehat{\mathcal{V}}_{\mu}-\mathcal{V}_{\mu}}{\mathcal{V}_{\mu}}=o_{p}(1)$
and it implies that
$\frac{\mathcal{V}_{\mu}}{\widehat{\mathcal{V}}_{\mu}}\overset{\mathbb{P}}{\longrightarrow}1$.
Then, by the Slutsky’s theorem with Theorem C.1, we have the desired result.
(ii) Case 2 $(\widehat{\theta}_{t_{0}}^{(d)})$: The proof is the same as that
of Case 1 if we change $A^{(0)},B^{(0)}$ to $A^{(d-1)},B^{(d-1)}$. Since it is
a simple extension of the proof of Case 1, we omit it. $\square$

##  Appendix D Modification of results from Chen et al., 2020b

Finally, we present technical tools used for proving Lemmas A.8 and A.9 in
Section A.5. These results are modifications of similar results from Chen et
al., 2020b  when missing is random. Indeed the overall architecture of our
proof is the same as those in Chen et al., 2020b , and for brevity, we shall
omit proofs of lemmas that are straightforward adaptation of those in Chen et
al., 2020b .

###  D.1 Proximity between the nonconvex estimator and the nuclear norm
penalized estimator

We begin by introducing further notations. For any matrix $G$, we denote by
$G_{l,\cdot}$ (resp. $G_{\cdot,l}$) the $l$-th row (resp. column) of $G$. Let
$G$ be a $N_{o}\times T_{o}$ matrix with rank $r$ and $L\Sigma R^{\top}$ be
SVD of $G$. Then the tangent space of $G$, denoted by $T(G)$, is defined as

$T(G)=\\{D\in\mathbb{R}^{N_{o}\times T_{o}}|D=AR^{\top}+LB^{\top}\,\,\text{for
some}\,\,A\in\mathbb{R}^{N_{o}\times
r}\,\,\text{and}\,\,B\in\mathbb{R}^{T_{o}\times r}\\}.$

Let $\mathcal{P}_{T(G)}$ be the orthogonal projection onto $T(G)$, that is,

$\mathcal{P}_{T(G)}(E)=LL^{\top}E+ERR^{\top}-LL^{\top}ERR^{\top}$

for any $E\in\mathbb{R}^{N_{o}\times T_{o}}$. When there is no risk of
confusion, we will simply denote by $T$ instead of $T(G)$. Let $T^{\perp}$ be
the orthogonal complement of $T$ and $\mathcal{P}_{T^{\perp}}$ be the
projection onto $T^{\perp}$. Note that
$\mathcal{P}_{T^{\perp}}(E)=(I-LL^{\top})E(I-RR^{\top})$ and
$\mathcal{P}_{T}(E)+\mathcal{P}_{T^{\perp}}(E)=E$. Lastly, we define
$\mathcal{P}_{\Omega_{o}}^{\text{diff}}(G)=\mathcal{P}_{\Omega_{o}}(G)-G$, for
all $G\in\mathbb{R}^{N_{o}\times T_{o}}$.

The following lemma plays a key role in showing the proximity between the
nonconvex estimator $(\breve{X}_{o},\breve{Z}_{o})$ and the nuclear norm
penalized estimator $\widetilde{M}_{o}$. We will eventually set
$(\ddot{X}_{o},\ddot{Z}_{o})=(\breve{X}_{o}\breve{H}_{o},\breve{Z}_{o}\breve{H}_{o})$
where
$(\breve{X}_{o},\breve{Z}_{o})=(X^{\tau^{*}_{o}}_{o},Z^{\tau^{*}_{o}}_{o})$
and $\breve{H}_{o}=H^{\tau^{*}_{o}}_{o}$.

######  Condition D.1 (Regularization parameter).

The regularization parameter $\lambda_{o}$ satisfies (i)
$\left\|\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})\right\|<\frac{7}{8}\lambda_{o}$
and (ii)
$\left\|\mathcal{P}_{\Omega_{o}}(\ddot{X}_{o}\ddot{Z}_{o}^{\top}-M_{o})-\ddot{X}_{o}\ddot{Z}_{o}^{\top}-M_{o}\right\|<\frac{1}{80}\lambda_{o}$.

######  Condition D.2 (Injectivity).

Let $T$ be the tangent space of $\ddot{X}_{o}\ddot{Z}_{o}^{\top}$. There is a
quantity $c_{\text{inj},o}>0$ such that
$\left\|\mathcal{P}_{\Omega_{o}}(H)\right\|_{F}^{2}\geq
c_{\text{inj},o}\left\|H\right\|^{2}_{F}$ for all $H\in T$.

######  Lemma D.3.

Suppose that $(\ddot{X}_{o},\ddot{Z}_{o})$ satisfies

$\displaystyle\left\|\nabla f(\ddot{X}_{o},\ddot{Z}_{o})\right\|_{F}\leq
c\frac{\sqrt{c_{\textrm{inj},o}}}{\kappa_{o}}\lambda_{o}\sqrt{\psi_{\min,o}}$
(D.1)

for some sufficiently small constant $c>0$. Additionally, assume that any
nonzero singular value of $\ddot{X}_{o}$ and $\ddot{Z}_{o}$ exists in the
interval $[\sqrt{\frac{\psi_{\min,o}}{2}},\sqrt{2\psi_{\max,o}}]$. Then, under
Conditions D.1 and D.2, $\widetilde{M}_{o}$ satisfies

$\displaystyle\left\|\ddot{X}_{o}\ddot{Z}_{o}^{\top}-\widetilde{M}_{o}\right\|_{F}\leq
C_{cvx}\frac{\kappa_{o}}{c_{\text{inj,o}}}\frac{1}{\sqrt{\psi_{\min,o}}}\left\|\nabla
f(\ddot{X}_{o},\ddot{Z}_{o})\right\|_{F}$

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

###### Proof.

This lemma is the simple modified version of Lemma 2 of Chen et al., 2020b .
If we follow their proof by setting $p=1$ and considering our observation
pattern with caution, we can get the result. To save space, we omit the proof.
∎

The following lemmas are used to show that our nonconvex estimator
$(\breve{X}_{o}\breve{H}_{o},\breve{Z}_{o}\breve{H}_{o})$ satisfies Conditions
D.1 and D.2. Lemma D.4 shows Condition D.1 (i) is satisfied when
$\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for a sufficiently
large constant $C_{\lambda}>0$. In addition, Lemma D.5 is used when we show
Condition D.1 (ii) and Condition D.2 are satisfied in the case
$(\ddot{X}_{o},\ddot{Z}_{o})=(\breve{X}_{o}\breve{H}_{o},\breve{Z}_{o}\breve{H}_{o})$.

######  Lemma D.4.

With probability at least $1-O(\min\\{N_{o}^{-101},T_{o}^{-101}\\})$, we have
(i)
$\left\|\mathcal{P}_{\Omega_{o}}(\mathbf{1}\mathbf{1}^{\top})-\mathbf{1}\mathbf{1}^{\top}\right\|\lesssim\sqrt{\max\\{N_{o},T_{o}\\}}$,
(ii)
$\left\|\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})\right\|\lesssim\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$.

###### Proof.

(i) All elements of
$\mathcal{P}_{\Omega_{o}}(\mathbf{1}\mathbf{1}^{\top})-\mathbf{1}\mathbf{1}^{\top}$
excluding the elements of $\\{(i,t_{o})\\}_{i\in\mathcal{Q}_{o}}$ are $0$.
Because the elements of $\\{(i,t_{o})\\}_{i\in\mathcal{Q}_{o}}$ are $-1$ and
$|\mathcal{Q}_{o}|\leq N_{o}$, it is trivial.
(ii) Denote a $N_{o}\times(T_{o}-1)$ matrix excluding the $t_{o}$-th column of
$\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})$ by
$\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})^{(-t_{o})}$. By Theorem 5.39 of
Vershynin, (2010), we have

$||\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})^{(-t_{o})}||=||\mathcal{E}_{o}^{(-t_{o})}||\lesssim\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$

where $\mathcal{E}_{o}^{(-t_{o})}$ is the $N_{o}\times(T_{o}-1)$ matrix
excluding the $t_{o}$-th column of $\mathcal{E}_{o}$. In addition, it is
trivial that

$||\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})_{\cdot,t_{o}}||\leq||(\mathcal{E}_{o})_{\cdot,t_{o}}||\lesssim\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$

where $\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})_{\cdot,t_{o}}$ and
$(\mathcal{E}_{o})_{\cdot,t_{o}}$ are the $t_{o}$-th column of
$\mathcal{P}_{\Omega_{o}}(\mathcal{E}_{o})$ and $\mathcal{E}_{o}$,
respectively. ∎

######  Lemma D.5.

Suppose that

$\displaystyle\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},\ \ \vartheta_{o}\mu_{o}r\ll\min\\{N_{o},T_{o}\\},$
$\displaystyle\min\\{N_{o}^{2},T_{o}^{2}\\}\gg\kappa_{o}^{4}\mu_{o}^{2}r^{2}\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}.$

Assume that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$. Further, let $T$ denote the tangent space
of $\ddot{X}\ddot{Z}_{o}^{\top}$. Then, with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\}$,

$\displaystyle\left\|\mathcal{P}_{\Omega_{o}}(\ddot{X}_{o}\ddot{Z}_{o}^{\top}-M_{o})-\ddot{X}_{o}\ddot{Z}_{o}^{\top}-M_{o}\right\|<\frac{1}{80}\lambda_{o}\quad\text{(Condition
\ref{cond:regularization} (ii))}$
$\displaystyle\left\|\mathcal{P}_{\Omega_{o}}(H)\right\|_{F}^{2}\geq\frac{1}{32\kappa_{o}}\left\|H\right\|_{F}^{2}\quad\text{for
all $H\in T$}\quad\text{(Condition \ref{cond:injectivity} with
$c_{\textrm{inj},o}=1/(32\kappa_{o})$)}$

hold uniformly for all $(\ddot{X}_{o},\ddot{Z}_{o})$ satisfying

$\displaystyle\max\Big{\\{}\left\|\ddot{X}_{o}-X_{o}\right\|_{2,\infty},\left\|\ddot{Z}_{o}-Z_{o}\right\|_{2,\infty}\Big{\\}}$
$\displaystyle\ \ \leq C\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\max\Big{\\{}\left\|X_{o}\right\|_{2,\infty},\left\|Z_{o}\right\|_{2,\infty}\Big{\\}}$
(D.2)

for some constant $C>0$.

###### Proof.

It follows immediately from Lemma D.6 and Lemma D.7. ∎

######  Lemma D.6.

Assume that $\min\\{N_{o},T_{o}\\}\gg\mu_{o}r\max\\{\log N_{o},\log T_{o}\\}$
and $\vartheta_{o}\mu_{o}r\ll\min\\{N_{o},T_{o}\\}$. Let $T$ denote the
tangent space of $\ddot{X}_{o}\ddot{Z}_{o}^{\top}$. Then, with probability at
least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\}$,

$\displaystyle\left\|\mathcal{P}_{\Omega_{o}}(H)\right\|_{F}^{2}\geq\frac{1}{32\kappa_{o}}\left\|H\right\|_{F}^{2}\quad\text{for
all $H\in T$}\quad\text{(Condition \ref{cond:injectivity} with
$c_{\textrm{inj}}=1/(32\kappa_{o})$)}$

holds uniformly for all $(\ddot{X}_{o},\ddot{Z}_{o})$ such that

$\displaystyle\max\Big{\\{}\left\|\ddot{X}_{o}-X_{o}\right\|_{2,\infty},\left\|\ddot{Z}_{o}-Z_{o}\right\|_{2,\infty}\Big{\\}}\leq\frac{c}{\kappa_{o}\sqrt{\max\\{N_{o},T_{o}\\}}}\left\|X_{o}\right\|$

where $c>0$ is some sufficiently small constant.

###### Proof.

This Lemma is the simple modification of Lemma 7 of Chen et al., 2020b . If we
follow their proof by considering our observation pattern cautiously, we can
get the result. Importantly, we use Lemma D.12 which is the modified version
of Corollary 4.3 of Candès and Recht, (2009) in the place where Chen et al.,
2020b  use Corollary 4.3 of Candès and Recht, (2009). To save space, we omit
the proof. ∎

######  Lemma D.7.

Assume that

$\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\kappa_{o}},\ \
\min\\{N_{o}^{2},T_{o}^{2}\\}\gg\kappa_{o}^{4}\mu_{o}^{2}r^{2}\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}.$

Let $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for some large
constant $C_{\lambda}>0$. Then, with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$,

$\left\|\mathcal{P}_{\Omega_{o}}(\ddot{X}_{o}\ddot{Z}_{o}^{\top}-M_{o})-\ddot{X}_{o}\ddot{Z}_{o}^{\top}-M_{o}\right\|\lesssim\sigma\sqrt{\max\\{N_{o},T_{o}\\}}\sqrt{\frac{\kappa_{o}^{4}\mu_{o}^{2}r^{2}\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}{\min\\{N_{o}^{2},T_{o}^{2}\\}}}<\frac{1}{80}\lambda_{o}$

holds uniformly for all $(\ddot{X}_{o},\ddot{Z}_{o})$ satisfying (D.2).

###### Proof.

This Lemma is the simple modification of Lemma 8 of Chen et al., 2020b . To
save space, we omit the proof. ∎

###  D.2 Quality of non-convex estimates

Before we proceed, we introduce some notations. Define an augmented loss
function $f_{\textrm{aug}}(A,B)$ to be

$f_{\textrm{aug}}\coloneqq\frac{1}{2}\left\|\mathcal{P}_{\Omega_{o}}(AB^{\top}-Y_{o})\right\|_{F}^{2}+\lambda_{o}\left\|A\right\|_{F}^{2}+\lambda_{o}\left\|B\right\|_{F}^{2}+\frac{1}{8}\left\|A^{\top}A-B^{\top}B\right\|_{F}^{2}.$

Then, the gradient of $f_{\textrm{aug}}(\cdot,\cdot)$ is given by

$\displaystyle\nabla_{X}f_{\textrm{aug}}(A,B)=\mathcal{P}_{\Omega_{o}}(AB^{\top}-Y_{o})B+\lambda_{o}A+\frac{1}{2}A(A^{\top}A-B^{\top}B),$
$\displaystyle\nabla_{Z}f_{\textrm{aug}}(A,B)=\mathcal{P}_{\Omega_{o}}(AB^{\top}-Y_{o}))^{\top}A+\lambda_{o}B+\frac{1}{2}B(B^{\top}B-A^{\top}A).$

The difference between gradients of $\nabla f(A,B)$ and $\nabla
f_{\textrm{aug}}(A,B)$ are

$\nabla_{X}f_{\textrm{diff}}(A,B)=-\frac{1}{2}A(A^{\top}A-B^{\top}B),\ \
\nabla_{Z}f_{\textrm{diff}}(A,B)=-\frac{1}{2}B(B^{\top}B-A^{\top}A).$

In addition, note that we have the following properties of $\mathcal{F}_{o}$:

$\displaystyle\psi_{1}(\mathcal{F}_{o})=\left\|\mathcal{F}_{o}\right\|=\sqrt{2\psi_{\max,o}},\
\ \psi_{r}(\mathcal{F}_{o})=\sqrt{2\psi_{\min,o}},\ \
\left\|\mathcal{F}_{o}\right\|_{2,\infty}\leq\sqrt{\frac{\mu
r\psi_{\max,o}}{\min\\{N_{o},T_{o}\\}}}.$

The following Lemma is the one of the main parts where we require the
condition $\min\\{N_{o},T_{o}\\}\gg\vartheta_{o}\kappa_{o}^{2}\mu_{o}r$. While
it is the modified version of Lemma 12 in Chen et al., 2020b , the proof of it
is quite different from theirs. Hence, we provide the full proof.

######  Lemma D.8.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$, $0<\eta_{o}\ll
1/(\kappa_{o}^{2}\psi_{\max,o}\min\\{N_{o},T_{o}\\})$,
$\min\\{N_{o},T_{o}\\}\gg\vartheta_{o}\kappa_{o}^{2}\mu_{o}r$, and

$\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},$
$\min\\{N_{o},T_{o}\\}\gg\kappa_{o}\mu_{o}r\max\\{\log^{3}N,\log^{3}T\\}.$

Suppose also that the iterates satisfy (A.18)-(A.25) at the $\tau$-th
iteration, then with probability at least
$1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\}),$ we have

$\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}\leq
C_{3}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}$

where $C_{3}$ is some sufficiently large constant.

###### Proof.

Fix $1\leq m\leq N_{o}+T_{o}$. The definition of $Q_{o}^{\tau+1,(m)}$ and the
unitary invariance of Frobenius norm yield

$\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}\leq\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau,(m)}\right\|_{F}.$

By the gradient update rules (A.3) and (A.4), we obtain

$\displaystyle\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau,(m)}$
$\displaystyle\ \ =\left(\mathcal{F}_{o}^{\tau}-\eta_{o}\nabla
f(\mathcal{F}_{o}^{\tau})\right)H_{o}^{\tau}-\left(\mathcal{F}_{o}^{\tau,(m)}-\eta_{o}\nabla
f^{(m)}(\mathcal{F}_{o}^{\tau,(m)})\right)Q_{o}^{\tau,(m)}$ $\displaystyle\ \
=\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\eta_{o}\nabla
f(\mathcal{F}_{o}^{\tau}H_{o}^{\tau})-\left(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\eta_{o}\nabla
f^{(m)}(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})\right)$ $\displaystyle\ \
=\underbrace{\left(\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right)-\eta_{o}\left(\nabla
f_{\textrm{aug}}(\mathcal{F}_{o}^{\tau}H_{o}^{\tau})-\nabla
f_{\textrm{aug}}(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})\right)}_{\coloneqq
A_{1}}$ $\displaystyle\quad-\underbrace{\eta_{o}\left(\nabla
f_{\textrm{diff}}(\mathcal{F}_{o}^{\tau}H_{o}^{\tau})-\nabla
f_{\textrm{diff}}(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})\right)}_{\coloneqq
A_{2}}+\underbrace{\eta_{o}\left(\nabla
f^{(m)}(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})-\nabla
f(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})\right)}_{\coloneqq A_{3}},$

Here, we use the facts that $\nabla f(\mathcal{A})O=\nabla f(\mathcal{A}O)$
and $\nabla f^{(m)}(\mathcal{A})O=\nabla f^{(m)}(\mathcal{A}O)$ for any
$(N_{o}+T_{o})\times r$ matrix $\mathcal{A}$ and any orthonormal matrix
$O\in\mathcal{O}^{r\times r}$. Hereinafter, we control $A_{1},A_{2}$ and
$A_{3}$ separately. The way of bounding $A_{1}$ and $A_{2}$ are the same as
the proof of Lemma 12 in Chen et al., 2020b  while the way of bounding $A_{3}$
is quite different.

  1. 1.

The first term $A_{1}$ can be bounded using the same derivation as
$\alpha_{1}$ in the proof of Lemma 10 of Chen et al., 2020b :

$\left\|A_{1}\right\|_{F}\leq\left(1-\frac{\psi_{\min,o}}{20}\eta_{o}\right)\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right\|_{\rm
F}$

with probability at least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$. Here, we
use the assumptions

$\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},$
$\min\\{N_{o},T_{o}\\}\gg\kappa_{o}\mu_{o}r\max\\{\log^{2}N_{o},\log^{2}T_{o}\\},$

and $0\leq\eta_{o}\ll 1/(\kappa_{o}^{2}\psi_{\max,o}\min\\{N_{o},T_{o}\\})$.

  2. 2.

Regarding $A_{2}$, the triangle inequality gives us, with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$,

$\left\|A_{2}\right\|_{F}\leq\eta_{o}\left\|\nabla
f_{\textrm{diff}}(\mathcal{F}_{o}^{\tau}H_{o}^{\tau})\right\|_{F}+\eta_{o}\left\|\nabla
f_{\textrm{diff}}(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})\right\|_{F}.$

Following the bound of $\alpha_{2}$ in the proof of Lemma 10 of Chen et al.,
2020b , we obtain

$\eta_{o}\left\|\nabla
f_{\textrm{diff}}(\mathcal{F}_{o}^{\tau}H_{o}^{\tau})\right\|_{F}\leq
2C_{B}\kappa_{o}\eta_{o}^{2}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\sqrt{r}\psi_{\max,o}^{2}\left\|X_{o}\right\|.$

Additionally, Lemma D.20 and the argument for bounding $\alpha_{2}$ in the
proof of Lemma 10 of Chen et al., 2020b  together give us

$\eta_{o}\left\|\nabla
f_{\textrm{diff}}(\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)})\right\|_{F}\leq
2C_{B}\kappa_{o}\eta_{o}^{2}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\sqrt{r}\psi_{\max,o}^{2}\left\|X_{o}\right\|.$

The three inequalities together allow us to have

$\displaystyle\left\|A_{2}\right\|_{F}$ $\displaystyle\leq
4C_{B}\kappa_{o}\eta_{o}^{2}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\sqrt{r}\psi_{\max,o}^{2}\left\|X_{o}\right\|$
$\displaystyle\leq\eta_{o}\left(\sigma\sqrt{\max\\{N_{o},T_{o}\\}}+\lambda_{o}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$

with probability at least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$, where
the last inequality follows from the assumption
$\eta_{o}\ll\frac{1}{\min\\{N_{o},T_{o}\\}\kappa_{o}^{2}\psi_{\max,o}}$.

  3. 3.

For bounding $A_{3}$, observe that

$\displaystyle A_{3}$
$\displaystyle=\eta_{o}\begin{bmatrix}\underbrace{\left(\mathcal{P}_{m,\cdot}(X_{o}^{\tau,(m)}Z_{o}^{\tau,(m)\top}-M_{o})-\mathcal{P}_{\Omega_{m,\cdot}}(X_{o}^{\tau,(m)}Z_{o}^{\tau,(m)\top}-M_{o})\right)Z_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}}_{\coloneqq
B_{1}}\\\
\underbrace{\left(\mathcal{P}_{m,\cdot}(X_{o}^{\tau,(m)}Z_{o}^{\tau,(m)\top}-M_{o})-\mathcal{P}_{\Omega_{m,\cdot}}(X_{o}^{\tau,(m)}Z_{o}^{\tau,(m)\top}-M_{o})\right)^{\top}X_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}}_{\coloneqq
B_{2}}\end{bmatrix}$ $\displaystyle\ \
+\eta_{o}\begin{bmatrix}\underbrace{\mathcal{P}_{\Omega_{m,\cdot}}(\mathcal{E}_{o})Z_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}}_{\coloneqq
C_{1}}\\\
\underbrace{\left(\mathcal{P}_{\Omega_{m,\cdot}}(\mathcal{E}_{o})\right)^{\top}X_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}}_{\coloneqq
C_{2}}\end{bmatrix}$

We invoke the following three claims to control $B_{1}$, $B_{2}$, and $C_{1}$,
$C_{2}$, whose proofs are provided after the proof of Lemma D.8.

######  Claim D.9.

Assume that

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}}.$

Then, for each $1\leq m\leq N_{o}+T_{o}$, we have

$\left\|B_{1}\right\|_{F}\lesssim\frac{\sqrt{\vartheta_{o}}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

######  Claim D.10.

Assume that

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}}.$

Then, for each $1\leq m\leq N_{o}+T_{o}$, we have

$\left\|B_{2}\right\|_{F}\lesssim\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

######  Claim D.11.

Assume that

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\max\\{N_{o},T_{o}\\}\gg\max\\{\log^{3}N_{o},\log^{3}T_{o}\\}.$

Then, for each $1\leq m\leq N_{o}+T_{o}$, we have

$\max\\{\left\|C_{1}\right\|_{F},\left\|C_{2}\right\|_{F}\\}\lesssim\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty},$

with probability at least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$.

Then, the triangle inequality yields, with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$

$\displaystyle\left\|A_{3}\right\|_{F}$
$\displaystyle\leq\eta_{o}(\left\|B_{1}\right\|_{F}+\left\|B_{2}\right\|_{F}+\left\|C_{1}\right\|_{F}+\left\|C_{2}\right\|_{F})$
$\displaystyle\lesssim\eta_{o}\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}+\eta_{o}\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\leq\eta_{o}\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}$ $\displaystyle\ \
+\eta_{o}\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}(C_{\infty}\kappa_{o}+C_{3})\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

Here, the last inequality follows from Lemma D.22 (i).

Combining the bounds on $A_{i}$, $i=1,2,3$, we reach, with probability at
least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$,

$\displaystyle\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}$
$\displaystyle\leq\left\|A_{1}\right\|_{F}+\left\|A_{2}\right\|_{F}+\left\|A_{3}\right\|_{F}$
$\displaystyle\leq\left(1-\frac{\psi_{\min,o}}{20}\eta_{o}\right)\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right\|_{F}$
$\displaystyle\ \
+\eta_{o}\left(\sigma\sqrt{\max\\{N_{o},T_{o}\\}}+\lambda_{o}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}+\widetilde{C}\eta_{o}\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\ \
+\widetilde{C}\eta_{o}\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}(C_{\infty}\kappa_{o}+C_{3})\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\leq\left(1-\frac{\psi_{\min,o}}{20}\eta_{o}\right)C_{3}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\ \
+\eta_{o}\left(\sigma\sqrt{\max\\{N_{o},T_{o}\\}}+\lambda_{o}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}+\widetilde{C}\eta_{o}\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\ \
+\widetilde{C}\eta_{o}\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}(C_{\infty}\kappa_{o}+C_{3})\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}$
$\displaystyle\leq C_{3}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}$

for some constant $\widetilde{C}>0$. The penultimate inequality uses the
induction hypothesis (A.20), and the last inequality holds provided that
$C_{3}$ is sufficiently large and
$\min\\{N_{o},T_{o}\\}\gg\vartheta_{o}\kappa_{o}^{2}\mu_{o}r$. Therefore, with
probability at least $1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\}),$ we have

$\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}\leq
C_{3}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

∎

###### Proof of Claim D.9.

Assume that $m\leq N_{o}$ and define $C\coloneqq
X_{o}^{\tau,(m)}Z_{o}^{\tau,(m)\top}-X_{o}Z_{o}^{\top}$ and
$\mathcal{X}\coloneqq\mathcal{P}_{\Omega_{m,\cdot}}(C)-\mathcal{P}_{m,\cdot}(C)$.
Using the unitary invariance of Frobenius norm, we have
$\left\|B_{1}\right\|_{F}=\Big{\lVert}\mathcal{X}Z_{o}^{\tau,(m)}\Big{\rVert}_{F}$.
First of all, if $m\notin\mathcal{Q}_{o}$, $\mathcal{X}=0$. Hence,
$\left\|B_{1}\right\|_{F}=0$. If $m\in\mathcal{Q}_{o}$, $\mathcal{X}$ has only
one nonzero element $-C_{lt_{o}}$. So, we have

$\left\|B_{1}\right\|_{F}=\left\|\mathcal{X}Z_{o}^{\tau,(m)}\right\|_{F}\leq\left\|C_{lt_{o}}Z^{\tau,(m)}_{o,t_{o},\cdot}\right\|_{2}\leq\left\|C\right\|_{\infty}\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}\leq
2\left\|C\right\|_{\infty}\left\|Z_{o}\right\|_{2,\infty}$

where $\left\|\cdot\right\|_{\infty}$ is the max norm, and the last inequality
follows from Lemma D.22 (iv) provided that

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}}.$

Additionally, observe that Lemma D.22 (iv) gives

$\displaystyle\left\|C\right\|_{\infty}$
$\displaystyle=\left\|X_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\left(Z_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right)^{\top}-X_{o}Z_{o}^{\top}\right\|_{\infty}$
$\displaystyle\leq\left\|X_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-X_{o}\right\|_{2,\infty}\left\|Z_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right\|_{2,\infty}+\left\|X_{o}\right\|_{2,\infty}\left\|Z_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-Z_{o}\right\|_{2,\infty}$
$\displaystyle\leq
3\left\|\mathcal{F}_{o}\right\|_{2,\infty}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

Finally, we have

$\displaystyle\left\|B_{1}\right\|_{F}\lesssim\left\|C\right\|_{\infty}\left\|Z_{o}\right\|_{2,\infty}\lesssim\left\|\mathcal{F}_{o}\right\|_{2,\infty}^{2}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}\lesssim\frac{\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

Now, assume that $N_{o}+1\leq m\leq N_{o}+T_{o}$ and define
$\breve{\mathcal{X}}\coloneqq\mathcal{P}_{\Omega_{\cdot,(m-N_{o})}}(C)-\mathcal{P}_{\cdot,(m-N_{o})}(C)$.
First, if $m\neq N_{o}+t_{o}$, $\breve{\mathcal{X}}=0$. If $m=N_{o}+t_{o}$, we
have

$\displaystyle\left\|B_{1}\right\|_{F}=\left\|\breve{\mathcal{X}}Z_{o}^{\tau,(m)}\right\|_{F}=\left\|\begin{bmatrix}(\omega_{1t_{o}}-1)C_{1,t_{o}}\\\
\vdots\\\
(\omega_{N_{o}t_{o}}-1)C_{N_{o},t_{o}}\end{bmatrix}Z^{\tau,(m)}_{o,t_{o},\cdot}\right\|_{F}\leq\left\|\begin{bmatrix}(\omega_{1t_{o}}-1)C_{1,t_{o}}\\\
\vdots\\\
(\omega_{N_{o}t_{o}}-1)C_{N_{o},t_{o}}\end{bmatrix}\right\|_{2}\left\|Z^{\tau,(m)}_{o,t_{o},\cdot}\right\|_{2},$

Then, since

$\displaystyle\left\|\begin{bmatrix}(\omega_{1t_{o}}-1)C_{1,t_{o}}\\\
\vdots\\\
(\omega_{N_{o}t_{o}}-1)C_{N_{o},t_{o}}\end{bmatrix}\right\|_{2}\left\|Z^{\tau,(m)}_{o,t_{o},\cdot}\right\|_{2}\leq\sqrt{\sum_{i\in\mathcal{Q}_{o}}C_{i,t_{o}}^{2}}\left\|Z^{\tau,(m)}_{o,t_{o},\cdot}\right\|_{2}\leq\sqrt{\vartheta_{o}}\left\|C\right\|_{\infty}\left\|Z_{o}\right\|_{2,\infty},$

we can obtain

$\left\|B_{1}\right\|_{F}\lesssim\frac{\sqrt{\vartheta_{o}}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

∎

###### Proof of Claim D.10.

First, assume that $m\leq N_{o}$. We follow the notation in the proof of Claim
D.9. When $m\notin\mathcal{Q}_{o}$, $X=0$. If $m\in\mathcal{Q}_{o}$, we have

$\displaystyle\left\|B_{2}\right\|_{F}$
$\displaystyle=\left\|\breve{\mathcal{X}}^{\top}X_{o}^{\tau,(m)}\right\|_{F}=\left\|\begin{bmatrix}0\\\
\vdots\\\ -C_{mt_{o}}\\\ \vdots\\\
0\end{bmatrix}X^{\tau,(m)}_{o,m,\cdot}\right\|_{F}\leq
2\left\|C\right\|_{\infty}\left\|X_{o}\right\|_{2,\infty}.$

So, we have

$\left\|B_{2}\right\|_{F}\lesssim\frac{\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

Assume now that $N_{o}+1\leq m\leq N_{o}+T_{o}$. Using the unitary invariance
of Frobenius norm, we have
$\left\|B_{2}\right\|_{F}=\Big{\lVert}\breve{\mathcal{X}}^{\top}X_{o}^{\tau,(m)}\Big{\rVert}_{F}$.
If $m\neq N_{o}+t_{o}$, then $\breve{\mathcal{X}}=0$. In addition, if
$m=N_{o}+t_{o}$, we obtain

$\left\|B_{2}\right\|_{F}=\left\|\breve{\mathcal{X}}^{\top}X_{o}^{\tau,(m)}\right\|_{F}=\left\|\sum_{i=1}^{N_{o}}\breve{\mathcal{X}}_{i,\cdot}^{\top}X^{\tau,(m)}_{o,i,\cdot}\right\|_{F}=\left\|\sum_{i\in\mathcal{Q}_{o}}-C_{i,t_{o}}X^{\tau,(m)}_{o,i,\cdot}\right\|_{2}\leq
2\vartheta_{o}\left\|C\right\|_{\infty}\left\|X_{o}\right\|_{2,\infty}.$

Therefore, we have

$\left\|B_{2}\right\|_{F}\lesssim\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\psi_{\max,o}\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}.$

∎

###### Proof of Claim D.11.

First, we bound $C_{1}$. Assume that $m\leq N_{o}$. Since Frobenius norm is
unitary invariant, we have

$\left\|C_{1}\right\|_{F}=\left\|\mathcal{P}_{\Omega_{m,\cdot}}(\mathcal{E}_{o})Z_{o}^{\tau,(m)}\right\|_{F}=\left\|\sum_{t=1}^{T_{o}}\underbrace{\omega_{mt}\epsilon_{mt}Z^{\tau,(m)}_{o,t,\cdot}}_{u_{mt}}\right\|_{2}.$

By the way of construction of leave-one-out estimates,
$\\{\epsilon_{mt}\\}_{1\leq t\leq T_{o}}$ are independent of
$Z_{o}^{\tau,(m)}$. Therefore, we have
$\mathbb{E}\left[\epsilon_{mt}\left|Z_{o}^{\tau,(m)}\right.\right]=\mathbb{E}\left[\epsilon_{mt}\right]=0$,
and conditioning on $Z_{o}^{\tau,(m)}$, $\\{\epsilon_{mt}\\}_{1\leq t\leq
T_{o}}$ are independent across $t$. Hence, conditioning on $Z_{o}^{\tau,(m)}$,
we can exploit the matrix Bernstein inequality (Koltchinskii et al.,, 2011,
Proposition 2). Note that

$\left\|\left\|u_{mt}\right\|_{2}\right\|_{\text{subE}}\leq\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}\left\|\omega_{mt}\epsilon_{mt}\right\|_{\text{subE}}\lesssim\sigma\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty},$

where $\left\|\cdot\right\|_{\text{subE}}$ denotes the sub-exponential norm;
see Koltchinskii et al., (2011); Tropp et al., (2015). Further, we can see
that

$\left\|\sum_{t=1}^{T_{o}}\omega_{mt}^{2}\mathbb{E}\left[\epsilon_{mt}^{2}\left|Z_{o}^{\tau,(m)}\right.\right]Z^{\tau,(m)}_{o,t,\cdot}Z^{\tau,(m)\top}_{o,t,\cdot}\right\|\lesssim\sigma^{2}\left\|\sum_{t=1}^{T_{o}}Z^{\tau,(m)}_{o,t,\cdot}Z^{\tau,(m)\top}_{o,t,\cdot}\right\|=\sigma^{2}\left\|Z_{o}^{\tau,(m)}\right\|_{F}^{2}.$

Then, the matrix Bernstein inequality reveals that, with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$,

$\displaystyle\left\|\sum_{t=1}^{T_{o}}u_{mt}\right\|_{2}$
$\displaystyle\lesssim\sqrt{\sigma^{2}\left\|Z_{o}^{\tau,(m)}\right\|_{F}^{2}\max\\{\log
N_{o},\log
T_{o}\\}}+\sigma\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\}$
$\displaystyle\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty},$

where the last relation uses the assumption
$\max\\{N_{o},T_{o}\\}\gg\max\\{\log^{3}N_{o},\log^{3}T_{o}\\}$. Applying
Lemma D.22 (iv) with the assumption

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},$

we reach, with probability at least
$1-O\left(\min\\{N_{o}^{-100},T_{o}^{-100}\\}\right)$,

$\left\|C_{1}\right\|_{F}\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

Now, we consider the case of $m\geq N_{o}+1$. Since Frobenius norm is unitary
invariant and only the $(m-N_{o})$-th column of the matrix
$\mathcal{P}_{\Omega_{\cdot,(m-N_{o})}}(\mathcal{E}_{o})$ has nonzero
elements,

$\displaystyle\left\|C_{1}\right\|_{F}$
$\displaystyle=\left\|\mathcal{P}_{\Omega_{\cdot,(m-N_{o})}}(\mathcal{E}_{o})Z_{o}^{\tau,(m)}\right\|_{F}=\left\|\begin{bmatrix}\omega_{1,(m-N_{o})}\epsilon_{1,(m-N_{o})}\\\
\vdots\\\
\omega_{N_{o},(m-N_{o})}\epsilon_{N_{o},(m-N_{o})}\end{bmatrix}Z^{\tau,(m)}_{o,(m-N_{o}),\cdot}\right\|_{F}$
$\displaystyle\leq\left\|\sum_{i=1}^{N_{o}}\underbrace{e_{i}\omega_{i,(m-N_{o})}\epsilon_{i,(m-N_{o})}Z^{\tau,(m)}_{o,(m-N_{o}),\cdot}}_{\coloneqq
u_{i,(m-N_{o})}}\right\|_{F}.$

Similarly, conditioning on $\\{Z_{o}^{\tau,(m)}\\}$, we can exploit the matrix
Bernstein inequality (Koltchinskii et al.,, 2011, Proposition 2). Note that

$\left\|\left\|u_{i,(m-N_{o})}\right\|_{F}\right\|_{\text{subE}}\leq\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}\left\|\epsilon_{i,(m-N_{o})}\right\|_{\text{subE}}\lesssim\sigma\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}\text{
and }$
$\displaystyle\left\|\sum_{i=1}^{N_{o}}\omega_{i,(m-N_{o})}\mathbb{E}\left[\epsilon_{i,(m-N_{o})}^{2}\left|Z_{o}^{\tau,(m)}\right.\right]e_{i}Z^{\tau,(m)}_{o,(m-N_{o}),\cdot}Z^{\tau,(m)\top}_{o,(m-N_{o}),\cdot}e_{i}^{\top}\right\|\lesssim
N_{o}\sigma^{2}\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}^{2}.$

Then, the matrix Bernstein inequality reveals that, with probability at least
$1-O(\min\\{N_{o}^{-101},T_{o}^{-101}\\})$,

$\displaystyle\left\|\sum_{i=1}^{N_{o}}u_{i,(m-N_{o})}\right\|_{F}$
$\displaystyle\lesssim\sqrt{\sigma^{2}\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}^{2}\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}+\sigma\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\}$
$\displaystyle\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|Z_{o}^{\tau,(m)}\right\|_{2,\infty},$

where the last relation uses the assumption
$\max\\{N_{o},T_{o}\\}\gg\max\\{\log^{3}N_{o},\log^{3}T_{o}\\}$. Applying
Lemma D.22 (iv) with the assumption

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},$

we reach, with probability at least
$1-O\left(\min\\{N_{o}^{-100},T_{o}^{-100}\\}\right)$,

$\left\|C_{1}\right\|_{F}\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

We turn to $C_{2}$. Assume $m\leq N_{o}$. Since Frobenius norm is unitary
invariant, we have

$\displaystyle\left\|C_{2}\right\|_{F}$
$\displaystyle=\left\|\left(\mathcal{P}_{\Omega_{m,\cdot}}(\mathcal{E}_{o})\right)^{\top}X_{o}^{\tau,(m)}\right\|_{F}=\left\|\begin{bmatrix}\omega_{m1}\epsilon_{m1}\\\
\vdots\\\
\omega_{mt}\epsilon_{mt}\end{bmatrix}X^{\tau,(m)}_{o,m,\cdot}\right\|_{F}=\left\|\sum_{t=1}^{T_{o}}\underbrace{e_{t}\omega_{mt}\epsilon_{mt}X^{\tau,(m)}_{o,m,\cdot}}_{\coloneqq
u_{mt}}\right\|_{F}.$

Similarly, conditioning on $X_{o}^{\tau,(m)}$, we can exploit the matrix
Bernstein inequality. Note that
$\left\|\left\|u_{mt}\right\|_{F}\right\|_{\text{subE}}\lesssim\sigma\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty}$
and

$\left\|\sum_{t=1}^{T_{o}}\omega_{mt}\mathbb{E}\left[\epsilon_{mt}^{2}\left|X_{o}^{\tau,(m)}\right.\right]e_{t}X^{\tau,(m)}_{o,m,\cdot}X^{\tau,(m)\top}_{o,m,\cdot}e_{t}^{\top}\right\|\lesssim\sigma^{2}\left\|\sum_{t=1}^{T_{o}}X^{\tau,(m)}_{o,m,\cdot}X^{\tau,(m)\top}_{o,m,\cdot}\right\|\leq
T_{o}\sigma^{2}\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty}^{2}.$

Then, the matrix Bernstein inequality reveals that, with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$,

$\displaystyle\left\|\sum_{t=1}^{T_{o}}u_{t}\right\|_{F}$
$\displaystyle\lesssim\sqrt{\sigma^{2}\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty}^{2}\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}+\sigma\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\}$
$\displaystyle\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty},$

where the last relation uses the assumption
$\max\\{N_{o},T_{o}\\}\gg\max\\{\log^{3}N_{o},\log^{3}T_{o}\\}$. Applying
Lemma D.22 (iv) with the assumption

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},$

we reach, with probability at least
$1-O\left(\min\\{N_{o}^{-100},T_{o}^{-100}\\}\right)$,

$\left\|C_{2}\right\|_{F}\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

Now, assume that $m\geq N_{o}+1$. Since Frobenius norm is unitary invariant
and only $(m-N_{o})$-th column of the matrix
$\mathcal{P}_{\Omega_{\cdot,(m-N_{o})}}(\mathcal{E}_{o})$ has nonzero
elements,

$\displaystyle\left\|C_{2}\right\|_{F}$
$\displaystyle=\left\|\left(\mathcal{P}_{\Omega_{\cdot,(m-N_{o})}}(\mathcal{E}_{o})\right)^{\top}X_{o}^{\tau,(m)}\right\|_{F}=\left\|\sum_{i=1}^{N_{o}}\underbrace{\omega_{i,(m-N_{o})}\epsilon_{i,(m-N_{o})}X^{\tau,(m)}_{o,i,\cdot}}_{\coloneqq
u_{i,(m-N_{o})}}\right\|_{2}.$

Conditioning on $X_{o}^{\tau,(m)}$, the matrix Bernstein inequality reveals
that, with probability at least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\})$,

$\displaystyle\left\|\sum_{i=1}^{N_{o}}u_{i,(m-N_{o})}\right\|_{2}$
$\displaystyle\lesssim\sqrt{\sigma^{2}\left\|X_{o}^{\tau,(m)}\right\|_{F}^{2}\max\\{\log
N_{o},\log
T_{o}\\}}+\sigma\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\}$
$\displaystyle\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|X_{o}^{\tau,(m)}\right\|_{2,\infty},$

where the last relation uses the assumption
$\max\\{N_{o},T_{o}\\}\gg\max\\{\log^{3}N_{o},\log^{3}T_{o}\\}$. Applying
Lemma D.22 (iv) with the assumption

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},$

we reach, with probability at least
$1-O\left(\min\\{N_{o}^{-100},T_{o}^{-100}\\}\right)$,

$\left\|C_{2}\right\|_{F}\lesssim\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

∎

The following two lemmas are the modifications of Section 4.2 of Candès and
Recht, (2009) for our missing pattern. The way of proof is different from that
of Candès and Recht, (2009) since we assume missing not at random. These
lemmas are used in many parts of proofs.

######  Lemma D.12.

Define
$\mathcal{P}_{T^{*}}(A)=U_{o}U_{o}^{\top}A+AV_{o}V_{o}^{\top}-U_{o}U_{o}^{\top}AV_{o}V_{o}^{\top}$.
Assume that $\frac{\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}\ll 1$. Then,
we have

$\displaystyle\sqrt{\frac{99}{100}}\left\|\mathcal{P}_{T^{*}}(A)\right\|_{F}\leq\left\|\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}(A)\right\|_{F}\leq\sqrt{\frac{101}{100}}\left\|\mathcal{P}_{T^{*}}(A)\right\|_{F}.$
(D.3)

###### Proof.

We have by Lemma D.13

$\displaystyle\big{|}\left\|\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}(A)\right\|_{F}^{2}-\left\|\mathcal{P}_{T^{*}}(A)\right\|_{F}^{2}\big{|}$
$\displaystyle=\big{|}\langle\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}(A),\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}(A)\rangle-\langle\mathcal{P}_{T^{*}}(A),\mathcal{P}_{T^{*}}(A)\rangle\big{|}$
$\displaystyle=\big{|}\langle(\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}})(A),\mathcal{P}_{T^{*}}(A)\rangle\big{|}$
$\displaystyle=\big{|}\langle(\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}})(A),\mathcal{P}_{T^{*}}(A)\rangle\big{|}$
$\displaystyle\leq\left\|(\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}})(A)\right\|_{F}\left\|\mathcal{P}_{T^{*}}(A)\right\|_{F}$
$\displaystyle\leq\left\|\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}}\right\|\left\|\mathcal{P}_{T^{*}}(A)\right\|_{F}^{2}$
$\displaystyle\leq 0.01\left\|\mathcal{P}_{T^{*}}(A)\right\|_{F}^{2}.$

∎

######  Lemma D.13.

Under the incoherence assumption, we have

$\left\|\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}}\right\|\leq\frac{2\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}.$

###### Proof.

Let $(e_{i}^{N_{o}})_{i\in[N_{o}]},(e_{t}^{T_{o}})_{t\in[T_{o}]}$ be the
standard basis vectors for $\mathbb{R}^{N_{o}}$ and $\mathbb{R}^{T_{o}}$,
respectively. Then $A\in\mathbb{R}^{N_{o}\times T_{o}}$ can be written as
$A=\sum_{(i,t)\in[N_{o}]\times[T_{o}]}\langle
A,e^{N_{o}}_{i}e^{T_{o}\top}_{t}\rangle e^{N_{o}}_{i}e^{T_{o}\top}_{t}$.
Further, we can readily obtain

$\displaystyle\mathcal{P}_{T^{*}}(A)=\sum_{i,t}\langle\mathcal{P}_{T^{*}}(A),e^{N_{o}}_{i}e^{T_{o}\top}_{t}\rangle
e^{N_{o}}_{i}e^{T_{o}\top}_{t}=\sum_{i,t}\langle
A,\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})\rangle
e^{N_{o}}_{i}e^{T_{o}\top}_{t},$
$\displaystyle\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}(A)=\sum_{i,t}\omega_{it}\langle
A,\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})\rangle
e^{N_{o}}_{i}e^{T_{o}\top}_{t},\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}(A)=\sum_{i,t}\omega_{it}\langle
A,\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})\rangle\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t}).$

By defining an outer product $\otimes$ as $(A\otimes B)(C)=\langle B,C\rangle
A$, we also have

$\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}=\sum_{i,t}\omega_{it}\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})$

and
$\mathcal{P}_{T^{*}}=\sum_{i,t}\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})$.
Hence, we have

$\displaystyle\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}}=\sum_{i,t}(\omega_{it}-1)\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t})=\sum_{i\in\mathcal{Q}_{o}}\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}}).$

By the definition of $\mathcal{P}_{T^{*}}$,

$\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|_{F}^{2}=\langle\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}}),e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}}\rangle=\left\|U_{o}U_{o}^{\top}e^{N_{o}}_{i}\right\|^{2}+\left\|V_{o}V_{o}^{\top}e^{T_{o}\top}_{t_{o}}\right\|^{2}-\left\|U_{o}U_{o}^{\top}e^{N_{o}}_{i}\right\|^{2}\left\|V_{o}V_{o}^{\top}e^{T_{o}\top}_{t_{o}}\right\|^{2}.$

Due to the incoherence condition,
$\left\|U_{o}U_{o}^{\top}e_{i}^{N_{o}}\right\|^{2}\leq\mu_{o}r/N_{o}$ and
$\left\|V_{o}V_{o}^{\top}e_{t_{o}}^{T_{o}}\right\|^{2}\leq\mu_{o}r/T_{o}$.
Then, we have

$\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|_{F}^{2}\leq
2\mu_{o}r/\min\\{N_{o},T_{o}\\}.$

Note that

$\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|=\sup\langle
B_{1},\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\rangle\langle\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}}),B_{2}\rangle$

where the supremum is taken over a countable collection of matrices $B_{1}$
and $B_{2}$ such that $\left\|B_{1}\right\|_{F}\leq 1$ and
$\left\|B_{2}\right\|_{F}\leq 1$. Then, for all $i\in\mathcal{Q}_{o}$, we have

$\displaystyle\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|$
$\displaystyle\leq|\langle
B_{1},\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\rangle||\langle\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}}),B_{2}\rangle|$
$\displaystyle\leq\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|_{F}^{2}$
$\displaystyle\leq\frac{2\mu_{o}r}{\min\\{N_{o},T_{o}\\}}.$

Hence, we have

$\displaystyle\left\|\mathcal{P}_{T^{*}}\mathcal{P}_{\Omega_{o}}\mathcal{P}_{T^{*}}-\mathcal{P}_{T^{*}}\right\|$
$\displaystyle\leq\sum_{i\in\mathcal{Q}_{o}}\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|$
$\displaystyle\leq\vartheta_{o}\max_{i\in\mathcal{Q}_{o}}\left\|\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\otimes\mathcal{P}_{T^{*}}(e^{N_{o}}_{i}e^{T_{o}\top}_{t_{o}})\right\|$
$\displaystyle\leq\frac{2\vartheta_{o}\mu_{o}r}{\min\\{N_{o},T_{o}\\}}.$

∎

The following lemma is a simple modification of Lemma D.19. Using this lemma,
we can change $\left\|\mathcal{F}_{o}\right\|_{2,\infty}$ with
$\left\|X_{o}\right\|_{2,\infty}$ and $\left\|Z_{o}\right\|_{2,\infty}$ at the
cost of having an additional term $\sqrt{r}$.

######  Lemma D.14.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$, $0<\eta_{o}\ll
1/(\kappa_{o}^{2}\psi_{\max,o}\min\\{N_{o},T_{o}\\})$,
$\min\\{N_{o},T_{o}\\}\gg\vartheta_{o}\kappa_{o}^{2}\mu_{o}r$, and

$\displaystyle\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\min\\{N_{o},T_{o}\\}\gg\kappa_{o}\mu_{o}r\max\\{\log^{3}N,\log^{3}T\\}.$

Suppose also that the iterates satisfy (A.18)-(A.25) at the $\tau$-th
iteration, then with probability at least
$1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\}),$ we have

$\displaystyle\left\|X_{o}^{\tau+1}H_{o}^{\tau+1}-X_{o}\right\|_{2,\infty}\leq
C_{\infty,X}r^{1/2}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty},$
$\displaystyle\left\|Z_{o}^{\tau+1}H_{o}^{\tau+1}-Z_{o}\right\|_{2,\infty}\leq
C_{\infty,Z}r^{1/2}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|Z_{o}\right\|_{2,\infty},$

where $C_{\infty,X}$ and $C_{\infty,Z}$ are some sufficiently large constants.

###### Proof.

By some modification of Lemma D.8, we can have

$\displaystyle\max_{1\leq m\leq
N_{o}}\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}\leq
C_{3,X}\sqrt{r}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty},$
$\displaystyle\max_{N_{o}+1\leq m\leq
T_{o}}\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}$
$\displaystyle\ \ \leq C_{3,Z}\sqrt{r}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|Z_{o}\right\|_{2,\infty}.$

In addition, by some modification of Lemma D.18, we have

$\displaystyle\max_{1\leq m\leq
N_{o}}\left\|\left(\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}-\mathcal{F}_{o}\right)_{m,\cdot}\right\|_{2}\leq
C_{4,X}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty},$
$\displaystyle\max_{N_{o}+1\leq m\leq
T_{o}}\left\|\left(\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}-\mathcal{F}_{o}\right)_{m,\cdot}\right\|_{2}\leq
C_{4,Z}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|Z_{o}\right\|_{2,\infty}.$

Then, when $1\leq m\leq N_{o}$, we have with probability at least
$1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\})$

$\displaystyle\left\|\left(X_{o}^{\tau+1}H_{o}^{\tau+1}-X_{o}\right)_{m,\cdot}\right\|_{2}$
$\displaystyle\leq\left\|\left(\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}\right)_{m,\cdot}\right\|_{2}$
$\displaystyle\leq\left\|\left(\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}\right)_{m,\cdot}\right\|_{2}+\left\|\left(\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}-\mathcal{F}_{o}\right)_{m,\cdot}\right\|_{2}$
$\displaystyle\leq\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}\right\|_{F}$
$\displaystyle\ \
+C_{4,\infty}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty},$
(D.4)

For the first term, use Lemma D.22 to have, with probability at least
$1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\})$

$\displaystyle\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}\right\|_{F}$
$\displaystyle\leq
5\kappa_{o}\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}^{\tau+1,(m)}Q_{o}^{\tau+1,(m)}\right\|_{F}$
$\displaystyle\leq
5\kappa_{o}C_{3,X}\sqrt{r}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty}$
(D.5)

Then, (D.4) and (D.5) collectively reveal that, with probability at least
$1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\})$,

$\displaystyle\left\|\left(X_{o}^{\tau+1}H_{o}^{\tau+1}-X_{o}\right)_{m,\cdot}\right\|_{2}\leq
C_{\infty,X}\sqrt{r}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{2,\infty}$

under the assumption that $C_{\infty,X}\geq 5C_{3,X}+C_{4,X}$. Similarly, we
can show the bound for
$\left\|\left(Z_{o}^{\tau+1}H_{o}^{\tau+1}-Z_{o}\right)_{m,\cdot}\right\|_{2}$.
∎

The following lemmas are the simple modified versions of the lemmas in Chen et
al., 2020b . With the aids of Lemmas D.12 and D.13, if we follow their proofs
by setting $p=1$ while considering our observation pattern cautiously, we can
get the results. To save space, we omit the proofs. However, we are willing to
provide the full proofs upond request.

######  Lemma D.15.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$, $\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern
2.0mu=\max\\{N_{o}^{23},T_{o}^{23}\\}$ and
$\eta_{o}\overset{c}{\asymp}1/\max\\{N_{o}^{6},T_{o}^{6}\\}\kappa_{o}^{3}\psi_{\max,o}$.
Suppose also that

$\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\min\\{N_{o},T_{o}\\}\gg\mu_{o}r\kappa_{o}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\},$

and the induction hypotheses (A.18)-(A.25) hold for all $0\leq\tau\leq\mkern
2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern 2.0mu$ and (A.26) holds for
all $1\leq\tau\leq\mkern 2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern
2.0mu$. Then there is a constant $C_{gr}>0$ such that

$\min_{0\leq\tau<\mkern 2.0mu\overline{\mkern-2.0mu\tau\mkern-2.0mu}\mkern
2.0mu}\left\|\nabla f(X_{o}^{\tau},Z_{o}^{\tau})\right\|_{F}\leq
C_{gr}\frac{1}{\max\\{N_{o}^{5},T_{o}^{5}\\}}\lambda_{o}\sqrt{\psi_{\min,o}}.$

######  Lemma D.16.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$,

$\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\min\\{N_{o},T_{o}\\}\gg\mu_{o}r\kappa_{o}\max\\{\log^{2}N_{o},\log^{2}T_{o}\\}$

and $0<\eta_{o}\ll 1/(\kappa_{o}^{5/2}\psi_{\max,o})$. Suppose also that the
iterates satisfy (A.18)-(A.25) at the $\tau$-th iteration, then with
probability at least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\}),$

$\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}\right\|_{F}\leq
C_{F}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|_{F},$

where $C_{F}>0$ is large enough.

######  Lemma D.17.

Suppose $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for some
large constant $C_{\lambda}>0$,

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\min\\{N_{o}^{2},T_{o}^{2}\\}\gg\kappa_{o}^{4}\mu_{o}^{2}r^{2}\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\},$

and $0<\eta_{o}\ll 1/(\kappa_{o}^{3}\psi_{\max,o}\sqrt{r})$. Suppose also that
the iterates satisfy (A.18)-(A.25) at the $\tau$-th iteration, then with
probability at least $1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\}),$

$\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}\right\|\leq
C_{op}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|$

provided that $C_{op}$ is sufficiently large.

######  Lemma D.18.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$,

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\min\\{N_{o}^{2},T_{o}^{2}\\}\gg\kappa_{o}^{2}\mu_{o}^{2}r^{2}\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\},$

and $0<\eta_{o}\ll 1/(\kappa_{o}^{2}\sqrt{r}\psi_{\max,o})$. Suppose also that
the iterates satisfy (A.18)-(A.25) at the $\tau$-th iteration, then with
probability at least $1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\}),$

$\max_{1\leq m\leq
N_{o}+T_{o}}\left\|\left(\mathcal{F}_{o}^{\tau+1,(m)}H_{o}^{\tau+1,(m)}-\mathcal{F}_{o}\right)_{m,\cdot}\right\|_{2}\leq
C_{4}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

######  Lemma D.19.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$,

$\displaystyle\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},$
$\displaystyle\min\\{N_{o}^{2},T_{o}^{2}\\}\gg\kappa_{o}^{4}\mu_{o}^{2}r^{2}\max\\{N_{o}\log^{2}N_{o},T_{o}\log^{2}T_{o}\\}.$

Suppose also that the iterates satisfy (A.18)-(A.25) at the $\tau$-th
iteration, then with probability at least
$1-O(\min\\{N_{o}^{-98},T_{o}^{-98}\\}),$

$\left\|\mathcal{F}_{o}^{\tau+1}H_{o}^{\tau+1}-\mathcal{F}_{o}\right\|_{2,\infty}\leq
C_{\infty}\kappa_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o}\log N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$

holds as long as $C_{\infty}\geq 5C_{3}+C_{4}$.

######  Lemma D.20.

Suppose $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for some
large constant $C_{\lambda}>0$,

$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\sqrt{\kappa_{o}^{2}\max\\{\log
N_{o},\log T_{o}\\}}},\ \
\min\\{N_{o}^{2},T_{o}^{2}\\}\gg\kappa_{o}^{2}\mu_{o}^{2}r^{2}\max\\{N_{o}\log
N_{o},T_{o}\log T_{o}\\},$

and $0<\eta_{o}<1/\psi_{\min,o}$. Suppose also that the iterates satisfy
(A.18)-(A.25) at the $\tau$-th iteration, then with probability at least
$1-O(\min\\{N_{o}^{-100},T_{o}^{-100}\\}),$

$\displaystyle\left\|X_{o}^{\tau+1\top}X_{o}^{\tau+1}-Z_{o}^{\tau+1\top}Z_{o}^{\tau+1}\right\|_{F}\leq
C_{B}\kappa_{o}\eta_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\sqrt{r}\psi_{\max,o}^{2}$
$\displaystyle\max_{1\leq m\leq
N_{o}+T}\left\|X_{o}^{\tau+1,(m)\top}X_{o}^{\tau+1,(m)}-Z_{o}^{\tau+1,(m)\top}Z_{o}^{\tau+1,(m)}\right\|_{F}\leq
C_{B}\kappa_{o}\eta_{o}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\sqrt{r}\psi_{\max,o}^{2}$

holds true as long as $C_{B}\gg C_{op}^{2}$.

######  Lemma D.21.

Suppose that $\lambda_{o}=C_{\lambda}\sigma\sqrt{\max\\{N_{o},T_{o}\\}}$ for
some large constant $C_{\lambda}>0$,

$\frac{\sigma}{\psi_{\min,o}}\sqrt{\frac{\max\\{N_{o}^{2},T_{o}^{2}\\}}{\min\\{N_{o},T_{o}\\}}}\ll\frac{1}{\sqrt{\kappa_{o}^{4}\mu_{o}r\max\\{\log
N_{o},\log T_{o}\\}}},$

and $0<\eta_{o}\ll 1/(q\psi_{\max,o}\max\\{N_{o},T_{o}\\})$. Suppose also that
the iterates satisfy (A.18)-(A.25) at the $\tau$-th iteration, then with
probability at least $1-O(\min\\{N_{o}^{-99},T_{o}^{-99}\\}),$

$\displaystyle f(X_{o}^{\tau+1},Z_{o}^{\tau+1})\leq
f(X_{o}^{\tau},Z_{o}^{\tau})-\frac{\eta_{o}}{2}\left\|\nabla
f(X_{o}^{\tau},Z_{o}^{\tau})\right\|_{F}^{2}.$

######  Lemma D.22.

Throughout the set of results, we assume that the $\tau$-th iterates satisfy
the induction hypotheses (A.18)-(A.25).

  1. (i)

Suppose that $\min\\{N_{o},T_{o}\\}\gg\mu_{o}r\max\\{\log N_{o},\log
T_{o}\\}$. Then, we obtain

$\displaystyle\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|_{2,\infty}\leq(C_{\infty}\kappa_{o}+C_{3})\left(\frac{\sigma\sqrt{\max\\{N_{o}\log
N_{o},T_{o}\log
T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
$\displaystyle\left\|\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}-\mathcal{F}_{o}\right\|\leq
2C_{op}\left(\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}+\frac{\lambda_{o}}{\psi_{\min,o}}\right)\left\|X_{o}\right\|.$

  2. (ii)

Suppose that
$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\kappa_{o}\sqrt{\max\\{\log
N_{o},\log T_{o}\\}}}$. Then, we have

$\displaystyle\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}\right\|\leq\left\|X_{o}\right\|,\quad\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}\right\|_{F}\leq\left\|X_{o}\right\|_{F},\quad\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}\right\|_{2,\infty}\leq\left\|\mathcal{F}_{o}\right\|_{2,\infty},$
(D.6) $\displaystyle\left\|\mathcal{F}_{o}^{\tau}\right\|\leq
2\left\|X_{o}\right\|,\quad\left\|\mathcal{F}_{o}^{\tau}\right\|_{F}\leq
2\left\|X_{o}\right\|_{F},\quad\left\|\mathcal{F}_{o}^{\tau}\right\|_{2,\infty}\leq
2\left\|\mathcal{F}_{o}\right\|_{2,\infty}.$ (D.7)

  3. (iii)

Suppose that
$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\kappa_{o}\sqrt{\max\\{\log
N_{o},\log T_{o}\\}}}$ and $\sqrt{\frac{\mu_{o}r}{\min\\{N_{o},T_{o}\\}}}\ll
1$. Then, we have

$\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}H_{o}^{\tau,(m)}\right\|_{F}\leq
5\kappa_{o}\left\|\mathcal{F}_{o}^{\tau}H_{o}^{\tau}-\mathcal{F}_{o}^{\tau,(m)}Q_{o}^{\tau,(m)}\right\|_{F}.$

  4. (iv)

Suppose that
$\frac{\sigma\sqrt{\max\\{N_{o},T_{o}\\}}}{\psi_{\min,o}}\ll\frac{1}{\kappa_{o}\sqrt{\max\\{\log
N_{o},\log T_{o}\\}}}$ and $\min\\{N_{o},T_{o}\\}\geq\kappa_{o}\mu_{o}$. Then
(D.6), (D.7) also hold for $\mathcal{F}_{o}^{\tau,(m)}H_{o}^{\tau,(m)}.$
Additionally, we have

$\psi_{\min,o}/2\leq\psi_{\min}\left((Z_{o}^{\tau,(m)}H_{o}^{\tau,(m)})^{\top}Z_{o}^{\tau,(m)}H_{o}^{\tau,(m)}\right)\leq\psi_{\max}\left((Z_{o}^{\tau,(m)}H_{o}^{\tau,(m)})^{\top}Z_{o}^{\tau,(m)}H_{o}^{\tau,(m)}\right)\leq
2\psi_{\max,o}.$

######  Lemma D.23.

Suppose
$\mathcal{F}_{1},\mathcal{F}_{2},\mathcal{F}_{0}\in\mathbb{R}^{(N_{o}+T_{o})\times
r}$ are three matrices such that