$\text{Tr}\left(A_{1}B\right)\geq\text{Tr}\left(A_{2}B\right)$

Proof  Since both $A$ and $B$ are positive symmetric, there exists
$X,Y\in\mathbb{R}^{d\times d}$, such that $A=X^{T}X$ and $B=Y^{T}Y$,
therefore:

$\displaystyle\text{Tr}\left(AB\right)$
$\displaystyle=\text{Tr}\left(X^{T}XY^{T}Y\right)$
$\displaystyle=\text{Tr}\left((YX^{T})^{T}YX^{T}\right)$ $\displaystyle\geq 0$

The following lemma presents an upper bound of the Frobenius norm of the
product of two matrices.

###### Lemma 14

For two matrices $A\in\mathbb{R}^{m\times n}$, and $B\in\mathbb{R}^{n\times
k}$, we have:

$\left\lVert AB\right\rVert_{F}\leq\left\lVert A\right\rVert_{op}\left\lVert
B\right\rVert_{F}$

and:

$\left\lVert AB\right\rVert_{F}\leq\left\lVert A\right\rVert_{F}\left\lVert
B\right\rVert_{op}$

The proof of the lemma can be found in Sun and Luo (2015).

The following lemma introduces a simple upper bound on the Frobenius norm of
$\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}$.

###### Lemma 15

For any rank-r orthonormal matrix $\bm{U}\in\mathbb{R}^{d\times r}$, and
rank-r projection matrix $\bm{P}\in\mathbb{R}^{d\times d}$, we have:

$\left\lVert\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right\rVert_{F}\leq
r-Tr\left(\bm{U}^{T}\bm{P}\bm{U}\right)$ (40)

Proof  It is easy to see that $\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}$ is positive
semidefinite. And for a positive semidefinite matrix, its Frobenius norm is
upper bounded by its trace. Inequality (40) follows accordingly.
We can proceed to the following lemma that upper bounds the trace of the
$k$-th power of $\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}$.

###### Lemma 16

For any rank-r orthonormal matrix $\bm{U}\in\mathbb{R}^{d\times r}$, and
rank-r projection matrix $\bm{P}\in\mathbb{R}^{d\times r}$, $k=1,2,...$,
$\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{k}$ is positive semi-definite
and:

$0\leq
Tr\left(\left(\bm{I}-\bm{U}^{T}\bm{P}\bm{U}\right)^{k}\right)\leq\left(r-Tr\left(\bm{U}^{T}\bm{P}\bm{U}\right)\right)^{k}$
(41)

Proof  Since $\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}$ is symmetric positive
semidefinite, $\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{k}$ is also
symmetric positive semidefinite. Assume eigenvalues of
$\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}$ are
$\lambda_{1},\lambda_{2},\cdots,\lambda_{d}$, with
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{d}$, we know that
$Tr\left(\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{k}\right)=\sum_{i=1}^{d}\lambda_{i}^{k}\leq\lambda_{1}^{k-1}\sum_{i=1}^{d}\lambda_{i}$.

By Lemma 15, we know that

$\lambda_{1}^{k-1}\leq\left\lVert\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right\rVert_{F}^{k-1}\leq\left(r-Tr\left(\bm{U}^{T}\bm{P}\bm{U}\right)\right)^{k-1}$

This completes our proof.
Based on the above results, we can discuss some properties of the projection
of a matrix onto a subspace. Suppose we know the column space of
$\bm{U}\in\mathbb{R}^{d\times r}$ is close to that of
$\bm{P}\in\mathbb{R}^{d\times d}$, can we find a matrix $\bm{U}^{*}$ close to
$\bm{U}$ with column vectors in $col(\bm{P})$? The following two lemmas give
affirmative answers.

###### Lemma 17

For any rank-r orthonormal matrix $\bm{U}\in\mathbb{R}^{d\times r}$, and
rank-r projection matrix $\bm{P}\in\mathbb{R}^{d\times d}$, we define:

$\bm{U}^{\star}=\bm{P}\bm{U}\left(\bm{U}^{T}\bm{P}\bm{U}\right)^{-1/2}$

If $r-Tr\left(\bm{U}^{T}\bm{P}\bm{U}\right)\leq 1$, we have:

$\left\lVert\bm{U}-\bm{U}^{\star}\right\rVert_{F}^{2}\geq
r-Tr\left(\bm{U}^{T}\bm{P}\bm{U}\right)$ (42)

and:

$\left\lVert\bm{U}-\bm{U}^{\star}\right\rVert_{F}^{2}\leq
2\left(r-Tr\left(\bm{U}^{T}\bm{P}\bm{U}\right)\right)$ (43)

Proof  Since:

$\displaystyle\left\lVert\bm{U}-\bm{U}^{\star}\right\rVert_{F}^{2}=\left\langle\bm{U},\bm{U}\right\rangle+\left\langle\bm{U}^{\star},\bm{U}^{\star}\right\rangle-2\left\langle\bm{U},\bm{U}^{\star}\right\rangle$
$\displaystyle=2r-2\left\langle\bm{U},\bm{U}^{\star}\right\rangle$

We need to find an upper bound for
$\left\langle\bm{U},\bm{U}^{\star}\right\rangle$.

Notice that:

$\displaystyle\left\langle\bm{U},\bm{U}^{\star}\right\rangle$
$\displaystyle=\text{Tr}\left(\bm{U}^{T}\bm{U}^{\star}\right)$
$\displaystyle=\text{Tr}\left(\bm{U}^{T}\bm{P}\bm{U}\left(\bm{U}^{T}\bm{P}\bm{U}\right)^{-1/2}\right)$
$\displaystyle=\text{Tr}\left(\left(\bm{U}^{T}\bm{P}\bm{U}\right)^{1/2}\right)$
$\displaystyle=\text{Tr}\left(\left(\bm{I}_{r}-\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)\right)^{1/2}\right)$
$\displaystyle=\text{Tr}\left(\bm{I}_{r}-\frac{1}{2}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)-\sum_{n=2}^{\infty}\frac{(2n-3)!!}{2^{n}n!}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}\right)$
$\displaystyle=r-\frac{1}{2}\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)-\sum_{n=2}^{\infty}\frac{(2n-3)!!}{2^{n}n!}\text{Tr}\left(\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}\right)$
$\displaystyle\leq
r-\frac{1}{2}\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)$

We used the series
$(1-x)^{\frac{1}{2}}=1-\frac{1}{2}x-\sum_{n=2}^{\infty}\frac{(2n-3)!!}{2^{n}n!}x^{n}$,
and the result
$\text{Tr}\left(\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}\right)\geq
0$ from Lemma 16.

As a result:

$\left\lVert\bm{U}-\bm{U}^{\star}\right\rVert_{F}^{2}\geq\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)=r-\text{Tr}\left(\bm{U}^{T}\bm{P}\bm{U}\right)$

Similarly, from Lemma 16,
$\text{Tr}\left(\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}\right)\leq\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}$,
thus:

$\displaystyle\left\langle\bm{U},\bm{U}^{\star}\right\rangle$
$\displaystyle=r-\frac{1}{2}\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)-\sum_{n=2}^{\infty}\frac{(2n-3)!!}{2^{n}n!}\text{Tr}\left(\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}\right)$
$\displaystyle\geq
r-\frac{1}{2}\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)-\sum_{n=2}^{\infty}\frac{(2n-3)!!}{2^{n}n!}\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)^{n}$
$\displaystyle=r+\left(1-\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)\right)^{\frac{1}{2}}-1$
$\displaystyle\geq-\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)$

where we used the relation $\sqrt{1-x}-1\geq-x,\forall x\in[0,1]$, in the last
inequality.

Thus

$\left\lVert\bm{U}-\bm{U}^{\star}\right\rVert_{F}^{2}\leq
2\text{Tr}\left(\bm{I}_{r}-\bm{U}^{T}\bm{P}\bm{U}\right)=2\left(r-\text{Tr}\left(\bm{U}^{T}\bm{P}\bm{U}\right)\right)$

The following lemma corresponds to Lemma 2 in the main paper. It shows that we
can identify global PCs from local PCs.

###### Lemma 18

Suppose for $i=1,\cdots,N$, $\bm{P}_{\bm{U}}$, $\bm{P}_{\bm{V}_{(i)}}$ and
$\bm{P}_{\bm{U}}^{\star}$, $\bm{P}_{\bm{V}_{(i)}}^{\star}$ are projection
matrices satisfying $\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}=0$ and
$\bm{P}_{\bm{U}}^{\star}\bm{P}_{\bm{V}_{(i)}}^{\star}=0$ for each $i$. Among
them, $\bm{P}_{\bm{U}}$ and $\bm{P}_{\bm{U}}^{\star}$ have rank $r_{1}$,
$\bm{P}_{\bm{V}_{(i)}}$ and $\bm{P}_{\bm{V}_{(i)}}^{\star}$ have rank
$r_{2,(i)}$. If there exists a positive constant $\theta>0$ such that

$\lambda_{max}(\frac{1}{N}\sum_{i=1}^{N}\bm{P}_{\bm{V}_{(i)}}^{\star})\leq
1-\theta$

we have the following bound:

$\sum_{i=1}^{N}r_{1}+r_{2,(i)}-Tr\left(\left(\bm{P}_{\bm{U}}+\bm{P}_{\bm{V}_{(i)}}\right)\left(\bm{P}_{\bm{U}}^{\star}+\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)\leq
N\left(r_{1}-Tr(\bm{P}_{\bm{U}}^{\star}\bm{P}_{\bm{U}})\right)+\sum_{i=1}^{N}r_{2,(i)}-Tr(\bm{P}_{\bm{V}_{(i)}}^{\star}\bm{P}_{\bm{V}_{(i)}})$
(44)

And also:

$\displaystyle\sum_{i=1}^{N}r_{1}+r_{2,(i)}-Tr\left(\left(\bm{P}_{\bm{U}}+\bm{P}_{\bm{V}_{(i)}}\right)\left(\bm{P}_{\bm{U}}^{\star}+\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)$
(45)
$\displaystyle\geq\frac{\theta}{2}\left(N\left(r_{1}-Tr(\bm{P}_{\bm{U}}^{\star}\bm{P}_{\bm{U}})\right)+\sum_{i=1}^{N}r_{2,(i)}-Tr(\bm{P}_{\bm{V}_{(i)}}^{\star}\bm{P}_{\bm{V}_{(i)}})\right)$

Notice that we can replace $+$ by $\oplus$ on the left hand side of (44) and
(45)

Proof  We first calculate the upper bound.

Since $\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}^{\star}\bm{P}_{\bm{U}}$ is
positive semidefinite, we know that:

$\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}^{\star}\bm{P}_{\bm{U}}\right)\geq
0$

Thus

$\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}^{\star}\bm{P}_{\bm{U}}\right)=\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\geq
0$

Similarly, we have:

$\text{Tr}\left(\bm{P}_{\bm{U}}^{\star}\bm{P}_{\bm{V}_{(i)}}\right)\geq 0$

Combining them, we have:

$\displaystyle\text{Tr}\left(\left(\bm{P}_{\bm{U}}+\bm{P}_{\bm{V}_{(i)}}\right)\left(\bm{P}_{\bm{U}}^{\star}+\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)$
$\displaystyle=\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$
$\displaystyle\geq\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$

This proves inequality (44).

Next we calculate the lower bound.

$\displaystyle\sum_{i=1}^{N}\text{Tr}\left(\left(\bm{P}_{\bm{U}}+\bm{P}_{\bm{V}_{(i)}}\right)\left(\bm{P}_{\bm{U}}^{\star}+\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)$
$\displaystyle=\sum_{i=1}^{N}\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{V}_{(i)}}^{\star})\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$
$\displaystyle=\sum_{i=1}^{N}\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{U}}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{V}_{(i)}}^{\star}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$
$\displaystyle=\sum_{i=1}^{N}\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{U}}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{V}_{(i)}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$

Since
$\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{U}}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)$
and $\bm{P}_{\bm{V}_{(i)}}^{\star}$ are both symmetric positive semidefinite,
we have:

$\displaystyle\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{U}}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\frac{1}{N}\sum_{i=1}^{N}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$
$\displaystyle\leq\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{U}}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\right)\lambda_{max}\left(\frac{1}{N}\sum_{i=1}^{N}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$
$\displaystyle\leq\text{Tr}\left(\bm{P}_{\bm{U}}-\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)\left(1-\theta\right)$
$\displaystyle=\left(r_{1}-\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)\right)\left(1-\theta\right)$

For notation simplicity, we define
$z_{0}=r_{1}-\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)$ and
$z_{i}=r_{2,(i)}-\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$.

From the orthogonality, we have:

$\displaystyle\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)$
$\displaystyle=\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\bm{P}_{\bm{U}}^{\star}\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)$
$\displaystyle=\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\bm{P}_{\bm{V}_{(i)}}\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\bm{P}_{\bm{U}}^{\star}\right)$
$\displaystyle\leq\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\bm{P}_{\bm{V}_{(i)}}\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)\lambda_{max}\left(\bm{P}_{\bm{U}}^{\star}\right)$
$\displaystyle\leq\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\bm{P}_{\bm{V}_{(i)}}\left(\bm{I}-\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right)$
$\displaystyle=\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}-\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)$
$\displaystyle=z_{i}$

Also, from the orthogonality, we have:

$\displaystyle\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)$
$\displaystyle=\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}\right)\bm{P}_{\bm{V}_{(i)}}\left(\bm{I}-\bm{P}_{\bm{U}}\right)\bm{P}_{\bm{U}}^{\star}\right)$
$\displaystyle=\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\left(\bm{I}-\bm{P}_{\bm{U}}\right)\bm{P}_{\bm{U}}^{\star}\left(\bm{I}-\bm{P}_{\bm{U}}\right)\right)$
$\displaystyle\leq\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}\right)\bm{P}_{\bm{U}}^{\star}\left(\bm{I}-\bm{P}_{\bm{U}}\right)\right)\lambda_{max}\left(\bm{P}_{\bm{V}_{(i)}}\right)$
$\displaystyle\leq\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}\right)\bm{P}_{\bm{U}}^{\star}\left(\bm{I}-\bm{P}_{\bm{U}}\right)\right)$
$\displaystyle=\text{Tr}\left(\bm{P}_{\bm{U}}^{\star}-\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)$
$\displaystyle=z_{0}$

Combining the two:

$\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)\leq\min\\{z_{0},z_{i}\\}$

As a result:

$\displaystyle\sum_{i=1}^{N}r_{1}+r_{2,(i)}-\left[\text{Tr}\left(\bm{P}_{\bm{U}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{U}}\left(\bm{I}-\bm{P}_{\bm{U}}^{\star}\right)\bm{P}_{\bm{V}_{(i)}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{U}}^{\star}\right)+\text{Tr}\left(\bm{P}_{\bm{V}_{(i)}}\bm{P}_{\bm{V}_{(i)}}^{\star}\right)\right]$
$\displaystyle\geq\sum_{i=1}^{N}z_{0}-\left(1-\theta\right)z_{0}+z_{i}-\min\\{z_{0},z_{i}\\}$

Since for any number $\nu\in\left(0,1\right)$, we know:

$z_{i}-\min\\{z_{0},z_{i}\\}\geq\nu\left(z_{i}-z_{0}\right)$

We can set $\nu=\frac{\theta}{2}$, then

$\displaystyle\sum_{i=1}^{N}z_{0}-\left(1-\theta\right)z_{0}+z_{i}-\min\\{z_{0},z_{i}\\}$
$\displaystyle\geq\sum_{i=1}^{N}\theta
z_{0}+\frac{\theta}{2}\left(z_{i}-z_{0}\right)$
$\displaystyle=\frac{\theta}{2}\sum_{i=1}^{N}z_{0}+z_{i}$

This proves inequality (45).

##  Appendix C KKT condition and proof of Theorem 8

We first show KKT conditions (25). The lagrangian to the objective (7) is:

$\displaystyle\mathscr{L}=$
$\displaystyle\sum_{i=1}^{N}\left[\frac{1}{2}\text{Tr}\left(\bm{U}^{T}\bm{S}_{(i)}\bm{U}\right)+\frac{1}{2}\text{Tr}\left(\bm{V}_{(i)}^{T}\bm{S}_{(i)}\bm{V}_{(i)}\right)+\left\langle\bm{\Lambda}_{2,(i)},\bm{V}_{(i)}^{T}\bm{V}_{(i)}-\bm{I}\right\rangle+\left\langle\bm{\Lambda}_{3,(i)},\bm{U}^{T}\bm{V}_{(i)}\right\rangle\right]$
(46)
$\displaystyle+\left\langle\bm{\Lambda}_{1},\bm{U}^{T}\bm{U}\right\rangle$

where $\bm{\Lambda}_{1}\in\mathbb{R}^{r_{1}\times r_{1}}$,
$\bm{\Lambda}_{2,(i)}\in\mathbb{R}^{r_{2,(i)}\times r_{2,(i)}}$, and
$\bm{\Lambda}_{3,(i)}\in\mathbb{R}^{r_{1}\times r_{2,(i)}}$ are dual
variables. The KKT conditions are:

$\left\\{\begin{aligned}
&\bm{S}_{(i)}\bm{V}_{(i)}+\bm{V}_{(i)}\left(\bm{\Lambda}_{2,(i)}+\bm{\Lambda}_{2,(i)}^{T}\right)+\bm{U}\bm{\Lambda}_{3,(i)}=0\\\
&\sum_{i=1}^{N}\left[\bm{S}_{(i)}\bm{U}+\bm{V}_{(i)}\bm{\Lambda}_{3,(i)}^{T}\right]+\bm{U}\left(\bm{\Lambda}_{1}+\bm{\Lambda}_{1}^{T}\right)=0\\\
&\bm{U}^{T}\bm{U}=\bm{I}_{r_{1}},\
\bm{V}_{(i)}^{T}\bm{V}_{(i)}=\bm{I}_{r_{2,(i)}},\ \bm{U}^{T}\bm{V}_{i}=0\\\
\end{aligned}\right.$ (47)

By left multiplying the first equation in (47) with
$\bm{I}-\bm{P}_{\bm{U}}-\bm{P}_{\bm{V}_{(i)}}$, we have
$\left(\bm{I}-\bm{P}_{\bm{U}}-\bm{P}_{\bm{V}_{(i)}}\right)\bm{S}_{(i)}\bm{V}_{(i)}=0$,
which is the first equation in (25). By left multiplying the first equation in
(47) with $\bm{U}^{T}$, we have
$\bm{\Lambda}_{(3,(i))}=-\bm{U}^{T}\bm{S}_{(i)}\bm{V}_{(i)}$. Plugging this
into the second equation in (47), we have
$\sum_{i=1}^{N}\left[\bm{S}_{(i)}\bm{U}-\bm{P}_{\bm{V}_{(i)}}\bm{S}_{(i)}\bm{U}\right]+\bm{U}\left(\bm{\Lambda}_{1}+\bm{\Lambda}_{1}^{T}\right)=0$.
We then left multiply both sides again by $\bm{I}-\bm{P}_{\bm{U}}$. The second
equation in (25) follows accordingly. One can also infer (47) from (25).

Then we consider the global convergence. We begin by calculate the derivative
of $\mathcal{L}_{(i),1}$ and $\mathcal{L}_{(i),2}$. The derivative of
$\mathcal{L}_{(i),1}$ over $\bm{U}$ is:

$\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U},\bm{V})=-\left(\bm{I}-\bm{P}_{\bm{V}}\right)\bm{S}_{(i)}\left(\bm{I}-\bm{P}_{\bm{V}}\right)\bm{U}$
(48)

When $\bm{V}^{T}\bm{U}=0$, this reduces to:

$\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U},\bm{V})=-\left(\bm{I}-\bm{P}_{\bm{V}}\right)\bm{S}_{(i)}\bm{U}$

And the derivative of $\mathcal{L}_{(i),1}$ over $\bm{V}$ is:

$\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U},\bm{V})=\bm{P}_{\bm{U}}\bm{S}_{(i)}\bm{V}+\bm{S}_{(i)}\bm{P}_{\bm{U}}\bm{V}-\bm{P}_{\bm{U}}\bm{P}_{\bm{V}}\bm{S}_{(i)}\bm{V}-\bm{S}_{(i)}\bm{P}_{\bm{V}}\bm{P}_{\bm{U}}\bm{V}$
(49)

When $\bm{V}^{T}\bm{U}=0$, this reduces to:

$\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U},\bm{V})=\bm{P}_{\bm{U}}\bm{S}_{(i)}\bm{V}$

Similarly, the derivative of $\mathcal{L}_{(i),2}$ over $\bm{V}$ is:

$\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U},\bm{V})=-\bm{S}_{(i)}\bm{V}$ (50)

The following lemma shows the function we introduced is Lipschitz continuous.

###### Lemma 19

When $\left\lVert\bm{U}\right\rVert_{op}$ and
$\left\lVert\bm{V}\right\rVert_{op}$ are upper bounded by 1, the functions
$\mathcal{L}_{(i),1}+\mathcal{L}_{(i),2}$ are Lipschitz continuous with
constant $L$. More formally, for any
$\bm{U}_{1},\bm{U}_{2},\bm{V}_{1},\bm{V}_{2}\in\mathbb{R}^{d\times r}$, such
that
$\left\lVert\bm{U}_{1}\right\rVert_{op},\left\lVert\bm{U}_{2}\right\rVert_{op},\left\lVert\bm{V}_{1}\right\rVert_{op},\left\lVert\bm{V}_{2}\right\rVert_{op}\leq
1$, we have:

$\displaystyle\Big{\lVert}\Big{[}\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1}),$
(51)
$\displaystyle\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})+\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1})-\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{1},\bm{V}_{1})\Big{]}\Big{\rVert}_{F}$
$\displaystyle\leq
L\sqrt{\left\lVert\bm{U}_{1}-\bm{U}_{2}\right\rVert_{F}^{2}+\left\lVert\bm{V}_{1}-\bm{V}_{2}\right\rVert_{F}^{2}}$

where

$L=9\sqrt{2}G_{(i),op}$ (52)

Proof  First we calculate the difference in the gradient of $\bm{U}$:

$\displaystyle\left\lVert\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1})\right\rVert_{F}$
$\displaystyle=\left\lVert\left(\bm{I}-\bm{V}_{1}\bm{V}_{1}^{T}\right)\bm{S}_{(i)}\bm{U}_{1}-\left(\bm{I}-\bm{V}_{2}\bm{V}_{2}^{T}\right)\bm{S}_{(i)}\bm{U}_{2}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left(\bm{I}-\bm{V}_{1}\bm{V}_{1}^{T}\right)\bm{S}_{(i)}\bm{U}_{1}-\left(\bm{I}-\bm{V}_{2}\bm{V}_{2}^{T}\right)\bm{S}_{(i)}\bm{U}_{1}\right\rVert_{F}+\left\lVert\left(\bm{I}-\bm{V}_{2}\bm{V}_{2}^{T}\right)\bm{S}_{(i)}\bm{U}_{1}-\left(\bm{I}-\bm{V}_{2}\bm{V}_{2}^{T}\right)\bm{S}_{(i)}\bm{U}_{2}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\bm{V}_{1}\bm{V}_{1}^{T}-\bm{V}_{2}\bm{V}_{2}^{T}\right\rVert_{F}G_{(i),op}+\left\lVert\bm{U}_{1}-\bm{U}_{2}\right\rVert_{F}G_{(i),op}$
$\displaystyle\leq
2\left\lVert\bm{V}_{1}-\bm{V}_{2}\right\rVert_{F}G_{(i),op}+\left\lVert\bm{U}_{1}-\bm{U}_{2}\right\rVert_{F}G_{(i),op}$

where we used the triangle inequality for the Frobenius norm for the first
inequality, and Lemma 14 for the second and third inequality. Next we
calculate the difference in the gradient of $\bm{V}$:

$\displaystyle\left\lVert\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})+\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1})-\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{1},\bm{V}_{1})\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left(\bm{P}_{\bm{U}_{2}}-\bm{I}\right)\bm{S}_{(i)}\bm{V}_{2}-\left(\bm{P}_{\bm{U}_{1}}-\bm{I}\right)\bm{S}_{(i)}\bm{V}_{1}\right\rVert_{F}+\left\lVert\bm{S}_{(i)}\bm{P}_{\bm{U}_{2}}\bm{V}_{2}-\bm{S}_{(i)}\bm{P}_{\bm{U}_{2}}\bm{V}_{2}\right\rVert$
$\displaystyle+\left\lVert\bm{P}_{\bm{U}_{2}}\bm{P}_{\bm{V}_{2}}\bm{S}_{(i)}\bm{V_{2}}-\bm{P}_{\bm{U}_{1}}\bm{P}_{\bm{V}_{1}}\bm{S}_{(i)}\bm{V}_{1}\right\rVert_{F}+\left\lVert\bm{S}_{(i)}\bm{P}_{\bm{V}_{2}}\bm{P}_{\bm{U}_{2}}\bm{V}_{2}-\bm{S}_{(i)}\bm{P}_{\bm{V}_{1}}\bm{P}_{\bm{U}_{1}}\bm{V}_{1}\right\rVert_{F}$
$\displaystyle\leq
7\left\lVert\bm{V}_{1}-\bm{V}_{2}\right\rVert_{F}G_{(i),op}+6\left\lVert\bm{U}_{1}-\bm{U}_{2}\right\rVert_{F}G_{(i),op}$

Summing them up, we know:

$\displaystyle\Big{\lVert}\Big{[}\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1}),$
(53)
$\displaystyle\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})+\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1})-\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{1},\bm{V}_{1})\Big{]}\Big{\rVert}_{F}$
$\displaystyle\leq\left\lVert\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1})\right\rVert_{F}$
$\displaystyle+\left\lVert\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{2},\bm{V}_{2})+\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{2},\bm{V}_{2})-\nabla_{\bm{V}}\mathcal{L}_{(i),1}(\bm{U}_{1},\bm{V}_{1})-\nabla_{\bm{V}}\mathcal{L}_{(i),2}(\bm{U}_{1},\bm{V}_{1})\right\rVert_{F}$
$\displaystyle\leq
9\left\lVert\bm{V}_{1}-\bm{V}_{2}\right\rVert_{F}G_{(i),op}+7\left\lVert\bm{U}_{1}-\bm{U}_{2}\right\rVert_{F}G_{(i),op}$
$\displaystyle\leq
9\sqrt{2}G_{max,op}\sqrt{\left\lVert\bm{U}_{1}-\bm{U}_{2}\right\rVert_{F}^{2}+\left\lVert\bm{V}_{1}-\bm{V}_{2}\right\rVert_{F}^{2}}$

We thus complete the proof.

Now we introduce some notations:

$\square\bm{U}_{\tau}=\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}$
(54)

It is easy to verify $\square\bm{U}_{\tau}\in\mathcal{T}_{\bm{U}_{\tau}}$ when
$\bm{U}^{T}\bm{V}_{(i),\tau}=0$:

$\bm{U}_{\tau}^{T}\square\bm{U}_{\tau}=0$

.

The Frobenius norm of $\square\bm{U}_{\tau}$ is upper bounded by:

$\displaystyle\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}$ (55)
$\displaystyle=\left\lVert\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\right\rVert_{op}\left\lVert\bm{S}_{(i)}\right\rVert_{op}\left\lVert\bm{U}_{\tau}\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}G_{max,op}\sqrt{r}$
$\displaystyle=G_{max,op}\sqrt{r}$

where we applied Lemma 14 for the first inequality.

By the client update rule, we know that:

$\bm{U}_{(i),\tau+1}=\bm{U}_{\tau}+\eta_{\tau}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}$
(56)

Therefore, after the server takes the average of $\bm{U}_{(i),\tau+1}$ and
performs generalized retraction, the following holds:

$\bm{U}_{\tau+1}=\bm{U}_{\tau}+\eta_{\tau}\square\bm{U}_{\tau}+\eta_{\tau}^{2}\bm{e}_{1,\tau}$
(57)

where $\bm{e}_{1,\tau}$ is an error term defined as:

$\bm{e}_{1,\tau}=\frac{1}{\eta_{\tau}^{2}}\left(\bm{U}_{\tau+1}-\bm{U}_{\tau}-\eta_{\tau}\square\bm{U}_{\tau}\right)$

By definition of generalized retraction, since $\square\bm{U}_{\tau}$ is in
the tangent space of $\bm{U}_{\tau}$, we have:

$\displaystyle\left\lVert\bm{e}_{1,\tau}\right\rVert_{F}\leq
M_{1}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}$

where we applied the condition
$\eta_{\tau}\leq\frac{M_{3}}{\sqrt{r}G_{max,op}}$ thus
$\left\lVert\eta_{\tau}\square\bm{U}_{\tau}\right\rVert_{F}\leq M_{3}$.

Similarly we define:

$\square\bm{V}_{(i),\tau}=\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau}$
(58)

Also by Lemma 14, the Frobenius norm of $\square\bm{V}_{(i),\tau}$ is upper
bounded by:

$\displaystyle\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}$ (59)
$\displaystyle=\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\right\rVert_{op}\left\lVert\bm{S}_{(i)}\right\rVert_{op}\left\lVert\bm{V}_{(i),\tau}\right\rVert_{F}$
$\displaystyle\leq G_{(i),op}\sqrt{r}$

Now we calculate the update of $\bm{V}_{(i),\tau}$ in one communication round.
We summarize the result in the following lemma.

###### Lemma 20

If we choose the stepsize
$\eta_{\tau}\leq\min\left\\{\frac{M_{3}}{2},\frac{\sqrt{M_{3}}}{\sqrt{6+12M_{1}+M_{1}^{2}}}\right\\}\frac{1}{G_{max,op}\sqrt{r}}$,
the update of $\bm{V}_{n}$ is given by:

$\bm{V}_{(i),\tau+1}=\bm{V}_{(i),\tau}+\eta_{\tau}\square\bm{V}_{(i),\tau}-\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{5,(i),\tau}$

where $\bm{e}_{5,(i),\tau}$ is an error term that satisfies:

$\left\lVert\bm{e}_{5,(i),\tau}\right\rVert\leq
C_{5,0}\left\lVert\square\bm{U}_{\tau}\right\rVert^{2}+C_{5,1}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert^{2}$

where $C_{5,0}$ and $C_{5,1}$ are two constants that only depend on $M_{1}$
and $M_{2}$ from the generalized retraction definition 5.

Proof  We firstly calculate the projection:

$\displaystyle\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}$
$\displaystyle=\left(\bm{U}_{\tau}+\eta_{\tau}\square\bm{U}_{\tau}+\eta_{\tau}^{2}\bm{e}_{1,\tau}\right)\left(\bm{U}_{\tau}+\eta_{\tau}\square\bm{U}_{\tau}+\eta_{\tau}^{2}\bm{e}_{1,\tau}\right)^{T}$
$\displaystyle=\bm{U}_{\tau}\bm{U}_{\tau}^{T}+\eta_{\tau}\left(\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}+\square\bm{U}_{\tau}\bm{U}_{\tau}^{T}\right)+\eta_{\tau}^{2}\bm{e}_{2,(i),\tau}$

where $\bm{e}_{2,(i),\tau}$ is defined as:

$\bm{e}_{2,(i),\tau}=\square\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}+\bm{U}_{\tau}\bm{e}_{1,(i),\tau}^{T}+\bm{e}_{1,(i),\tau}\bm{U}_{\tau}^{T}+\eta_{\tau}\square\bm{U}_{\tau}\bm{e}_{1,(i),\tau}^{T}+\eta\bm{e}_{1,(i),\tau}\square\bm{U}_{\tau}^{T}+\eta^{2}\bm{e}_{1,(i),\tau}\bm{e}_{1,(i),\tau}^{T}$

Its norm is upper bounded by:

$\displaystyle\left\lVert\bm{e}_{2,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\square\bm{U}_{\tau}\right\rVert^{2}_{F}+2\left\lVert\bm{U}_{\tau}\right\rVert_{op}\left\lVert\bm{e}_{1,(i),\tau}\right\rVert_{F}+2\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}\left\lVert\bm{e}_{1,(i),\tau}\right\rVert_{F}+\eta_{\tau}^{2}\left\lVert\bm{e}_{1,(i),\tau}\right\rVert_{F}^{2}$
$\displaystyle\leq\left\lVert\square\bm{U}_{\tau}\right\rVert^{2}_{F}+2M_{1}\left\lVert\square\bm{U}_{\tau}\right\rVert^{2}_{F}+2\eta_{\tau}M_{1}\left\lVert\square\bm{U}_{\tau}\right\rVert^{3}_{F}+\eta_{\tau}^{2}M_{1}^{2}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{4}$
$\displaystyle\leq(1+3M_{1}+\frac{1}{4}M_{1}^{2})\left\lVert\square\bm{U}_{\tau}\right\rVert^{2}_{F}$

where the final inequality comes from upper bound (55) and the choice of
stepsize $\eta_{\tau}$:
$\eta_{\tau}\leq\frac{1}{G_{max,op}\sqrt{r}}\frac{1}{\sqrt{6+12M_{1}+M_{1}^{2}}}\leq\frac{1}{2G_{max,op}\sqrt{r}}$.

Similarly, we define $\bm{e}_{3,(i),\tau}$ as:

$\eta_{\tau}^{2}\bm{e}_{3,(i),\tau}=\frac{1}{\eta_{\tau}^{2}}\left(\bm{V}_{(i),\tau+\frac{1}{2}}-\bm{V}_{(i),\tau}-\eta_{\tau}\square\bm{V}_{(i),\tau}\right)$

By definition of a retraction, the norm of $\bm{e}_{3,(i),\tau}$ is upper
bounded by:

$\left\lVert\bm{e}_{3,(i),\tau}\right\rVert_{F}\leq
M_{1}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$

Then

$\displaystyle\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}$
$\displaystyle=\bm{U}_{\tau}\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}+\eta_{\tau}\left(\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}+\square\bm{U}_{\tau}\bm{U}_{\tau}^{T}\right)\bm{V}_{(i),\tau+\frac{1}{2}}+\eta_{\tau}^{2}\bm{e}_{2,(i),\tau}\bm{V}_{(i),\tau+\frac{1}{2}}$
$\displaystyle=\bm{U}_{\tau}\bm{U}_{\tau}^{T}\left(\bm{V}_{(i),\tau}+\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{3,(i),\tau}\right)$
$\displaystyle+\eta_{\tau}\left(\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}+\square\bm{U}_{\tau}\bm{U}_{\tau}^{T}\right)\left(\bm{V}_{(i),\tau}+\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{3,(i),\tau}\right)+\eta_{\tau}^{2}\bm{e}_{2,(i),\tau}\bm{V}_{(i),\tau+\frac{1}{2}}$
$\displaystyle=\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{U}_{\tau}\bm{U}_{\tau}^{T}\bm{e}_{3,(i),\tau}+\eta_{\tau}^{2}\bm{e}_{2,(i),\tau}\bm{V}_{(i),\tau+\frac{1}{2}}+\eta_{\tau}^{2}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\square\bm{V}_{(i),\tau}$
$\displaystyle+\eta_{\tau}^{3}\left(\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}+\square\bm{U}_{\tau}\bm{U}_{\tau}^{T}\right)\bm{e}_{3,(i),\tau}$
$\displaystyle=\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{4,(i),\tau}$

where we use $\bm{e}_{4,(i),\tau}$ to denote:

$\bm{e}_{4,(i),\tau}=\bm{U}_{\tau}\bm{U}_{\tau}^{T}\bm{e}_{3,(i),\tau}+\bm{e}_{2,(i),\tau}\bm{V}_{(i),\tau+\frac{1}{2}}+\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\square\bm{V}_{(i),\tau}+\eta_{\tau}\left(\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}+\square\bm{U}_{\tau}\bm{U}_{\tau}^{T}\right)\bm{e}_{3,(i),\tau}$

Its norm is upper bounded as:

$\displaystyle\left\lVert\bm{e}_{4,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\bm{e}_{3,(i),\tau}\right\rVert_{F}+\left\lVert\bm{e}_{2,(i),\tau}\right\rVert_{F}+\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}+\eta_{\tau}\left(\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}+\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}\right)\left\lVert\bm{e}_{3,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq
C_{4,0}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+C_{4,1}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$

where

$C_{4,0}=\frac{3}{2}+3M_{1}+\frac{1}{4}M_{1}^{2}$

and

$C_{4,1}=\frac{1}{2}+2M_{1}$

Thus we know when
$\eta_{\tau}\leq\min\\{\frac{M_{3}}{2},\sqrt{\frac{M_{3}}{4C_{4,0}}}\\}\frac{1}{G_{max,op}\sqrt{r}}$,
$\left\lVert\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right\rVert_{F}\leq
M_{3}$

Next we calculate the projection
$\mathcal{P}_{\mathcal{N}_{\bm{V}_{(i),\tau+\frac{1}{2}}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)$:

$\displaystyle\mathcal{P}_{\mathcal{N}_{\bm{V}_{(i),\tau+\frac{1}{2}}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)=-\bm{V}_{(i),\tau+\frac{1}{2}}\left(\bm{V}_{(i),\tau+\frac{1}{2}}^{T}\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)$
$\displaystyle=\eta_{\tau}^{2}\bm{V}_{(i),\tau+\frac{1}{2}}\bm{V}_{(i),\tau+\frac{1}{2}}^{T}\bm{e}_{4,(i),\tau}$

We use $\bm{e}_{5,(i),\tau}$ to denote the difference between
$\mathcal{GR}_{\bm{V}_{(i),\tau+\frac{1}{2}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)$
and
$\bm{V}_{(i),\tau}+\eta_{\tau}\square\bm{V}_{(i),\tau}-\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}$,
then its norm is upper bounded by:

$\displaystyle\eta_{\tau}^{2}\left\lVert\bm{e}_{5,(i),\tau}\right\rVert_{F}$
$\displaystyle=\left\lVert\mathcal{GR}_{\bm{V}_{(i),\tau+\frac{1}{2}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)-\bm{V}_{(i),\tau}-\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\mathcal{GR}_{\bm{V}_{(i),\tau+\frac{1}{2}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)-\bm{V}_{(i),\tau+\frac{1}{2}}+\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right\rVert_{F}$
$\displaystyle+\left\lVert\bm{V}_{(i),\tau+\frac{1}{2}}-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}-\bm{V}_{(i),\tau}-\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}\right\rVert_{F}$

By property 2 of the generalized retraction in Definition 5, we have:

$\displaystyle\left\lVert\mathcal{GR}_{\bm{V}_{(i),\tau+\frac{1}{2}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)-\left(\bm{V}_{(i),\tau+\frac{1}{2}}-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)\right\rVert_{F}$
$\displaystyle\leq
M_{1}\left\lVert\mathcal{P}_{\mathcal{T}_{\bm{V}_{(i),\tau+\frac{1}{2}}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)\right\rVert_{F}^{2}+(M_{2}+1)\left\lVert\mathcal{P}_{\mathcal{N}_{\bm{V}_{(i),\tau+\frac{1}{2}}}}\left(-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right)\right\rVert_{F}$
$\displaystyle\leq
M_{1}\left\lVert-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}\right\rVert_{F}^{2}+(M_{2}+1)\eta_{\tau}^{2}\left\lVert\bm{V}_{(i),\tau+\frac{1}{2}}\bm{V}_{(i),\tau+\frac{1}{2}}^{T}\bm{e}_{4,(i),\tau}\right\rVert_{F}$
$\displaystyle=M_{1}\left\lVert\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{4,(i),\tau}\right\rVert_{F}^{2}+(M_{2}+1)\eta_{\tau}^{2}\left\lVert\bm{V}_{(i),\tau+\frac{1}{2}}\bm{V}_{(i),\tau+\frac{1}{2}}^{T}\bm{e}_{4,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq
2M_{1}\eta_{\tau}^{2}\left(\left\lVert\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{4}\left\lVert\bm{e}_{4,(i),\tau}\right\rVert_{F}^{2}\right)+(M_{2}+1)\eta_{\tau}^{2}\left\lVert\bm{V}_{(i),\tau+\frac{1}{2}}\bm{V}_{(i),\tau+\frac{1}{2}}^{T}\bm{e}_{4,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}^{2}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}\left(2M_{1}(C_{4,0}+C_{4,1})C_{4,0}+2M_{1}+M_{2}C_{4,0}\right)$
$\displaystyle+\eta_{\tau}^{2}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\left(2M_{1}(C_{4,0}+C_{4,1})C_{4,1}+M_{2}C_{4,1}\right)$

For the second part:

$\displaystyle\left\lVert\bm{V}_{(i),\tau+\frac{1}{2}}-\bm{U}_{\tau+1}\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+\frac{1}{2}}-\bm{V}_{(i),\tau}-\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}\right\rVert_{F}$
$\displaystyle=\eta_{\tau}^{2}\left\lVert
e_{3,(n),\tau}-e_{4,(n),\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}^{2}\left\lVert
e_{3,(n),\tau}\right\rVert_{F}+\eta_{\tau}^{2}\left\lVert
e_{4,(n),\tau}\right\rVert_{F}$

Therefore, the norm of $\bm{e}_{5,(i),\tau}$ is upper bounded as:

$\displaystyle\left\lVert\bm{e}_{5,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}\left(2M_{1}(C_{4,0}+C_{4,1})C_{4,0}+2M_{1}+M_{2}C_{4,0}+C_{4,0}\right)$
$\displaystyle+\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\left(2M_{1}(C_{4,0}+C_{4,1})C_{4,1}+M_{2}C_{4,1}+M_{1}+C_{4,1}\right)$

This completes our proof, with

$C_{5,0}=\frac{1}{8}\left(12\left(M_{2}+1\right)+M_{1}\left(24M_{2}+M_{1}\left(M_{1}\left(M_{1}\left(M_{1}+32\right)+254\right)+2\left(M_{2}+109\right)\right)+88\right)\right)$

and

$C_{5,1}=M_{1}^{4}+\frac{81M_{1}^{3}}{4}+13M_{1}^{2}+\left(2M_{2}+5\right)M_{1}+\frac{1}{2}\left(M_{2}+1\right)$

The following lemma shows the sufficient decrease property:

###### Lemma 21

(Formal version of Lemma 9) When we choose the stepsize
$\eta_{\tau}\leq\frac{1}{G_{max,op}\sqrt{r}}\min\left\\{\frac{M_{3}}{2},\frac{\sqrt{M_{3}}}{\sqrt{6+12M_{1}+M_{1}^{2}}}\right\\}$,
and $\bm{U}_{\tau}$ and $\bm{V}_{(i),\tau}$ satisfy the orthogonality
condition $\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}=0$, we have:

$\displaystyle\left\langle\sum_{i=1}^{N}\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{\tau},\bm{V}_{(i),\tau}),\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rangle$
(60)
$\displaystyle+\sum_{i=1}^{N}\left\langle\nabla_{\bm{V}_{(i)}}\mathcal{L}_{(i),1}(\bm{U}_{\tau},\bm{V}_{(i),\tau})+\nabla_{\bm{V}_{(i)}}\mathcal{L}_{(i),2}(\bm{U}_{\tau},\bm{V}_{(i),\tau}),\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rangle$
$\displaystyle\leq-\eta_{\tau}N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}-\eta_{\tau}\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{2}\left(C_{6,0}N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+C_{6,1}\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$

where $C_{6,0}$ and $C_{6,1}$ are constants dependent only on $M_{1}$,
$M_{2}$, $r$, and $G_{max,op}$:

$C_{6,0}=G_{max,op}\sqrt{r}(M_{1}+C_{5,0})$

and

$C_{6,1}=G_{max,op}\sqrt{r}C_{5,1}$

Proof  We firstly calculate the sufficient decrease of $\bm{U}$:

$\displaystyle\left\langle\sum_{i=1}^{N}\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{\tau},\bm{V}_{(i),\tau}),\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rangle$
$\displaystyle=\left\langle-\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau},\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rangle$
$\displaystyle=-\left\langle\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau},\frac{\eta_{\tau}}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}+\eta_{\tau}^{2}\bm{e}_{1,\tau}\right\rangle$
$\displaystyle=-\left\langle\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau},\frac{\eta_{\tau}}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}\right\rangle$
$\displaystyle-\left\langle\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau},\eta_{\tau}^{2}\bm{e}_{1,\tau}\right\rangle$
$\displaystyle=-\left\langle\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau},\frac{\eta_{\tau}}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}\right\rangle$
$\displaystyle-\left\langle\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau},\eta_{\tau}^{2}\bm{e}_{1,\tau}\right\rangle$
$\displaystyle\leq-\eta_{\tau}N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{2}\left\lVert\bm{e}_{1,\tau}\right\rVert_{F}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}\right\rVert_{F}$
$\displaystyle\leq-\eta_{\tau}N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+M_{1}\eta_{\tau}^{2}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}\sum_{i=1}^{N}G_{(i),op}\sqrt{r}$

Next, we calculate:

$\displaystyle\left\langle\nabla_{\bm{V}_{(i)}}\mathcal{L}_{(i),1}(\bm{U}_{\tau},\bm{V}_{(i),\tau})+\nabla_{\bm{V}_{(i)}}\mathcal{L}_{(i),2}(\bm{U}_{\tau},\bm{V}_{(i),\tau}),\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rangle$
$\displaystyle=\left\langle-\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau},\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{5,(i),\tau}\right\rangle$
$\displaystyle=\left\langle-\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau},\eta_{\tau}\square\bm{V}_{(i),\tau}\right\rangle+\left\langle-\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau},\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}\right\rangle$
$\displaystyle+\left\langle-\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau},\eta_{\tau}^{2}\bm{e}_{5,(i),\tau}\right\rangle$
$\displaystyle=\left\langle-\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau},\eta_{\tau}\square\bm{V}_{(i),\tau}\right\rangle+\left\langle-\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau},\eta_{\tau}^{2}\bm{e}_{5,(i),\tau}\right\rangle$
$\displaystyle\leq-\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{2}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau}\right\rVert_{F}\left\lVert\bm{e}_{5,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq-\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{2}G_{(i),op}\sqrt{r}\left(C_{5,0}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+C_{5,1}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert^{2}\right)$

Adding them, we have:

$\displaystyle\left\langle\sum_{i=1}^{N}\nabla_{\bm{U}}\mathcal{L}_{(i),1}(\bm{U}_{\tau},\bm{V}_{(i),\tau}),\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rangle$
$\displaystyle+\left\langle\nabla_{\bm{V}_{(i)}}\mathcal{L}_{(i),1}(\bm{U}_{\tau},\bm{V}_{(i),\tau})+\nabla_{\bm{V}_{(i)}}\mathcal{L}_{(i),2}(\bm{U}_{\tau},\bm{V}_{(i),\tau}),\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rangle$
$\displaystyle\leq-\eta_{\tau}N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}-\sum_{i=1}^{N}\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{2}\left(NC_{6,0}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+C_{6,1}\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$

where the constants are:

$C_{6,0}=G_{max,op}\sqrt{r}(M_{1}+C_{5,0})$

and

$C_{6,1}=G_{max,op}\sqrt{r}C_{5,1}$

Finally we come to the proof of Theorem 8.

Proof  We choose constant stepsize $\eta_{\tau}=\eta_{1}$ small enough:

$\displaystyle\eta_{1}\leq\eta_{c}=$
$\displaystyle\min\Big{\\{}\frac{1}{2C_{6,0}+L\left(\left(\left(1+\frac{M_{2}}{2}\right)^{2}+2\left(1+\frac{C_{5,0}}{2}\right)^{2}\right)\right)},\frac{1}{2C_{6,1}+2L\left(1+\frac{C_{5,1}}{2}\right)^{2}},$
(61)
$\displaystyle\frac{1}{G_{max,op}\sqrt{r}}\frac{M_{3}}{2},\frac{1}{G_{max,op}\sqrt{r}}\frac{\sqrt{M_{3}}}{\sqrt{6+12M_{1}+M_{1}^{2}}}\Big{\\}}$

Obviously, $\eta_{\tau}$ satisfies the requirement in Lemma 20 and 21.

By the property of Lipschitz continuity, we have:

$\displaystyle\mathcal{L}_{(i)}\left(\bm{U}_{\tau+1},\bm{V}_{(i),\tau+1}\right)\leq\mathcal{L}_{(i)}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right)$
$\displaystyle+\left\langle\nabla_{\bm{U}}\mathcal{L}_{(i)}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right),\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rangle+\left\langle\nabla_{\bm{U}}\mathcal{L}_{(i)}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right),\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rangle$
$\displaystyle+\frac{L}{2}\left(\left\lVert\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\left\lVert\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rVert_{F}^{2}\right)$

where $L$ is defined in (52). Since $\bm{U}_{\tau+1}^{T}\bm{V}_{(i),\tau+1}=0$
and $\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}=0$, we know that

$\mathcal{L}_{(i)}\left(\bm{U}_{\tau+1},\bm{V}_{(i),\tau+1}\right)=-f_{i}\left(\bm{U}_{\tau+1},\bm{V}_{(i),\tau+1}\right)$

and that

$\mathcal{L}_{(i)}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right)=-f_{i}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right)$

Then, summing up both sides for $n$ from 1 to $N$, we have:

$\displaystyle-f\left(\bm{U}_{\tau+1},\\{\bm{V}_{(i),\tau+1}\\}\right)\leq-f\left(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\}\right)$
$\displaystyle+\left\langle\sum_{i=1}^{N}\nabla_{\bm{U}}\mathcal{L}_{(i)}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right),\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rangle+\sum_{i=1}^{N}\left\langle\nabla_{\bm{U}}\mathcal{L}_{(i)}\left(\bm{U}_{\tau},\bm{V}_{(i),\tau}\right),\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rangle$
$\displaystyle+\sum_{i=1}^{N}\frac{L}{2}\left(\left\lVert\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rVert_{F}^{2}+\left\lVert\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rVert_{F}^{2}\right)$

From equation (57), we know

$\displaystyle\left\lVert\bm{U}_{\tau+1}-\bm{U}_{\tau}\right\rVert_{F}$
$\displaystyle=\left\lVert\eta_{\tau}\square\bm{U}_{\tau}+\eta_{\tau}^{2}\bm{e}_{1,\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}+\left\lVert\eta_{\tau}^{2}\bm{e}_{1,\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}+\eta_{\tau}^{2}M_{1}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}$
$\displaystyle\leq\eta_{\tau}(1+\frac{M_{1}}{2})\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}$

Similarly, from Lemma 20, we have:

$\displaystyle\left\lVert\bm{V}_{(i),\tau+1}-\bm{V}_{(i),\tau}\right\rVert_{F}$
$\displaystyle=\left\lVert\eta_{\tau}\square\bm{V}_{(i),\tau}+\eta_{\tau}\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}+\eta_{\tau}^{2}\bm{e}_{5,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}+\eta_{\tau}\left\lVert\bm{U}_{\tau}\square\bm{U}_{\tau}^{T}\bm{V}_{(i),\tau}\right\rVert_{F}+\eta_{\tau}^{2}\left\lVert\bm{e}_{5,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}+\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}+\eta_{\tau}^{2}\left\lVert\bm{e}_{5,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}\left(1+C_{5,0}\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}\right)+\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}\left(1+C_{5,1}\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}\right)$
$\displaystyle\leq\eta_{\tau}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}\left(1+\frac{1}{2}C_{5,1}\right)+\eta_{\tau}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}\left(1+\frac{1}{2}C_{5,0}\right)$

Combining the two inequalities and Lemma 21, we have:

$\displaystyle-f\left(\bm{U}_{\tau+1},\\{\bm{V}_{(i),\tau+1}\\}\right)$ (62)
$\displaystyle\leq-f\left(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\}\right)-\eta_{\tau}\left(N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$
$\displaystyle+\eta_{\tau}^{2}NC_{6,0}\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\eta_{\tau}^{2}\sum_{i=1}^{N}C_{6,1}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$
$\displaystyle+\eta_{\tau}^{2}\frac{L}{2}\sum_{i=1}^{N}\left(\left(\left(1+\frac{M_{2}}{2}\right)^{2}+2\left(1+\frac{C_{5,0}}{2}\right)^{2}\right)\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+2\left(1+\frac{C_{5,1}}{2}\right)^{2}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$
$\displaystyle\leq-f\left(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\}\right)-\frac{\eta_{\tau}}{2}\left(N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$

Summing up both sides for $\tau$ from $1$ to $R$ and rearranging terms, we
have:

$\frac{\eta_{1}}{2}\sum_{\tau=1}^{R}\left(N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)\leq
f^{\star}-f(\bm{U}_{1},\\{\bm{v}_{(i),1}\\})$

As a result,

$\min_{\tau\in\\{1,\cdots,N\\}}\sum_{\tau=1}^{R}\left(N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)\leq\frac{2\left(f^{\star}-f(\bm{U}_{1},\\{\bm{v}_{(i),1}\\})\right)}{R\eta_{1}}$

This completes the proof of Theorem 8. Notice that $C_{6,0}$, $C_{6,1}$, and
$L$ are of the order $G_{max,op}\sqrt{r}$, thus the requirement on $\eta_{c}$
in equation (61) becomes:

$\eta_{c}=C_{\eta}\frac{1}{G_{max,op}\sqrt{r}}$

where $C_{\eta}$ is a constant that only depends on $M_{1}$, $M_{2}$, and
$M_{3}$ from the generalized retraction definition 5.

##  Appendix D Proof for local exponential convergence

For simplicity, we introduce a few additional notations.

At communication round $\tau$, suppose the global and local PCs are
$\\{\bm{u}_{\tau,k}\\}_{k=1,...r}$ and
$\\{\bm{v}_{(i),\tau,k}\\}_{i=1,...N,k=1,...r}$, and they satisfy the
requirement in Theorem 10. Then we can introduce $\bm{U}^{\star}_{\tau}$ and
$\bm{V}_{(i),\tau}^{\star}$’s defined by

$\bm{U}^{\star}_{\tau}=\bm{\Pi}_{g}\bm{U}_{\tau}\left((\bm{U}_{\tau})^{T}\bm{\Pi}_{g}\bm{U}_{\tau}\right)^{-1/2}$
(63)

and

$\bm{V}_{(i),\tau}^{\star}=\bm{\Pi}_{(i)}\bm{V}_{(i),\tau}\left(\bm{V}_{(i),\tau}^{T}\bm{\Pi}_{(i)}\bm{V}_{(i),\tau}\right)^{-1/2}$
(64)

for each $n=1,...N$.

It’s easy to verify that

$\bm{U}^{\star}_{\tau}(\bm{U}^{\star}_{\tau})^{T}=\bm{\Pi}_{g}$

and that

$\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}=\bm{\Pi}_{(i)}$

Notice that $\bm{U}^{\star}_{\tau}$ and $\bm{V}_{(i),\tau}^{\star}$’s are one
global optimal solution, but not the unique global optimal solution. The
$\bm{U}^{\star}_{\tau}$ and $\bm{V}_{(i),\tau}^{\star}$’s are dependent on
communication $\tau$. We use $\Delta\bm{U}_{\tau}$ to denote the difference
between $\bm{U}_{\tau}$ and $\bm{U}_{\tau}^{\star}$:

$\Delta\bm{U}_{\tau}=\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}$ (65)

and similarly:

$\Delta\bm{V}_{(i),\tau}=\bm{V}_{(i),\tau}-\bm{V}_{(i),\tau}^{\star}$ (66)

The following lemma presents a lower bound on the norm of the updates:

###### Lemma 22

(Formal version of Lemma 11) (Personalized gradient dominance property)
Suppose $\bm{U}_{\tau}^{\star}$ and $\bm{V}_{(i),\tau}^{\star}$’s are defined
by equation (63) and (64), where $\bm{U}_{\tau}$ and $\bm{V}_{(i),\tau}$ are
the global and local principal vectors at round $\tau$, then the following
inequality holds:

$\displaystyle
N\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\sum_{j=1}^{N}\frac{1}{N}\bm{P}_{\bm{V}_{(j),\tau}}\right)\bm{U}_{\tau}^{\star}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{V}_{(i),\tau}^{\star}\right\rVert_{F}^{2}$
(67) $\displaystyle\geq N\ell(\theta)\zeta_{\tau}-C_{9}\zeta_{\tau}^{1.5}$

where $\ell(\theta)$ is:

$\ell(\theta)=\frac{\theta^{2}}{2-\theta+\sqrt{\left(2-\theta\right)^{2}-\theta^{2}}}$
(68)

Proof

We begin by analyzing the first term in the inequality. By Definitions (65)
and (66), for any $i$, we know that:

$\displaystyle\left(\bm{I}_{d}-\bm{U}_{\tau}\bm{U}_{\tau}^{T}-\bm{V}_{(i),\tau}\bm{V}_{(i),\tau}^{T}\right)\bm{U}^{\star}_{\tau}$
(69)
$\displaystyle=\left(\bm{I}_{d}-\bm{U}_{\tau}^{\star}(\bm{U}_{\tau}^{\star})^{T}-\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}\right)\bm{U}^{\star}_{\tau}$
$\displaystyle-\left(\Delta\bm{U}_{\tau}(\bm{U}_{\tau}^{\star})^{T}+\Delta\bm{V}_{(i),\tau}(\bm{V}_{(i),\tau}^{\star})^{T}+\bm{V}_{(i),\tau}^{\star}(\Delta\bm{V}_{(i),\tau})^{T}\right)\bm{U}^{\star}_{\tau}$
$\displaystyle-\left(\Delta\bm{U}_{\tau}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\Delta\bm{V}_{(i),\tau})^{T}+\bm{U}_{\tau,\star}(\Delta\bm{U}_{\tau})^{T}\right)\bm{U}^{\star}_{\tau}$

The first term is $0$ by the definition of $\bm{U}^{\star}$ and
$\bm{V}_{(i)}^{\star}$. The second term is the leading term.

The norm of the third term is bounded as:

$\displaystyle\left\lVert\left(\Delta\bm{U}_{\tau}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\Delta\bm{V}_{(i),\tau})^{T}\right)\bm{U}^{\star}_{\tau}\right\rVert_{F}$
$\displaystyle\leq\left(\left\lVert\Delta\bm{U}^{\tau}\right\rVert_{F}^{2}+\left\lVert\Delta\bm{V}^{(n),\tau}\right\rVert_{F}^{2}\right)$

Then

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}_{d}-\bm{U}_{\tau}\bm{U}_{\tau}^{T}-\bm{V}_{(i),\tau}\bm{V}_{(i),\tau}^{T}\right)\bm{U}^{\star}_{\tau}$
$\displaystyle+\frac{1}{N}\sum_{i=1}^{N}\left(\Delta\bm{U}_{\tau}(\bm{U}_{\tau}^{\star})^{T}+\Delta\bm{V}_{(i),\tau}(\bm{V}_{(i),\tau}^{\star})^{T}+\bm{V}_{(i),\tau}^{\star}(\Delta\bm{V}_{(i),\tau})^{T}\right)\bm{U}^{\star}_{\tau}$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\left(\Delta\bm{U}_{\tau}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\Delta\bm{V}_{(i),\tau})^{T}+\bm{U}_{\tau,\star}(\Delta\bm{U}_{\tau})^{T}\right)\bm{U}^{\star}_{\tau}$
$\displaystyle=\bm{\epsilon}_{1,(0),\tau}$

where $\bm{\epsilon}_{1,(0),\tau}$ is defined as:

$\displaystyle\bm{\epsilon}_{1,(0),\tau}$
$\displaystyle=-\frac{1}{N}\sum_{i=1}^{N}\left(\Delta\bm{U}_{\tau}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\Delta\bm{V}_{(i),\tau})^{T}+\bm{U}_{\tau,\star}(\Delta\bm{U}_{\tau})^{T}\right)\bm{U}^{\star}_{\tau}$

Its norm is bounded by:

$\displaystyle\left\lVert\bm{\epsilon}_{1,(0),\tau}\right\rVert_{F}\leq\frac{1}{N}\sum_{i=1}^{N}\left(\left\lVert\Delta\bm{U}_{\tau}\right\rVert_{F}^{2}+\left\lVert\Delta\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$

The update of $\bm{V}_{(i)}$ can be estimated similarly:

$\displaystyle\left(\bm{I}_{d}-\bm{U}_{\tau}\bm{U}_{\tau}^{T}-\bm{V}_{(i),\tau}\bm{V}_{(i),\tau}^{T}\right)\bm{V}^{\star}_{(i),\tau}$
(70)
$\displaystyle=\left(\bm{I}_{d}-\bm{U}_{\tau}^{\star}(\bm{U}_{\tau}^{\star})^{T}-\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}\right)\bm{V}^{\star}_{(i),\tau}$
$\displaystyle-\left(\Delta\bm{U}_{\tau}(\bm{U}_{\tau}^{\star})^{T}+\bm{U}_{\tau,\star}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\bm{V}_{(i),\tau}^{\star})^{T}\right)\bm{V}^{\star}_{(i),\tau}$
$\displaystyle-\left(\Delta\bm{U}_{\tau}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\Delta\bm{V}_{(i),\tau})^{T}+\bm{V}_{(i),\tau}^{\star}(\Delta\bm{V}_{(i),\tau})^{T}\right)\bm{V}^{\star}_{(i),\tau}$

Similarly, we can define

$\displaystyle\bm{\epsilon}_{1,(i),\tau}=-\left(\Delta\bm{U}_{\tau}(\Delta\bm{U}_{\tau})^{T}+\Delta\bm{V}_{(i),\tau}(\Delta\bm{V}_{(i),\tau})^{T}\right)\bm{U}^{\star}_{\tau}$

Its norm is upper bounded by:

$\left\lVert\bm{\epsilon}_{1,(i),\tau}\right\rVert\leq\left\lVert\Delta\bm{U}_{\tau}\right\rVert_{F}^{2}+\left\lVert\Delta\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$

We define $\bm{\nu}_{\tau}$ as the vectorization of $\Delta\bm{U}_{\tau}$ and
$\Delta\bm{V}_{(i),\tau}$’s:

$\bm{\nu}_{\tau}=\text{vec}\left(\left[\Delta\bm{U}_{\tau},\Delta\bm{V}_{(1),\tau},\cdots,\Delta\bm{V}_{(N),\tau}\right]\right)$
(71)

and $\widetilde{\bm{\nu}_{\tau}}$ as:

$\widetilde{\bm{\nu}}_{\tau}=\text{vec}\left(\left[\sqrt{N}\Delta\bm{U}_{\tau},\Delta\bm{V}_{(1),\tau},\cdots,\Delta\bm{V}_{(N),\tau}\right]\right)$
(72)

By Lemma 17, we have:

$\displaystyle\left\lVert\widetilde{\bm{\nu}}_{\tau}\right\rVert=\sqrt{N\left\lVert\Delta\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\Delta\bm{V}_{(i),\tau}\right\rVert_{F}^{2}}$
$\displaystyle\geq\sqrt{N\zeta_{(0),\tau}+\sum_{i=1}^{N}\zeta_{(i),\tau}}$
$\displaystyle=\sqrt{N\zeta_{\tau}}$

and similarly,
$\left\lVert\bm{\nu}_{\tau}\right\rVert\leq\sqrt{2}\sqrt{\zeta_{\tau}}$.

We define $\bm{\omega}$ as the vectorization of
$\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\sum_{j=1}^{N}\frac{1}{N}\bm{P}_{\bm{V}_{(j),\tau}}\right)\bm{U}_{\tau}^{\star}$
and
$\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{V}_{(i),\tau}$’s:

$\displaystyle\bm{\omega}=\text{vec}\Big{(}\Big{[}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\sum_{j=1}^{N}\frac{1}{N}\bm{P}_{\bm{V}_{(j),\tau}}\right)\bm{U}_{\tau}^{\star},$
(73)
$\displaystyle\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(1),\tau}}\right)\bm{V}_{(1),\tau}^{\star},\cdots,\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{V}_{(N),\tau}^{\star}\Big{]}\Big{)}$

and $\bm{\varsigma}$ as the vectorization of $\bm{\epsilon}_{1,(0),\tau}$ and
$\bm{\epsilon}_{1,(i).\tau,}$’s:

$\bm{\varsigma}=\text{vec}\left(\left[\bm{\epsilon}_{1,(0),\tau},\cdots,\bm{\epsilon}_{1,(i),\tau}\right]\right)$
(74)

By Lemma 17, we have:

$\displaystyle\left\lVert\bm{\varsigma}\right\rVert=\sqrt{\sum_{i=0}^{N}\left\lVert\bm{\epsilon}_{1,(i),\tau}\right\rVert_{F}^{2}}$
$\displaystyle\leq\sum_{i=0}^{N}\left\lVert\bm{\epsilon}_{1,(i),\tau}\right\rVert_{F}$
$\displaystyle\leq\frac{N+1}{N}\left(N\left\lVert\Delta\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\Delta\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\right)$
$\displaystyle\leq 2(N+1)\zeta_{\tau}$

Remember that we use $\bm{\mathcal{D}}_{a,b,c}$ to denote a $(b+c)\times(b+c)$
diagonal matrix, whose first $b$ diagonal entries are $a$ and remaining $c$
diagonal entries are 1.

By definition of vectorization, we have:

$\bm{\omega}_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}\bm{\omega}_{\tau}=N\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\sum_{j=1}^{N}\frac{1}{N}\bm{P}_{\bm{V}_{(j),\tau}}\right)\bm{U}_{\tau}^{\star}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{V}_{(i),\tau}^{\star}\right\rVert_{F}^{2}$
(75)

With the vectorized matrices, we can rewrite equations (69) and (70) into the
following vector form:

$\bm{\omega}_{\tau}=A_{\tau}\bm{\nu}_{\tau}+\bm{\varsigma}_{\tau}$ (76)

where $A_{\tau}$ is an $rd(N+1)$ by $rd(N+1)$ matrix. It has a block
structure:

$A_{\tau}=\begin{pmatrix}A_{00}&A_{01}&A_{02}&\cdots&A_{0N}\\\
A_{10}&A_{11}&0&\cdots&0\\\ A_{20}&0&A_{22}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ A_{N0}&0&0&\cdots&A_{NN}\end{pmatrix}$

And the blocks are:

$A_{00}=\bm{I}_{r}\otimes\bm{I}_{d}$ (77)

For $i\in\\{1,\cdots,N\\}$, we have:

$A_{0i}=\frac{1}{N}\begin{pmatrix}\bm{v}_{(i),1}^{\star}(\bm{u}_{\tau,1}^{\star})^{T}&\bm{v}_{(i),2}^{\star}(\bm{u}_{\tau,1}^{\star})^{T}&\cdots&\bm{v}_{(i),r}^{\star}(\bm{u}_{\tau,1}^{\star})^{T}\\\
\bm{v}_{(i),1}^{\star}(\bm{u}_{\tau,2}^{\star})^{T}&\bm{v}_{(i),2}^{\star}(\bm{u}_{\tau,2}^{\star})^{T}&\cdots&\bm{v}_{(i),r}^{\star}(\bm{u}_{\tau,2}^{\star})^{T}\\\
\vdots&\vdots&\ddots&\vdots\\\
\bm{v}_{(i),1}^{\star}(\bm{u}_{\tau,r}^{\star})^{T}&\bm{v}_{(i),2}^{\star}(\bm{u}_{\tau,r}^{\star})^{T}&\cdots&\bm{v}_{(i),r}^{\star}(\bm{u}_{\tau,r}^{\star})^{T}\end{pmatrix}$
(78)

The diagonal block is also:

$A_{ii}=\bm{I}_{r}\otimes\bm{I}_{d}$ (79)

The off-diagonal block is defined as:

$A_{i0}=NA_{0i}^{T}$ (80)

Therefore:

$\displaystyle\bm{\omega}_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}\bm{\omega}_{\tau}$
(81)
$\displaystyle=\bm{\nu}_{\tau}^{T}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\nu}_{\tau}$
$\displaystyle+\bm{\nu}_{\tau}^{T}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}\bm{\varsigma}_{\tau}+\bm{\varsigma}_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\nu}_{\tau}+\bm{\varsigma}_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}\bm{\varsigma}_{\tau}$
$\displaystyle\geq\bm{\nu}_{\tau}^{T}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\nu}_{\tau}-2\left\lVert\bm{\varsigma}_{\tau}\right\rVert\left\lVert\bm{\mathcal{D}}_{N,rd,Nrd}\right\rVert_{op}\left\lVert
A_{\tau}\bm{\nu}_{\tau}\right\rVert$
$\displaystyle\geq\bm{\nu}_{\tau}^{T}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\nu}_{\tau}-2\left\lVert\bm{\varsigma}_{\tau}\right\rVert\left\lVert\bm{\mathcal{D}}_{N,rd,Nrd}\right\rVert_{op}\left\lVert
A_{\tau}\right\rVert_{op}\left\lVert\bm{\nu}_{\tau}\right\rVert$
$\displaystyle\geq\widetilde{\bm{\nu}_{\tau}}^{T}\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}\widetilde{\bm{\nu}}_{\tau}-4(N+1)\zeta_{\tau}N\sqrt{2(N+1)}\sqrt{2\zeta_{\tau}}$
$\displaystyle\geq\left\lVert\widetilde{\bm{\nu}}_{\tau}\right\rVert^{2}\lambda_{min}\left(\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}\right)-C_{9}N\zeta_{\tau}^{1.5}$

where we applied Lemma 25 in the third inequality. $C_{9}$ is a constant
defined as:

$C_{9}=8(N+1)\sqrt{N+1}$

We can introduce:

$B=\begin{pmatrix}A_{01}&A_{02}&\cdots&A_{0N}\\\ \end{pmatrix}$

Then $A_{\tau}$ satisfies the definition of $\theta$-block-arrowhead matrix in
Lemma 12. As shown in Lemma 12 and Sec. E, the minimum eigenvalue of
$\mathcal{Q}(A_{\tau})$ is lower bounded by
$\lambda_{min}\left(\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}A_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A_{\tau}\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}\right)\geq\ell(\theta)$.
As a result:

$\displaystyle\bm{\omega}_{\tau}^{T}\bm{\mathcal{D}}_{N,rd,Nrd}\bm{\omega}_{\tau}$
$\displaystyle\geq\left\lVert\widetilde{\bm{\nu}}_{\tau}\right\rVert^{2}\ell(\theta)-C_{9}N\zeta_{\tau}^{1.5}$
$\displaystyle\geq N\zeta_{\tau}\ell(\theta)-C_{9}N\zeta_{\tau}^{1.5}$

By the application of (75), we prove the inequality (67).

Remember that we introduced $\zeta_{(i),\tau}$’s and $\zeta_{\tau}$ in (30),
(31), and (32). Now we define some similar variables:

$\widetilde{\zeta}_{(i),\tau}=2r-\left\langle\bm{P}_{\bm{U}_{\tau}}+\bm{P}_{\bm{V}_{(i),\tau}},\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right\rangle$
(82)

for each $i=1,...N$. We use $\zeta_{\tau}$ to denote:

$\widetilde{\zeta}_{\tau}=\sum_{i=1}^{N}\zeta_{(i),\tau}$ (83)

From Lemma 2, there exists a relation between $\zeta_{\tau}$ and
$\widetilde{\zeta}_{\tau}$:

$\frac{\theta}{2}N\zeta_{\tau}\leq\widetilde{\zeta}_{\tau}\leq N\zeta_{\tau}$
(84)

The following lemma establishes a Polyak-Lojasiewicz-style inequality for the
update.

###### Lemma 23

Suppose $\mu$ is the lowest minimum eigenvalue of
$\\{\bm{S}_{(i)}\\}_{i=1,...,N}$, and $\square\bm{U}_{\tau}$ and
$\square\bm{V}_{(i),\tau}$’s are defined in (54) and (58), we have:

$N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}\geq\mu^{2}\ell(\theta)\zeta_{\tau}-C_{10}\zeta_{\tau}^{1.5}$
(85)

where $C_{10}$ is a constant:

$C_{10}=\mu^{2}C_{9}+2\sqrt{2}N(1+\sqrt{N})G_{max,op}^{2}\leq
O(N^{1.5}G_{max,op}^{2})$

Proof  We first calculate $\square\bm{U}_{\tau}$

$\displaystyle\square\bm{U}_{\tau}=\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}^{\star}+\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)$
$\displaystyle=\square\bm{U}_{\tau,1}+\square\bm{U}_{\tau,2}$

where

$\square\bm{U}_{\tau,1}=\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}^{\star}$

and

$\square\bm{U}_{\tau,2}=\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)$

We bound the norm of $\square\bm{U}_{\tau,2}$ as:

$\displaystyle\left\lVert\square\bm{U}_{\tau,2}\right\rVert_{F}$
$\displaystyle=\left\lVert\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right\rVert_{F}\left\lVert\bm{S}_{(i)}\right\rVert_{op}\left\lVert\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$

By Lemma 17, we know that:

$\displaystyle\left\lVert\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq\left\lVert\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right\rVert_{op}\left\lVert\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle=\left\lVert\Delta\bm{U}_{\tau}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left[\Delta\bm{U}_{\tau},\Delta\bm{V}_{(i),\tau}\right]\right\rVert_{F}$
$\displaystyle\leq\sqrt{2}\sqrt{\widetilde{\zeta}_{(i),\tau}}$

Also,

$\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right\rVert_{F}=\sqrt{\widetilde{\zeta}_{(i),\tau}}$

Combining them, we have:

$\displaystyle\left\lVert\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{U}_{\tau}-\bm{U}_{\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\sqrt{2}G_{(i),op}\widetilde{\zeta}_{(i),\tau}$
$\displaystyle\leq\sqrt{2}G_{max,op}\zeta_{\tau}$

where we used Lemma 2 in the second inequality.

Also,

$\displaystyle\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}$
$\displaystyle=\left\lVert\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}^{\star}\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}^{\star}\right\rVert_{F}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\bm{U}_{\tau}^{\star}\right\rVert_{F}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right\rVert_{F}\left\lVert\bm{S}_{(i)}\right\rVert_{op}\left\lVert\bm{U}_{\tau}^{\star}\right\rVert_{op}$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{N}\sqrt{\widetilde{\zeta}_{(i),\tau}}G_{op,max}$
$\displaystyle\leq\sqrt{\frac{1}{N}\sum_{i=1}^{N}\widetilde{\zeta}_{(i),\tau}}G_{op,max}$
$\displaystyle\leq\sqrt{\zeta_{\tau}}G_{op,max}$

For the update of $\bm{V}_{(i),\tau}$

$\displaystyle\square\bm{V}_{(i),\tau}=\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau}$
$\displaystyle=\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau}^{\star}+\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{V}_{(i),\tau}-\bm{V}_{(i),\tau}^{\star}\right)$
$\displaystyle=\square\bm{V}_{(i),\tau,1}+\square\bm{V}_{(i),\tau,2}$

where the first term is defined as:

$\square\bm{V}_{(i),\tau,1}=\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{V}_{(i),\tau}^{\star}$
(86)

and the second term is defined as

$\square\bm{V}_{(i),\tau,2}=\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{V}_{(i),\tau}-\bm{V}_{(i),\tau}^{\star}\right)$
(87)

We can bound the norm of $\square\bm{V}_{(i),\tau,2}$ as:

$\displaystyle\left\lVert\square\bm{V}_{(i),\tau,2}\right\rVert_{F}$
$\displaystyle=\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\left(\bm{V}_{(i),\tau}-\bm{V}_{(i),\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{V}_{(i),\tau}-\bm{V}_{(i),\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right\rVert_{F}\left\lVert\bm{S}_{(i)}\right\rVert_{op}\left\lVert\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{V}_{(i),\tau}-\bm{V}_{(i),\tau}^{\star}\right)\right\rVert_{F}$
$\displaystyle\leq G_{max,op}\sqrt{2}\widetilde{\zeta}_{(i),\tau}$

and bound the norm of $\square\bm{V}_{\tau,1}$ as:

$\displaystyle\left\lVert\square\bm{V}_{\tau,1}\right\rVert_{F}\leq\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\bm{U}_{\tau}^{\star}\right\rVert_{F}$
$\displaystyle=\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\bm{S}_{(i)}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right\rVert_{F}\left\lVert\bm{S}_{(i)}\right\rVert_{op}$
$\displaystyle\leq G_{max,op}\sqrt{\widetilde{\zeta}_{(i),\tau}}$

With the decomposition,

$\square\bm{U}_{\tau}=\square\bm{U}_{\tau,1}+\square\bm{U}_{\tau,2}$

and

$\square\bm{V}_{(i),\tau}=\square\bm{V}_{(i),\tau,1}+\square\bm{V}_{(i),\tau,2}$

we have:

$\displaystyle
N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$
$\displaystyle=N\left\lVert\square\bm{U}_{\tau,1}+\square\bm{U}_{\tau,2}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau,1}+\square\bm{V}_{(i),\tau,2}\right\rVert_{F}^{2}$
$\displaystyle\geq
N\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}^{2}-2N\left\lVert\square\bm{U}_{\tau,2}\right\rVert_{F}\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}$
$\displaystyle+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau,1}\right\rVert_{F}^{2}-2\left\lVert\square\bm{V}_{(i),\tau,1}\right\rVert_{F}\left\lVert\square\bm{V}_{(i),\tau,2}\right\rVert_{F}$

For the leading term, we have:

$\displaystyle
N\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau,1}\right\rVert_{F}^{2}$
$\displaystyle=N\text{Tr}\left(\left(\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\right)^{2}\bm{S}_{(i)}\bm{U}_{\tau}^{\star}(\bm{U}_{\tau}^{\star})^{T}\bm{S}_{(i)}\right)$
$\displaystyle+\sum_{i=1}^{N}\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)^{2}\bm{S}_{(i)}\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}\bm{S}_{(i)}\right)$

Since

$\bm{S}_{(i)}\bm{U}_{\tau}^{\star}(\bm{U}_{\tau}^{\star})^{T}\bm{S}_{(i)}\succeq\mu^{2}\bm{U}_{\tau}^{\star}(\bm{U}_{\tau}^{\star})^{T}$

and

$\bm{S}_{(i)}\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}\bm{S}_{(i)}\succeq\mu^{2}\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}$

By Lemma 13, we have:

$\displaystyle
N\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau,1}\right\rVert_{F}^{2}$
$\displaystyle\geq\mu^{2}N\text{Tr}\left(\left(\frac{1}{N}\sum_{i=1}^{N}\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\right)^{2}\bm{U}_{\tau}^{\star}(\bm{U}_{\tau}^{\star})^{T}\right)$
$\displaystyle+\mu^{2}\sum_{i=1}^{N}\text{Tr}\left(\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)^{2}\bm{V}_{(i),\tau}^{\star}(\bm{V}_{(i),\tau}^{\star})^{T}\right)$
$\displaystyle\geq\mu^{2}\left(\ell(\theta)N\zeta_{\tau}-C_{9}N\zeta_{\tau}^{1.5}\right)$

where we use Lemma 22 in the last inequality with the condition that
$\ell(\theta)\zeta_{\tau}\geq C_{9}\zeta_{\tau}^{1.5}$.

For the cross terms, since we know that
$\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}\leq\frac{1}{\sqrt{N}}\sqrt{r\widetilde{\zeta}_{\tau}}G_{max,F}$,
we can derive:

$\displaystyle
2N\left\lVert\square\bm{U}_{\tau,2}\right\rVert_{F}\left\lVert\square\bm{U}_{\tau,1}\right\rVert_{F}+2\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau,1}\right\rVert_{F}\left\lVert\square\bm{V}_{(i),\tau,2}\right\rVert_{F}$
$\displaystyle\leq
2\sqrt{2}NG_{max,op}^{2}\zeta_{\tau}^{1.5}+2\sqrt{2}G_{max,op}^{2}\sum_{i=1}^{N}\widetilde{\zeta}_{(i),\tau}^{1.5}$
$\displaystyle\leq
2\sqrt{2}NG_{max,op}^{2}\zeta_{\tau}^{1.5}+2\sqrt{2}G_{max,op}^{2}N^{1.5}\left(\frac{1}{N}\sum_{i=1}^{N}\widetilde{\zeta}_{(i),\tau}\right)^{1.5}$
$\displaystyle\leq
2\sqrt{2}NG_{max,op}^{2}\zeta_{\tau}^{1.5}+2\sqrt{2}N^{1.5}G_{max,op}^{2}\zeta_{\tau}^{1.5}$
$\displaystyle=2\sqrt{2}N(1+\sqrt{N})G_{max,op}^{2}\zeta_{\tau}^{1.5}$

Combining the inequalities, we have:

$\displaystyle
N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$
$\displaystyle\geq\mu^{2}N\ell(\theta)\zeta_{\tau}-NC_{10}\zeta_{\tau}^{1.5}$

where $C_{10}=\mu^{2}C_{9}+2\sqrt{2}(1+\sqrt{N})G_{max,op}^{2}$

This completes our proof.

###### Lemma 24

Suppose the optimal value of objective is $f^{\star}$, we have:

$G_{max,op}\zeta_{\tau}\geq
f^{\star}-f(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\})$

Proof  The proof is straightforward.

For the objective on client $i$, we have:

$\displaystyle f_{i}^{\star}-f_{i}$
$\displaystyle=\text{Tr}\left(\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right)-\text{Tr}\left(\bm{S}_{(i)}\left(\bm{P}_{\bm{U}_{\tau}}+\bm{P}_{\bm{V}_{(i),\tau}}\right)\right)$
$\displaystyle=\text{Tr}\left(\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right)-\text{Tr}\left(\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{P}_{\bm{U}_{\tau}}+\bm{P}_{\bm{V}_{(i),\tau}}\right)\right)$
$\displaystyle=\text{Tr}\left(\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right)-\text{Tr}\left(\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{P}_{\bm{U}_{\tau}}+\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right)$
$\displaystyle=\text{Tr}\left(\bm{S}_{(i)}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right)$
$\displaystyle\leq
G_{(i),op}\text{Tr}\left(\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{I}-\bm{P}_{\bm{U}_{\tau}}-\bm{P}_{\bm{V}_{(i),\tau}}\right)\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\right)$
$\displaystyle=G_{(i),op}\left(2r-\text{Tr}\left(\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)\left(\bm{P}_{\bm{U}_{\tau}}+\bm{P}_{\bm{V}_{(i),\tau}}\right)\right)\right)$
$\displaystyle=G_{(i),op}\widetilde{\zeta}_{(i),\tau}$

where we apply the result in Lemma 13 and the fact that $\bm{S}_{(i)}\preceq
G_{(i),op}\left(\bm{\Pi}_{g}+\bm{\Pi}_{(i)}\right)$.

Then we can sum the above inequality for $i$ from 1 to $N$:

$\displaystyle\sum_{i=1}^{N}f_{i}^{\star}-f_{i}$ (88)
$\displaystyle\leq\sum_{i=1}^{N}G_{(i),op}\zeta_{(i),\tau}$ $\displaystyle\leq
NG_{max,op}\zeta_{\tau}$

This completes the proof.
Finally we come to the proof of Theorem 10:

Proof  Combining Lemma 23 and Lemma 24, we know that when $\zeta_{\tau}$ is
sufficiently small:

$\sqrt{\zeta_{\tau}}\leq\frac{\ell(\theta)\mu^{2}}{2C_{10}}\leq
O\left(\frac{\ell(\theta)\mu^{2}}{N^{1.5}G_{max,op}^{2}}\right)$

we have:

$\displaystyle
N\left\lVert\square\bm{U}_{\tau}\right\rVert_{F}^{2}+\sum_{i=1}^{N}\left\lVert\square\bm{V}_{(i),\tau}\right\rVert_{F}^{2}$
$\displaystyle\geq\mu^{2}N\ell(\theta)\zeta_{\tau}-NC_{10}\zeta_{\tau}^{1.5}$
$\displaystyle\geq\frac{1}{2}\mu^{2}N\ell(\theta)\zeta_{\tau}$
$\displaystyle\geq\frac{\mu^{2}\ell(\theta)}{2G_{max,op}}\left(f^{\star}-f(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\})\right)$

Therefore from equation 62, we know:

$\displaystyle-f\left(\bm{U}_{\tau+1},\\{\bm{V}_{(i),\tau+1}\\}\right)\leq-f\left(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\}\right)-\frac{\eta_{\tau}\mu^{2}\ell(\theta)}{4NG_{max,op}}\left(f^{\star}-f(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\})\right)$

We add $f^{\star}$ on both sides:

$\displaystyle
f^{\star}-f\left(\bm{U}_{\tau+1},\\{\bm{V}_{(i),\tau+1}\\}\right)$
$\displaystyle\leq
f^{\star}-f\left(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\}\right)-\frac{\eta_{\tau}\mu^{2}\ell(\theta)}{4G_{max,op}}\left(f^{\star}-f(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\})\right)$
$\displaystyle=\left(1-\frac{\eta_{\tau}\mu^{2}\ell(\theta)}{4G_{max,op}}\right)\left(f^{\star}-f(\bm{U}_{\tau},\\{\bm{V}_{(i),\tau}\\})\right)$

This completes the proof of Theorem 10.

##  Appendix E The spectral analysis on $\theta$-block-arrowhead matrix $A$

In this section, we will give a lower bound of the minimum eigenvalue of
$\theta$-arrowhead matrices. The analysis has stand-alone value as no previous
works on estimating eigenvalues of matrices can give reasonable results, to
our best knowledge.

The lower bound on the minimum eigenvalue is nontrivial because $A$ is
nonsymmetric, and
$\mathcal{Q}(A)=\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}A^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}$
is not necessarily diagonal dominant. Therefore, a bound given by conventional
matrix perturbation theory like Gershgorin’s circle theorem, becomes vacuous:
the lower bound on the eigenvalue of a positive semidefinite matrix is
negative. Our result is novel and applies to a general form of matrices.

The bound (34) is surprisingly tight. In some of our numerical simulations,
the difference between $\ell(\theta)$ and the numerical solution for the
minimum eigenvalue is smaller than $10^{-14}$. We present the proof of Lemma
12:

Proof  Remember that:

$\mathcal{Q}(A)=\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}A^{T}\bm{\mathcal{D}}_{N,rd,Nrd}A\bm{\mathcal{D}}_{\frac{1}{\sqrt{N}},rd,Nrd}=\begin{pmatrix}\bm{I}+NBB^{T}&2\sqrt{N}B\\\
2\sqrt{N}B^{T}&\bm{I}+NB^{T}B\\\ \end{pmatrix}$

Suppose $\bm{\alpha}=(\bm{\alpha}_{0}^{T},\bm{\alpha}_{1}^{T})^{T}$ is an
eigenvector of matrix $\mathcal{Q}(A)$ with corresponding eigenvalue
$\lambda$:

$\mathcal{Q}(A)\bm{\alpha}=\lambda\bm{\alpha}$ (89)

The second block of the eigen-equations (89) is:

$2\sqrt{N}B^{T}\bm{\alpha}_{0}+\left(\bm{I}+NB^{T}B\right)\bm{\alpha}_{1}=\lambda\bm{\alpha}_{1}$

We can solve for $\bm{\alpha}_{1}$:

$\bm{\alpha}_{1}=-2\sqrt{N}\left((1-\lambda)\bm{I}+NB^{T}B\right)^{-1}B^{T}\bm{\alpha}_{0}$

Plugging this into the first block of the eigen-equations (89):

$\left(\bm{I}+NBB^{T}\right)\bm{\alpha}_{0}+2\sqrt{N}B\bm{\alpha}_{1}=\lambda\bm{\alpha}_{0}$

we have:

$\left(\bm{I}+NBB^{T}\right)\bm{\alpha}_{0}-4NB\left((1-\lambda)\bm{I}+NB^{T}B\right)^{-1}B^{T}\bm{\alpha}_{0}=\lambda\bm{\alpha}_{0}$

Similarly, we can solve the above equation for $\bm{\alpha}_{0}$:

$\bm{\alpha}_{0}=4N\left((1-\lambda)\bm{I}+N^{2}BB^{T}\right)^{-1}B\left((1-\lambda)\bm{I}+NB^{T}B\right)^{-1}B^{T}\bm{\alpha}_{0}$

By matrix inversion lemma, when $\lambda<1$:

$\left((1-\lambda)\bm{I}+NB^{T}B\right)^{-1}=\frac{1}{1-\lambda}\left(\bm{I}-B^{T}\left(\frac{\bm{I}}{N}+\frac{1}{1-\lambda}BB^{T}\right)^{-1}B\frac{1}{1-\lambda}\right)$

With some algebra, we have:

$\displaystyle
4N\left((1-\lambda)\bm{I}+NBB^{T}\right)^{-1}B\left((1-\lambda)\bm{I}+NB^{T}B\right)^{-1}B^{T}$
$\displaystyle=4N\left((1-\lambda)\bm{I}+NBB^{T}\right)^{-1}B\frac{1}{1-\lambda}\left(\bm{I}-B^{T}\left(\frac{\bm{I}}{N}+\frac{1}{1-\lambda}BB^{T}\right)^{-1}B\frac{1}{1-\lambda}\right)B^{T}$
$\displaystyle=4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}$

where $C_{B}$ is a matrix defined as:

$C_{B}=NBB^{T}$

Note that the second assumption of Lemma 12 requires that

$0\preceq C_{B}\preceq(1-\theta)\bm{I}$

Therefore, we can rewrite the eigen-equation on $\bm{\alpha}_{0}$ as:

$\bm{\alpha}_{0}=4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}\bm{\alpha}_{0}$

The equation shows that $\bm{\alpha}_{0}$ is an eigenvector of
$4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}$
with eigenvalue $1$. As a result, the operator norm of the matrix should be no
smaller than $1$:

$\lambda_{max}\left(4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}\right)\geq
1$ (90)

We now show, by contradiction, that $\forall\lambda\in\mathbb{R}$ that
satisfies the inequality (90), it must be lower bounded by $\ell(\theta)$:

$\lambda\geq\ell(\theta)=\frac{\theta^{2}}{2-\theta+\sqrt{\left(2-\theta\right)^{2}-\theta^{2}}}$
(91)

Suppose there exists a $\widetilde{\lambda}$ such that:

$0\leq\widetilde{\lambda}<\ell(\theta)$ (92)

Since $C_{B}$ is real symmetric positive semidefinite, by spectral theorem, it
has eigen-decomposition

$C_{B}=\sum_{i=1}^{rd}\lambda_{C_{B},i}\vartheta_{i}\vartheta_{i}^{T}$ (93)

with all eigenvalues bounded by:

$0\leq\lambda_{C_{B},i}\leq 1-\theta$

Then,

$4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}=4\sum_{i=1}^{rd}\frac{\lambda_{C_{B},i}}{\left(1-\lambda+\lambda_{C_{B},i}\right)^{2}}\vartheta_{i}\vartheta_{i}^{T}$

The operator norm of
$4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}$
is defined as:

$\displaystyle\max_{\bm{\beta}}\bm{\beta}^{T}4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}\bm{\beta}$
$\displaystyle\text{such that}\left\lVert\bm{\beta}\right\rVert=1$

We can write the objective in summation form:

$\displaystyle\bm{\beta}^{T}4\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}C_{B}\left((1-\lambda)\bm{I}+C_{B}\right)^{-1}\bm{\beta}$
$\displaystyle=4\sum_{i=1}^{rd}\frac{\lambda_{C_{B},i}}{\left((1-\lambda)+\lambda_{C_{B},i}\right)^{2}}\left(\vartheta_{i}^{T}\bm{\beta}\right)^{2}$
$\displaystyle\leq
4\max_{i=1,\cdots,rd}\frac{\lambda_{C_{B},i}}{\left((1-\lambda)+\lambda_{C_{B},i}\right)^{2}}\sum_{j=1}^{rd}\left(\vartheta_{j}^{T}\bm{\beta}\right)^{2}$
$\displaystyle=4\max_{i=1,\cdots,rd}\frac{\lambda_{C_{B},i}}{\left((1-\lambda)+\lambda_{C_{B},i}\right)^{2}}$

When $\widetilde{\lambda}$ satisfies the assumption (92),
$\widetilde{\lambda}\leq\ell(\theta)\leq\theta$, it is easy to verify that
$\frac{\lambda_{C_{B},i}}{\left((1-\widetilde{\lambda})+\lambda_{C_{B},i}\right)^{2}}$
is an increasing function of $\lambda_{C_{B},i}$ on $[0,1-\theta]$, therefore:

$\displaystyle\frac{\lambda_{C_{B},i}}{\left((1-\widetilde{\lambda})+\lambda_{C_{B},i}\right)^{2}}\leq\frac{1-\theta}{\left((1-\widetilde{\lambda})+1-\theta\right)^{2}}$

Since the right hand side is an increasing function of $\widetilde{\lambda}$
in the range specified by (92), we have:

$\frac{1-\theta}{\left((1-\widetilde{\lambda})+1-\theta\right)^{2}}<\frac{1-\theta}{\left((1-\ell(\theta))+1-\theta\right)^{2}}=\frac{1}{4}$

which contradicts equation (90) . This completes the proof.
Next we give an upper bound of the operator norm of $A$.

###### Lemma 25

The operator norm of a $\theta$-arrowhead matrix $A$ is bounded by:

$\left\lVert A\right\rVert_{op}\leq\sqrt{2(N+1)}$ (94)

Proof  By decomposition

$A=\bm{I}+\begin{pmatrix}0&B\\\ NB^{T}&0\\\ \end{pmatrix}$

we have:

$A^{T}A=\begin{pmatrix}\bm{I}+N^{2}BB^{T}&(N+1)B\\\
(N+1)B^{T}&\bm{I}+B^{T}B\\\ \end{pmatrix}$

Therefore,

$\left\lVert
A^{T}A\right\rVert_{op}=\left\lVert\begin{pmatrix}\bm{I}+N^{2}BB^{T}&0\\\
0&\bm{I}+B^{T}B\\\
\end{pmatrix}\right\rVert_{op}+\left\lVert\begin{pmatrix}0&(N+1)B\\\
(N+1)B^{T}&0\\\ \end{pmatrix}\right\rVert_{op}$

For the first term, since $\left\lVert NBB^{T}\right\rVert_{op}\leq
1-\theta\leq 1$, and $\left\lVert B^{T}B\right\rVert_{op}=\left\lVert
BB^{T}\right\rVert_{op}$, we know:

$\left\lVert\begin{pmatrix}\bm{I}+N^{2}BB^{T}&0\\\ 0&\bm{I}+B^{T}B\\\
\end{pmatrix}\right\rVert_{op}\leq 1+N$

For the second term, we have:

$\displaystyle\left\lVert\begin{pmatrix}0&B\\\ B^{T}&0\\\
\end{pmatrix}\right\rVert_{op}^{2}=\left\lVert\begin{pmatrix}BB^{T}&0\\\
0&B^{T}B\\\ \end{pmatrix}\right\rVert_{op}\leq\frac{1}{N}$

Thus:

$\left\lVert A^{T}A\right\rVert_{op}\leq 1+N+(1+N)\frac{1}{N}\leq 2(N+1)$

We thus complete the proof.