# Improved Performance Guarantees for Orthogonal Group Synchronization via
Generalized Power Metho

Shuyang Ling New York University Shanghai (Email: sl3635@nyu.edu). This work
is partially supported by National Natural Science Foundation of China (NSFC)
No.12001372 and a grant from Shanghai Municipal Education Commission (SMEC).

###### Abstract

Given the noisy pairwise measurements among a set of unknown group elements,
how to recover them efficiently and robustly? This problem, known as group
synchronization, has drawn tremendous attention in the scientific community.
In this work, we focus on orthogonal group synchronization that has found many
applications, including computer vision, robotics, and cryo-electron
microscopy. One commonly used approach is the least squares estimation that
requires solving a highly nonconvex optimization program. The past few years
have witnessed considerable advances in tackling this challenging problem by
convex relaxation and efficient first-order methods. However, one fundamental
theoretical question remains to be answered: how does the recovery performance
depend on the noise strength? To answer this question, we study a benchmark
model: recovering orthogonal group elements from their pairwise measurements
corrupted by Gaussian noise. We investigate the performance of convex
relaxation and the generalized power method (GPM). By applying the novel
_leave-one-out_ technique, we prove that the GPM with spectral initialization
enjoys linear convergence to the global optima to the convex relaxation that
also matches the maximum likelihood estimator. Our result achieves a near-
optimal performance bound on the convergence of the GPM and improves the
state-of-the-art theoretical guarantees on the tightness of convex relaxation
by a large margin.

##  1 Introduction

Group synchronization aims to recover group elements $\\{g_{i}\\}_{i=1}^{n}$
from their pairwise measurements:

$g_{ij}=g_{i}g_{j}^{-1}+\text{noise},\quad(i,j)\in{\cal E}$

where ${\cal E}$ is a given edge set. It has attracted an increasing amount of
attention in the past few years as it can be often found in various
applications. Examples include computer vision (special orthogonal group
SO($d$)) [4, 15], robotics (special Euclidean group SE($d$)) [48], cryo-
electron microscopy (SO(3)) [50, 52, 53], clock-synchronization on networks
[28], sensor network localization (Euclidean group) [22], joint alignment
($\hbox{\msbm{Z}}_{n}$-group) [16] and community detection
($\hbox{\msbm{Z}}_{2}$-group) [1, 21]. Without noise, solving group
synchronization is a trivial task since one can recover every group element
sequentially and they are uniquely determined modulo a global group action.
However, it is often highly challenging to solve the group synchronization
problem in the presence of noise. When the noise exists, sequential recovery
no longer works as it would amplify the noise.

Recent few years have seen many theoretical and algorithmic progresses in
solving group synchronization under various types of noise and with different
underlying network structures [6, 32, 37, 44, 48, 60]. In this work, we are
interested in studying how to recover orthogonal group elements
$\bm{G}_{i}\in\operatorname{O}(d)$ from the pairwise measurements corrupted by
Gaussian noise,

$\displaystyle\bm{A}_{ij}$
$\displaystyle=\bm{G}_{i}\bm{G}_{j}^{\top}+\sigma\bm{W}_{ij},$ (1.1)
$\displaystyle\operatorname{O}(d)$
$\displaystyle:=\\{\bm{O}\in\hbox{\msbm{R}}^{d\times
d}:\bm{O}\bm{O}^{\top}=\bm{O}^{\top}\bm{O}=\bm{I}_{d}\\},$

where $\sigma$ measures the noise strength and
$\bm{W}_{ij}=\bm{W}_{ji}^{\top}\in\hbox{\msbm{R}}^{d\times d}$ is a Gaussian
random matrix with each entry an independent standard normal random variable.

Why is (1.1) an interesting model to study? Orthogonal group is a
generalization of many useful groups such as $\hbox{\msbm{Z}}_{2}:=\\{1,-1\\}$
and unitary group
$U(1):=\\{e^{\operatorname{\mathrm{i}}\theta}:\theta\in[0,2\pi)\\}$, and
contains permutation groups and special orthogonal group as subgroups.
Moreover, $\operatorname{O}(d)$ synchronization plays an important role in the
special Euclidean group synchronization problem $\text{SE}(d)$, a core problem
in SLAM (simultaneous localization and mapping) [48] and sensor network
localization [22]. Therefore, studying this benchmark model provides more
insights into solving many relevant problems.

Given this statistical model (1.1), one common approach is maximum likelihood
estimation (MLE) which is equivalent to finding the least squares estimator.
Minimizing the least squares cost function is a potentially NP-hard problem in
general since it includes graph max-cut [29] as a special case $d=1$. On the
other hand, many numerical simulations and previous theoretical works indicate
that despite its seeming NP-hardness, $\operatorname{O}(d)$ synchronization is
solvable with an efficient algorithm if noise level is relatively low. The
focus of this paper is analyzing the performance of semidefinite relaxation
and generalized power method in solving (1.1). More precisely, we attempt to
answer two questions:

_When does convex relaxation recover the least squares estimator?_

The first question concerns tightness: the solution to the relaxed convex
program is not necessarily equal to the least squares estimator in general.
When are they the same?

_Can we design an efficient algorithm to solve this orthogonal group
synchronization?_

The second question is about efficient recovery: in practice, we do not often
use SDP (semidefinite programming) relaxation due to its expensive
computational costs. As a result, finding an efficient algorithm with global
convergence will be very favorable. In particular, we will study the
convergence of generalized power method applied to $\operatorname{O}(d)$
synchronization [9, 37, 38, 60]. The answers to both questions are closely
related to the noise strength, namely $\sigma$. As the noise strength
increases, the recovery problem becomes more challenging. Therefore, we aim to
identify a regime for $\sigma$ within which the generalized power method will
successfully and efficiently recover the maximum likelihood estimator.

###  1.1 Related works

Since there is an extensive literature on group synchronization, we are not
able to provide an exhaustive literature review. Instead, we will give a brief
review of these works that inspire ours. Group synchronization has been
studied for several different groups including
$\hbox{\msbm{Z}}_{2}=\\{-1,1\\}$ [1, 2, 6, 36], angular (phase)
synchronization [5, 37, 51, 60], permutation group [20, 31, 43, 49], special
Euclidean group [22, 48], and finite cyclic group [16]. For
$\operatorname{O}(d)$ synchronization, it has found broad applications in
computer vision [4, 19, 42, 54] and cryo-electron microscopy [52, 53].

Due to the practical importance of $\operatorname{O}(d)$ synchronization,
numerous efforts have been made towards developing fast and reliable
algorithms, as well as mathematical theory. One major difficulty of solving
$\operatorname{O}(d)$ synchronization is its severe nonconvexity in the least
squares estimation. The nonconvexity makes naive local search algorithms
vulnerable to poor local optima. Therefore, one needs to come up with
alternative approaches to overcome these issues. Convex relaxation, especially
semidefinite relaxation, is viewed as one of the most powerful methods in
solving these highly nonconvex programs. The SDP relaxation of
$\hbox{\msbm{Z}}_{2}$ synchronization is studied in [1] which obtains a near-
optimal performance bound for the exact recovery of hidden group elements from
corrupted measurements. The work [51] by Singer studies angular
synchronization by spectral methods and semidefinite program in presence of
random noise. Later on, [5] provides the first yet suboptimal theoretical
guarantee for the tightness of SDP relaxation for angular synchronization. The
near-optimal bound is first established in [60] which uses the leave-one-out
technique. In [58], the authors studies the SDP relaxation approach for
$\operatorname{SO}(d)$ synchronization with a subset of measurements corrupted
by arbitrary random orthogonal matrices, and obtained a near-optimal
performance guarantee with respect to the corruption level. The convex
relaxation of $\operatorname{O}(d)$ synchronization under arbitrary noise is
recently studied in [35] which gives a sub-optimal performance bound.

However, even if SDP relaxation works in many scenarios, its expensive
computational costs does not allow wide uses in practice. Instead, it is more
practical to use fast low-rank nonconvex optimization approach for
$\operatorname{O}(d)$ synchronization including Riemannian optimization [3, 8,
11, 12, 13, 24, 40, 48, 57, 59] since the solution is often low-rank. In
particular, the Burer-Monteiro factorization [12, 13] has gained substantial
popularity due to its great empirical successes in solving large-scale SDPs.
However, since the objective function associated with Burer-Monteiro
factorization is nonconvex, there is always risk that the iterates might get
stuck at one of the poor local optima. Recent theoretical progresses have
shown that as long as the degree of freedom $p$ in the search space is large
(scales like $p\approx\sqrt{2n}$ where $n$ is the number of constraints), the
first and second order necessary optimality conditions are sufficient to
guarantee global optimality [11, 57], which provides a solid theoretical
foundation for the Burer-Monteiro approach. Moreover, even if one chooses a
search space of much smaller dimension, the Burer-Monteiro factorization still
works [10, 34] in the examples such as community detection, and
$\hbox{\msbm{Z}}_{2}$\- and $\operatorname{O}(d)$ synchronization, provided
that the noise is sufficiently small (not optimal). Other approaches of group
synchronization includes the convenient spectral relaxation [34, 47, 51, 53],
often providing a solution close to the ground truth but not as good as the
maximum likelihood estimator. Message passing type algorithms are also
discussed in group synchronization [32, 44] in which a general algorithmic
framework is established to solve a large class of compact group
synchronization problems.

The performances of projected power method in joint alignment problem
($\hbox{\msbm{Z}}_{m}$-cyclic group) and angular synchronization are studied
in a series of works [9, 16, 37, 60]. The algorithm consists of an ordinary
power iteration plus a projection to the group. One core question regarding
the power method is: when can we recover the maximum likelihood estimator via
generalized power method? The answer depends on the noise level. The work [16]
proves that projected power method with proper initialization converges to the
MLE for joint alignment problem and achieves an information-theoretically
optimal performance bound in the asymptotic regime. For angular
synchronization, the inspiring work [60] employs the leave-one-out technique
and is able to establish a near-optimal bound on the noise strength to ensure
the global convergence of generalized power method to the MLE. As a by-
product, [60] also provides a near-optimal bound for the tightness of SDP
relaxation. Recently, [38] proposes an algorithmic framework based on
generalized power method to solve the synchronization of $\operatorname{O}(d)$
group and its subgroups such as permutation group and special orthogonal
group. The authors also provide a theoretical analysis on how far the output
from GPM is away from the ground truth.

One important technical ingredient in our work is matrix perturbation theory
[23, 46, 56, 26], commonly used in statistics, signal processing, and machine
learning. In particular, our analysis relies on matrix perturbation argument
to analyze the spectral initialization. However, the classical Davis-Kahan
theorem [23] is insufficient to directly provide a tight bound because we need
a block-wise operator norm bound for the eigenvectors while Davis-Kahan
theorem only gives an error bound in $\ell_{2}$-norm. Our work benefits
greatly from the leave-one-out technique in [2, 17, 27, 39, 60] which is used
to overcome this technical challenge. This technique has proven to be a
surprisingly powerful method in dealing with the statistical dependence
between the signal and noisy measurements, and allowing us to achieve near-
optimal performance bounds. We have seen many successful examples including
$\hbox{\msbm{Z}}_{2}$-synchronization and community detection under stochastic
block model [2], statistical ranking problem [18], $\ell_{\infty}$-norm
eigenvector perturbation [27], spectral clustering [25], and phase
retrieval/blind deconvolution [33, 39], and matrix completion [17, 39].

Our main contribution of this work is multifold. The work studies the global
convergence of generalized power method [38] and the performance of SDP
relaxation [8, 48, 11, 35] in solving orthogonal group synchronization with
data corrupted by Gaussian noise. Despite the aforementioned progresses, there
still exists a gap between the theory and practice. Numerical experiments
indicate that SDP relaxation and generalized power methods work if the noise
strength $\sigma\lesssim\sqrt{n}/(\sqrt{d}+\sqrt{\log n})$ holds, modulo a
possible log-factor. However, the state-of-the-art guarantee $\sigma\lesssim
n^{1/4}/d^{3/4}$ in [35] is still far from this empirical observations in
$\operatorname{O}(d)$-synchronization for $d\geq 3.$ We establish a near-
optimal performance bound for the global convergence to the maximum likelihood
estimator as well as the tightness of SDP relaxation. Our result narrows the
gap between theory and empirical observation by showing that GPM and SDP
relaxation work if $\sigma\lesssim\sqrt{n}/\sqrt{d}(\sqrt{d}+\sqrt{\log n})$,
only losing a factor of $\sqrt{d}$ to the detection threshold [45]. Moreover,
we provide a near-optimal error bound between the MLE and ground truth. Our
work can be viewed as a generalization of the projected power method for phase
synchronization [60] to orthogonal group synchronization [38]. However, since
$U(1)$ in [60] is a commutative group while orthogonal group
$\operatorname{O}(d)$ is non-commutative for $d\geq 3$, this fundamental
difference requires many different technical treatments in the proof.
Moreover, this result complements the work [38] by answering what the limiting
point of GPM is, i.e., the convergence to the MLE for the iterates from
generalized power method under (1.1).

###  1.2 Organization

We will discuss the preliminaries including model setup and algorithm in
Section 2. The main results will be provided in Section 3 and the proofs are
given in Section 4.

###  1.3 Notation

We denote vectors and matrices by boldface letters $\bm{x}$ and $\bm{X}$
respectively. For a given matrix $\bm{X}$, $\bm{X}^{\top}$ is the transpose of
$\bm{X}$ and $\bm{X}\succeq 0$ means $\bm{X}$ is positive semidefinite. Let
$\bm{I}_{n}$ be the identity matrix of size $n\times n$. For two matrices
$\bm{X}$ and $\bm{Y}$ of the same size, their inner product is
$\langle\bm{X},\bm{Y}\rangle=\operatorname{Tr}(\bm{X}^{\top}\bm{Y})=\sum_{i,j}X_{ij}Y_{ij}.$
Let $\|\bm{X}\|$ be the operator norm, $\|\bm{X}\|_{*}$ be the nuclear norm,
and $\|\bm{X}\|_{F}$ be the Frobenius norm. We denote the $i$th largest and
the smallest singular value (and eigenvalue) of $\bm{X}$ by
$\sigma_{i}(\bm{X})$ and $\sigma_{\min}(\bm{X})$ (and $\lambda_{i}(\bm{X})$
and $\lambda_{\min}(\bm{X})$) respectively. For a non-negative function
$f(x)$, we write $f(x)\lesssim g(x)$ and $f(x)=O(g(x))$ if there exists a
positive constant $C_{0}$ such that $f(x)\leq C_{0}g(x)$ for all $x.$

##  2 Preliminaries

Recall the orthogonal group synchronization under Gaussian noise:

$\bm{A}_{ij}=\bm{G}_{i}\bm{G}_{j}^{\top}+\sigma\bm{W}_{ij}\in\hbox{\msbm{R}}^{d\times
d}$

where $\bm{G}_{i}\in\operatorname{O}(d)$ and $\bm{W}_{ij}$ is a $d\times d$
Gaussian random matrix. Let
$\bm{G}^{\top}=[\bm{G}^{\top}_{1},\cdots,\bm{G}^{\top}_{n}]\in\hbox{\msbm{R}}^{d\times
nd}$. Then we write the model into a more convenient block matrix form

$\bm{A}=\bm{G}\bm{G}^{\top}+\sigma\bm{W},\quad\bm{W}\in\hbox{\msbm{R}}^{nd\times
nd}$ (2.1)

where $\bm{W}=[\bm{W}_{ij}]_{1\leq i,j\leq n}$ is an $nd\times nd$ symmetric
Gaussian random matrix whose entries are i.i.d. standard normal. The task is
to recover the group elements from their pairwise measurements $\bm{A}_{ij}$.

Among many existing approaches for $\operatorname{O}(d)$ synchronization, one
popular approach is maximum likelihood estimation. Under Gaussian noise, the
likelihood function is equivalent to the least squares cost function:

$\min_{\bm{R}_{i}\in\operatorname{O}(d)}\sum_{i<j}\|\bm{R}_{i}\bm{R}_{j}^{\top}-\bm{A}_{ij}\|_{F}^{2}$

which is equivalent to

$\max_{\bm{R}_{i}\in\operatorname{O}(d)}\sum_{i<j}\langle\bm{R}_{i}\bm{R}_{j}^{\top},\bm{A}_{ij}\rangle.$
(2.2)

Directly maximizing (2.2) is not an easy task since (2.2) is a highly
nonconvex optimization program and potentially NP-hard. Convex relaxation is a
powerful approach to overcome the nonconvexity. Let
$\bm{R}\in\operatorname{O}(d)^{\otimes n}$ be a matrix of size $nd\times d$
whose $i$th block is $\bm{R}_{i}.$ Note that every element in
$\\{\bm{R}\bm{R}^{\top}:\bm{R}_{i}\in\operatorname{O}(d)\\}$ is positive
semidefinite and its diagonal block equals $\bm{I}_{d}.$ The convex relaxation
is obtained by “lifting” the feasible set:

$\max~{}\langle\bm{A},\bm{X}\rangle\quad\text{ such that }\quad\bm{X}\succeq
0,~{}\bm{X}_{ii}=\bm{I}_{d}.$ (2.3)

This semidefinite relaxation is a generalization of Goemans-Williamson
relaxation [29] for graph max-cut. The global maximizer of (2.3) can be
recovered by using a standard convex program solver [30, 41]. However, due to
the relaxation, it is likely that the solution to (2.3) does not match that to
(2.2). Therefore, one major theoretical question is the tightness, i.e., when
(2.2) and (2.3) share the same global maximizer. More generally, we are
interested in when (2.2) is solvable by an algorithm with polynomial time
complexity. The answer depends on the value of $\sigma$: for (2.2) with small
$\sigma$, it is more likely to obtain the optimal solution.

Our discussion focuses on answering two questions: (a) when is the SDP
relaxation tight? How does the tightness depend on $\sigma$?; (b) if the SDP
is tight, does there exist an efficient algorithm to recover the optimal
solution to (2.3) and (2.2)? Now we introduce the generalized power method:
the algorithm consists of a two-step procedure widely employed in nonconvex
optimization literature [14, 39, 60]: first we find a good initialization by
using spectral method and then show the global convergence of the generalized
power method. Before proceeding to the algorithm, we give a few useful
definitions.

######  Definition 2.1 (Generalized “phase”).

The generalized “phase” of a matrix $\bm{\Psi}\in\hbox{\msbm{R}}^{d\times d}$
is defined as

$\mathcal{P}(\bm{\Psi}):=\bm{U}\bm{V}^{\top},\quad\bm{\Psi}=\bm{U}\bm{\Sigma}\bm{V}^{\top},$

where $\bm{U}\bm{\Sigma}\bm{V}^{\top}$ is the SVD of $\bm{\Psi}.$ In
particular, if $\bm{\Psi}\in\hbox{\msbm{R}}^{d\times d}$ is invertible, then

$\mathcal{P}(\bm{\Psi}):=\bm{\Psi}(\bm{\Psi}^{\top}\bm{\Psi})^{-\frac{1}{2}}=(\bm{\Psi}\bm{\Psi}^{\top})^{-\frac{1}{2}}\bm{\Psi}.$

For a block matrix
$\bm{X}^{\top}=[\bm{X}_{1}^{\top},\cdots,\bm{X}_{n}^{\top}]\in\hbox{\msbm{R}}^{d\times
nd}$ with $\bm{X}_{i}\in\hbox{\msbm{R}}^{d\times d}$, we define

$\mathcal{P}_{n}(\bm{X}):=\begin{bmatrix}\mathcal{P}(\bm{X}_{1})\\\ \vdots\\\
\mathcal{P}(\bm{X}_{n})\end{bmatrix}\in\hbox{\msbm{R}}^{nd\times d}.$

The operator $\mathcal{P}_{n}$ is essentially the projection operator which
maps a matrix of $\hbox{\msbm{R}}^{nd\times d}$ to
$\operatorname{O}(d)^{\otimes n}$ since for each block $\bm{X}_{i}$,
$\mathcal{P}(\bm{X}_{i})$ is the orthogonal matrix closest to $\bm{X}_{i}$:

$\mathcal{P}(\bm{X}_{i}):=\operatorname{argmin}_{\bm{Q}\in\operatorname{O}(d)}\|\bm{Q}-\bm{X}_{i}\|_{F}^{2}.$

In our discussion, we also need to introduce a new distance function between
two matrices $\bm{X}$ and $\bm{Y}$ in $\operatorname{O}(d)^{\otimes n}$.
Remember that for orthogonal group synchronization, the solution is equivalent
up to a global group action, i.e., $\bm{X}$ and $\bm{X}\bm{Q}$ are equivalent
for any $\bm{Q}\in\operatorname{O}(d)$. This fact needs to be taken into
consideration and we define the following distance function for matrices in
$\hbox{\msbm{R}}^{nd\times d}$:

$d_{F}(\bm{Y},\bm{X})=\min_{\bm{Q}\in\operatorname{O}(d)}\|\bm{Y}-\bm{X}\bm{Q}\|_{F},$
(2.4)

where $\bm{Q}=\mathcal{P}(\bm{X}^{\top}\bm{Y})$ minimizes
$\|\bm{Y}-\bm{X}\bm{Q}\|_{F}.$ This distance function satisfies triangle
inequality. For three arbitrary $nd\times d$ matrices $\bm{X},\bm{Y},$ and
$\bm{Z}$, we have

$\displaystyle d_{F}(\bm{X},\bm{Z})$
$\displaystyle=\|\bm{X}-\bm{Z}\bm{Q}_{ZX}\|_{F}\leq\|\bm{X}-\bm{Z}\bm{Q}_{ZY}\bm{Q}_{YX}\|_{F}$
$\displaystyle\leq\|\bm{X}-\bm{Y}\bm{Q}_{YX}\|_{F}+\|\bm{Y}\bm{Q}_{YX}-\bm{Z}\bm{Q}_{ZY}\bm{Q}_{YX}\|_{F}$
$\displaystyle\leq d_{F}(\bm{X},\bm{Y})+d_{F}(\bm{Y},\bm{Z})$

where $\bm{Q}_{ZX}=\mathcal{P}(\bm{Z}^{\top}\bm{X})$,
$\bm{Q}_{ZY}=\mathcal{P}(\bm{Z}^{\top}\bm{Y})$, and
$\bm{Q}_{YX}=\mathcal{P}(\bm{Y}^{\top}\bm{X})$ all belong to
$\operatorname{O}(d).$

Now we are ready to present the algorithm, which has been proposed in [38,
60].

Algorithm 1 Generalized power methods for orthogonal group synchronization

1:Compute the top $d$ eigenvectors $\bm{\Phi}\in\hbox{\msbm{R}}^{nd\times d}$
of $\bm{A}$ with $\bm{\Phi}^{\top}\bm{\Phi}=n\bm{I}_{d}.$

2:Compute $\mathcal{P}(\bm{\Phi}_{i})$ for all $1\leq i\leq n$ where
$\bm{\Phi}_{i}$ is the $i$th block of $\bm{\Phi}$.

3:Initialize $\bm{S}^{0}=\mathcal{P}_{n}(\bm{\Phi}).$

4:$\bm{S}^{t+1}=\mathcal{P}_{n}(\bm{A}\bm{S}^{t})$, $t=0,1,\cdots$

5:Stop when the iteration stabilizes.

The algorithm begins with a spectral initialization which first computes the
top $d$ eigenvectors of $\bm{A}$ and then projects them onto
$\operatorname{O}(d)^{\otimes n}.$ After that, each step of the algorithm is
essentially one step of power iteration followed by projection. In order to
better understand this algorithm, we first take a closer look at this
algorithm and its possible fixed point. Let $\bm{S}_{i}^{t}$ be the $i$th
block of $\bm{S}^{t}$ and the update rule for the $i$th block is

$\bm{S}_{i}^{t+1}=\mathcal{P}\left(\sum_{j=1}^{n}\bm{A}_{ij}\bm{S}_{j}^{t}\right)=\bm{U}_{ii}^{t}(\bm{V}_{i}^{t})^{\top},\quad
1\leq i\leq n,$

where $\bm{U}_{i}^{t}$ and $\bm{V}_{i}^{t}$ are the left and right singular
vectors of $\sum_{j=1}^{n}\bm{A}_{ij}\bm{S}_{j}^{t}$. Note that

$\sum_{j=1}^{n}\bm{A}_{ij}\bm{S}_{j}^{t}=\bm{U}_{i}^{t}\bm{\Sigma}_{i}^{t}(\bm{V}_{i}^{t})^{\top}=\bm{U}_{i}^{t}\bm{\Sigma}_{i}^{t}(\bm{U}_{i}^{t})^{\top}\cdot\bm{U}_{i}^{t}(\bm{V}_{i}^{t})^{\top}=\bm{\Lambda}_{ii}^{t}\bm{S}_{i}^{t+1}$
(2.5)

where
$\bm{\Lambda}_{ii}^{t}:=\bm{U}_{i}^{t}\bm{\Sigma}_{i}^{t}(\bm{U}_{i}^{t})^{\top}\succeq
0.$ A more compact form of the update rule is

$\bm{A}\bm{S}^{t}=\bm{\Lambda}^{t}\bm{S}^{t+1}$

where
$\bm{\Lambda}^{t}=\operatorname{blkdiag}(\bm{\Lambda}_{11}^{t},\cdots,\bm{\Lambda}_{nn}^{t})$
is a block-diagonal matrix whose blocks consist of
$\\{\bm{\Lambda}_{ii}^{t}\\}_{i=1}^{n}.$

Suppose $\\{\bm{S}^{t}\\}_{t\geq 0}$ finally converges under
$d_{F}(\cdot,\cdot)$, the limiting point $\bm{S}^{\infty}$ is  _likely_ to
satisfy (we will justify why it holds later):

$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$ (2.6)

where
$\bm{\Lambda}=\operatorname{blkdiag}(\bm{\Lambda}_{11},\cdots,\bm{\Lambda}_{nn})\in\hbox{\msbm{R}}^{nd\times
nd}\succeq 0$. In fact, (2.6) arises again when we want to characterize the
global optimality of $\bm{S}^{\infty}(\bm{S}^{\infty})^{\top}$ in (2.3): if
$\bm{S}^{\infty}$ satisfies (2.6) and $\bm{\Lambda}-\bm{A}\succeq 0$, then
$\bm{S}^{\infty}(\bm{S}^{\infty})^{\top}$ is the global maximizer to (2.3),
which follows from the duality theory in convex optimization.

##  3 Main theorems

The first result improves the state-of-the-art bound for the tightness of SDP
relaxation to solve orthogonal group synchronization.

######  Theorem 3.1.

Consider orthogonal group synchronization problem (2.1) under Gaussian noise
and its convex relaxation (2.3). The SDP relaxation is tight, i.e., the
solution to (2.3) is rank-$d$ and equal to the maximum likelihood estimator
(2.2), if

$\sigma<\frac{c_{0}\sqrt{n}}{\sqrt{d}(\sqrt{d}+\sqrt{\log n})}$ (3.1)

with high probability for a small constant $c_{0}.$ Moreover, its solution is
unique and satisfies

$\min_{\bm{Q}\in\operatorname{O}(d)}\max_{1\leq i\leq
n}\|\widehat{\bm{G}}_{i}-\bm{G}_{i}\bm{Q}\|_{F}\lesssim\sigma\sqrt{n^{-1}d}(\sqrt{d}+\sqrt{\log
n})$

where $\widehat{\bm{G}}_{i}$ is the MLE and the solution to (2.3).

Here we have several remarks on Theorem 3.1. The maximum likelihood estimator
$\widehat{\bm{G}}$ does not have an explicit form and is not equal to the
ground truth $\bm{G}$. The best known bound on $\sigma$ for the tightness
before this result is $\sigma<c_{1}n^{1/4}/d^{3/4}$ for some small constant
$c_{1}$ in [35]. The bound (3.1) greatly improves the scaling on $n$ from
$n^{1/4}$ to a near-optimal dependence $\sqrt{n}$. Note that in random matrix
theory, it has been extensively studied when the top eigenvectors of $\bm{A}$
are correlated with the planted signals (low-rank matrix), see e.g. [7, 45].
In fact, once the noise level $\sigma$ reaches $\sigma>\sqrt{n/d}$, spectral
methods fail to provide useful information about the planted signal. Moreover,
spectral methods (PCA) achieve the optimal detection threshold under certain
natural priors for the spike. Therefore, the optimal bound on $\sigma$ should
scale like $\sqrt{n/d}$ up to a logarithmic factor and our bound differs from
this threshold by a factor of $\sqrt{d}$.

Another relevant approach to solve $\operatorname{O}(d)$ synchronization uses
spectral relaxation. Note that [34] implies that spectral relaxation provides
a spectral estimator $\widehat{\bm{G}}_{i,\operatorname{spec}}$ of
$\bm{G}_{i}$ which satisfies
$\min_{\bm{Q}\in\operatorname{O}(d)}\max\|\widehat{\bm{G}}_{i,\operatorname{spec}}-\bm{G}_{i}\bm{Q}\|\lesssim\sigma\sqrt{n^{-1}d}$
with a near-optimal bound on $\sigma$, i.e.,
$\sigma\lesssim\sqrt{n}/(\sqrt{d}+\sqrt{\log n}).$ However, the solution
$\widehat{\bm{G}}_{\operatorname{spec}}$ given by spectral relaxation is often
not equal to the MLE.

The second result concerns establishing an efficient algorithm with guaranteed
global convergence. Despite that spectral method fails to directly give the
MLE, it can be used as an initialization since
$\bm{S}^{0}=\widehat{\bm{G}}_{\operatorname{spec}}$ is very close to $\bm{G}$
even in block-wise error bound. Using this idea, we have the following theorem
which provides a convergence analysis of the generalized power method.

######  Theorem 3.2.

Consider orthogonal group synchronization problem (2.1) under Gaussian noise.
Suppose

$\sigma<\frac{c_{0}\sqrt{n}}{\sqrt{d}(\sqrt{d}+\sqrt{\log n})}$

for some small constant $c_{0}$, then the sequence
$\\{\bm{S}^{t}\\}_{t=0}^{\infty}$ from generalized power method converges
linearly to the global maximizer of the SDP relaxation with probability at
least $1-O(n^{-2})$. In other words, because of the tightness of SDP
relaxation, the limiting point $\bm{S}^{\infty}$ equals the maximum likelihood
estimator, i.e., the global maximizer to (2.2).

Theorem 3.2 is a generalization of the convergence result on phase
synchronization [60]. As discussed before, the dependence on $n$ is near-
optimal but the scaling of $d$ remains suboptimal by $\sqrt{d}$. In fact, the
suboptimal dependence of performance bound on the rank $d$ is a general issue
in the convergence analysis of nonconvex approach in many signal processing
and machine learning problems [17, 33]. It is an open problem to have an exact
recovery guarantee of the MLE via convex/nonconvex approach provided that

$\sigma=O\left(\sqrt{\frac{n}{d}}\right)$

holds modulo a log-factor. Resolving this open problem will lead to a
substantial improvement of performance guarantees in many examples of low-rank
matrix recovery via nonconvex approach. For $\operatorname{O}(d)$
synchronization, one possible solution is to derive a performance bound in
terms of
$d_{2}(\bm{X},\bm{Y}):=\min_{\bm{Q}\in\operatorname{O}(d)}\|\bm{Y}-\bm{X}\bm{Q}\|$,
which is significantly more challenging since the norm is no longer equipped
with an inner product. This will create technical difficulties in proving that
the Algorithm 1 is actually a contraction mapping within a basin of
attraction, more precisely discussed in Lemma 4.8 and 4.9.

##  4 Proofs

This section is devoted to the proof of the main theorems. Our proof will
follow a similar route in [60]. However, since $\operatorname{O}(d)$ is non-
commutative, many technical parts need different treatments. Also we will use
some supporting results in [35], especially regarding spectral initialization,
without giving the detailed proofs. To make this manuscript more self-
contained, the proof idea of each cited result will be discussed. Note that
orthogonal transform will not change the distribution of Gaussian random
matrix. It suffices to consider

$\bm{A}=\bm{Z}\bm{Z}^{\top}+\sigma\bm{W}\in\hbox{\msbm{R}}^{nd\times nd}$

after performing a simple change of variable to (2.1) where
$\bm{Z}^{\top}:=[\bm{I}_{d},\cdots,\bm{I}_{d}]\in\hbox{\msbm{R}}^{d\times
nd}.$

Our main goal is to show the tightness of the SDP relaxation (2.3), i.e., the
global maximizer to the SDP is of rank $d$, which corresponds to the global
maximizer to (2.2). Similar to phase synchronization, the global maximizer to
(2.2) does not have an explicit form ($\bm{Z}$ is not the global maximizer),
which makes it harder to characterize the global maximum. To resolve this
issue, [60] developed a smart way of characterizing the global maximizer by
treating it as the limiting point of the sequences generated by the
generalized power method. We will show that the sequence
$\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ always stays in the intersection of
the following two sets in Section 4.1 and 4.2:

$\displaystyle{\cal N}_{\epsilon}$
$\displaystyle:=\left\\{\bm{S}\in\operatorname{O}(d)^{\otimes
n}:\min_{\bm{Q}\in\operatorname{O}(d)}\|\bm{S}-\bm{Z}\bm{Q}\|_{F}\leq\epsilon\sqrt{nd}\right\\},$
$\displaystyle{\cal N}_{\xi,\infty}$
$\displaystyle:=\left\\{\bm{S}\in\operatorname{O}(d)^{\otimes
n}:\left\|\bm{W}_{i}^{\top}\bm{S}\right\|_{F}\leq\xi\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n}),~{}1\leq i\leq n\right\\},$

where $\xi>0$ is a constant to be determined later, $\epsilon$ is another
constant which satisfies

$\epsilon\leq\frac{1}{32\sqrt{d}}\Longrightarrow\epsilon^{2}d\leq\frac{1}{1024}$

and $\bm{W}_{i}\in\hbox{\msbm{R}}^{nd\times d}$ is the $i$th block column of
$\bm{W}=[\bm{W}_{1},\cdots,\bm{W}_{n}].$

Note that both $\mathcal{N}_{\epsilon}$ and $\mathcal{N}_{\xi,\infty}$ are
closed and compact sets in Euclidean space. Then if we can prove that
$\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ converges to a limiting point, it also
stays in $\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$.

######  Theorem 4.1.

Suppose the generalized power iteration converges to a limiting point
$\bm{S}^{\infty}$ which satisfies
$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$ where $\bm{\Lambda}\succeq
0$ is a block-diagonal matrix. Moreover, if $\bm{S}^{\infty}$ is located in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\infty}$, then
$\bm{X}^{\infty}=\bm{S}^{\infty}(\bm{S}^{\infty})^{\top}$ is the unique global
maximizer to (2.3) if

$\sigma<\frac{1-3\epsilon^{2}d/2}{\xi+3}\cdot\frac{\sqrt{n}}{\sqrt{d}(\sqrt{d}+4\sqrt{\log
n})}.$ (4.1)

Therefore, our task becomes (a): to show that the sequence
$\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ is located in the
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ and converges to a
limiting point; (b): to justify why the limiting point $\bm{S}^{\infty}$ is
the global maximizer.

Now we focus on answering the second question by first providing a certificate
of global optimality. Then we will show that if the limiting point is a fixed
point of the power iteration and is located in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$, then it must satisfy the
global optimality condition. Finally, we will verify the assumptions in
Theorem 4.1 hold in Section 4.3.

######  Theorem 4.2.

The matrix $\bm{X}=\bm{S}\bm{S}^{\top}$ with
$\bm{S}\in\operatorname{O}(d)^{\otimes n}$ is a global optimal solution to
(2.3) if there exists a block-diagonal matrix
$\bm{\Lambda}\in\hbox{\msbm{R}}^{nd\times nd}$ such that

$\bm{A}\bm{S}=\bm{\Lambda}\bm{S},\quad\bm{\Lambda}-\bm{A}\succeq 0.$ (4.2)

Moreover, if $\bm{\Lambda}-\bm{A}$ is of rank $(n-1)d$, then $\bm{X}$ is the
unique global maximizer.

This optimality condition can be found in several places including [35,
Proposition 5.1] and [48, Theorem 7]. The derivation of Theorem 4.2 follows
from the standard routine of duality theory in convex optimization. The first
equation in (4.2) seems relatively simple to achieve as we have seen that the
fixed point of power iteration naturally satisfies this condition. The only
difficulty is to take care of the solution ambiguity induced by a global group
action. The more challenging part arises from achieving
$\bm{\Lambda}-\bm{A}\succeq 0$ which reduces to finding a tight lower bound
for the smallest eigenvalue of $\bm{\Lambda}.$ We will prove that a tight
lower bound of $\lambda_{\min}(\bm{\Lambda})$ can be obtained if the limiting
point is inside $\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}.$ Before
proceeding to the proof of Theorem 4.1, we introduce two useful supporting
facts.

######  Lemma 4.3.

Suppose $\bm{W}\in\hbox{\msbm{R}}^{nd\times nd}$ is a symmetric Gaussian
random matrix, then

$\|\bm{W}\|\leq 3\sqrt{nd}$ (4.3)

with probability at least $1-\exp(-nd/2).$

This is a quite standard result in random matrix theory, which can be found in
many places [5, 60, 55].

######  Lemma 4.4.

For any $\bm{S}\in\mathcal{N}_{\epsilon}$, all the singular values of
$\bm{Z}^{\top}\bm{S}$ satisfy

$\left(1-\frac{\epsilon^{2}d}{2}\right)n\leq\sigma_{i}(\bm{Z}^{\top}\bm{S})\leq
n,\quad 1\leq i\leq d.$

###### Proof: .

Note that

$\displaystyle d_{F}^{2}(\bm{S},\bm{Z})$
$\displaystyle=\|\bm{S}-\bm{Z}\bm{Q}\|_{F}^{2}$
$\displaystyle=\|\bm{S}\|_{F}^{2}+\|\bm{Z}\|_{F}^{2}-2\langle\bm{Z}^{\top}\bm{S},\bm{Q}\rangle$
$\displaystyle=2(nd-\|\bm{Z}^{\top}\bm{S}\|_{*})\leq\epsilon^{2}nd$

where $\bm{Q}=\mathcal{P}(\bm{Z}^{\top}\bm{S})$. Since
$\|\bm{Z}^{\top}\bm{S}\|\leq n$ implies
$0\leq\sigma_{i}(\bm{Z}^{\top}\bm{S})\leq n$, $1\leq i\leq d$ , we have

$\frac{\epsilon^{2}nd}{2}\geq\sum_{i=1}^{d}(n-\sigma_{i}(\bm{Z}^{\top}\bm{S}))\Longrightarrow\sigma_{\min}\left(\bm{Z}^{\top}\bm{S}\right)\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n.$

∎

This bound is actually quite conservative due to the extra $d$ factor in the
lower bound. It is also the reason why we obtain a sub-optimal scaling on
$\sigma$ in the main theorem. Now we are ready to prove Theorem 4.1.

###### Proof of Theorem 4.1.

Suppose the fixed point $\bm{S}^{\infty}$ satisfies
$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$ for some positive
semidefinite block-diagonal matrix
$\bm{\Lambda}=\operatorname{blkdiag}(\bm{\Lambda}_{11},\cdots,\bm{\Lambda}_{nn})\in\hbox{\msbm{R}}^{nd\times
nd}$. Then we have

$\bm{\Lambda}_{ii}=[\bm{A}\bm{S}^{\infty}]_{i}(\bm{S}_{i}^{\infty})^{\top}\succeq
0,\quad 1\leq i\leq n.$

We first obtain a lower bound of the smallest eigenvalue of
$\bm{\Lambda}_{ii}$ as follows:

$\displaystyle\lambda_{\min}(\bm{\Lambda}_{ii})$
$\displaystyle=\sigma_{\min}(\bm{\Lambda}_{ii})=\sigma_{\min}\left(\sum_{j=1}^{n}\bm{A}_{ij}\bm{S}_{j}^{\infty}\right)$
$\displaystyle=\sigma_{\min}\left(\bm{Z}^{\top}\bm{S}^{\infty}+\sigma\sum_{j=1}^{n}\bm{W}_{ij}\bm{S}_{j}^{\infty}\right)$
(Weyl’s theorem)
$\displaystyle\geq\sigma_{\min}\left(\bm{Z}^{\top}\bm{S}^{\infty}\right)-\sigma\left\|\bm{W}_{i}^{\top}\bm{S}^{\infty}\right\|_{F}$
$\displaystyle\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n-\sigma\xi\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$

where $\bm{\Lambda}_{ii}\succeq 0$ is symmetric for all $1\leq i\leq n$ and
$\bm{S}^{\infty}\in\mathcal{N}_{\epsilon}$. Note that
$(\bm{\Lambda}-\bm{A})\bm{S}^{\infty}=0$ means at least $d$ eigenvalues are 0.
To show that $\bm{\Lambda}-\bm{A}\succeq 0$ with rank $(n-1)d$, it suffices to
have $\lambda_{d+1}(\bm{\Lambda}-\bm{A})>0$, i.e.,
$\bm{u}^{\top}(\bm{\Lambda}-\bm{A})\bm{u}>0$ for any nonzero unit vector
$\bm{u}\in\hbox{\msbm{R}}^{nd}$ such that $\bm{u}^{\top}\bm{S}^{\infty}=0$. It
holds that

$\displaystyle\bm{u}^{\top}\bm{A}\bm{u}$
$\displaystyle=\bm{u}^{\top}\bm{Z}\bm{Z}^{\top}\bm{u}+\sigma\bm{u}^{\top}\bm{W}\bm{u}$
$\displaystyle=\bm{u}^{\top}(\bm{S}^{\infty}-\bm{Z}\bm{Q})(\bm{S}^{\infty}-\bm{Z}\bm{Q})^{\top}\bm{u}+\sigma\bm{u}^{\top}\bm{W}\bm{u}$
$\displaystyle\leq\|\bm{S}^{\infty}-\bm{Z}\bm{Q}\|^{2}+\sigma\|\bm{W}\|$
$\displaystyle\leq\epsilon^{2}nd+3\sigma\sqrt{nd}$

where $\|\bm{W}\|\leq 3\sqrt{nd}$,
$\|\bm{S}^{\infty}-\bm{Z}\bm{Q}\|\leq\|\bm{S}^{\infty}-\bm{Z}\bm{Q}\|_{F}\leq\epsilon\sqrt{nd}$
and $\bm{Q}=\mathcal{P}(\bm{Z}^{\top}\bm{S}^{\infty})$. Thus if (4.1) holds,
we have

$\displaystyle\bm{u}^{\top}(\bm{\Lambda}-\bm{A})\bm{u}$
$\displaystyle\geq\min_{1\leq i\leq
n}\lambda_{\min}(\bm{\Lambda}_{ii})-\max_{\bm{u}:\bm{u}^{\top}\bm{S}^{\infty}=0,\|\bm{u}\|=1}\bm{u}^{\top}\bm{A}\bm{u}$
$\displaystyle\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n-\sigma\xi\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})-\left(\epsilon^{2}nd+3\sigma\sqrt{nd}\right)$
$\displaystyle\geq\left(1-\frac{3\epsilon^{2}d}{2}\right)n-\sigma(\xi+3)\sqrt{nd}\left(\sqrt{d}+4\sqrt{\log
n}\right)>0.$

Then we have $\bm{\Lambda}-\bm{A}\succeq 0$ with the $(d+1)$th smallest
eigenvalue strictly positive and bottom $d$ eigenvalues equal to zero. ∎

Roadmap: Now we provide an overview of the next few sections. To prove the
main results, Theorem 4.1 indicates that we need to show the iterates
$\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ stay in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ for all $\ell$ and
moreover, it will converge to a limiting point which satisfies
$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$ for some positive
semidefinite block-diagonal matrix $\bm{\Lambda}\in\hbox{\msbm{R}}^{nd\times
nd}.$ We will justify why $\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ stay in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ in Section 4.1 and 4.2.
The existence and convergence of limiting point, and its global optimality
will be given in Section 4.3. In Section 4.4, we will prove why spectral
initialization provides a good starting point within
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$.

###  4.1 Contraction mapping on
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$

The tricky part is that we do not know the explicit form of the MLE which is
not necessarily equal to $\bm{Z}$. In order to show the convergence of
iterates to the MLE, we start with proving the power iteration essentially
gives a contraction mapping on
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$. Define

${\cal L}:=n^{-1}\bm{A},\quad{\cal
L}\bm{S}:=\frac{1}{n}\bm{A}\bm{S}=\frac{1}{n}(\bm{Z}\bm{Z}^{\top}+\sigma\bm{W})\bm{S}\in\hbox{\msbm{R}}^{nd\times
d}$ (4.4)

Then the power iteration is equivalent to:

$\bm{S}^{t+1}=\mathcal{P}_{n}({\cal L}\bm{S}^{t}).$

Now, we will prove that $\mathcal{P}_{n}\circ{\cal L}$ is a contraction
mapping, by investigating ${\cal L}$ and $\mathcal{P}_{n}$ individually.
Ideally, if we manage to prove that $\mathcal{P}_{n}\circ{\cal L}$ maps
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ to itself, then the proof
is done which follows from the contraction mapping theorem. However, it
remains unclear how to prove this statement. Instead, we will show that the
iterates $\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ from the projected power
method stay in the region of contraction. We will address this issue in the
next subsection.

######  Lemma 4.5.

Suppose $\bm{X}$ and $\bm{Y}\in\operatorname{O}(d)^{\otimes n}$ with
$d_{F}(\bm{X},\bm{Z})\leq\epsilon\sqrt{nd}$ and
$d_{F}(\bm{Y},\bm{Z})\leq\epsilon\sqrt{nd}$, it holds

$d_{F}({\cal L}\bm{X},{\cal L}\bm{Y})\leq\rho^{\prime}\cdot
d_{F}(\bm{X},\bm{Y}).$

where

$\rho^{\prime}=2\epsilon\sqrt{d}+3\sigma\sqrt{\frac{d}{n}}.$

Under the assumption

$\epsilon\sqrt{d}<\frac{1}{32},\quad\sigma\leq\frac{1}{72}\sqrt{\frac{n}{d}},$

then

$\rho^{\prime}\leq\frac{1}{9}.$

We give the proof of this lemma at the end of this subsection. Next, we turn
our focus to $\mathcal{P}_{n}(\cdot)$. We first introduce the famous Davis-
Kahan theorem.

######  Theorem 4.6 (Davis-Kahan theorem [23]).

Suppose $\bm{\Psi}$ and $\bm{\Psi}_{E}$ are the top $d$ normalized
eigenvectors of $\bm{X}$ and $\bm{X}_{\bm{E}}=\bm{X}+\bm{E}$ respectively,
then

$\min_{\bm{Q}\in\operatorname{O}(d)}\|\bm{\Psi}_{\bm{E}}-\bm{\Psi}\bm{Q}\|\leq\sqrt{2}\|(\bm{I}-\bm{\Psi}\bm{\Psi}^{\top})\bm{\Psi}_{E}\|\leq\frac{\sqrt{2}\|\bm{E}\bm{\Psi}_{E}\|}{\delta}$

where $\bm{\Psi}^{\top}\bm{\Psi}=\bm{\Psi}_{E}^{\top}\bm{\Psi}_{E}=\bm{I}_{d}$
and $\delta=\lambda_{d}(\bm{X})-\lambda_{d+1}(\bm{X}_{\bm{E}})>0$ is the
spectral gap. The bound also holds when replacing $\|\cdot\|$ by
$\|\cdot\|_{F}$.

In particular, in order to obtain a meaningful bound, we would hope to have
$\delta>\|\bm{E}\|$ such that
$\|(\bm{I}-\bm{\Psi}\bm{\Psi}^{\top})\bm{\Psi}_{\bm{E}}\|<1.$

By Theorem 4.6, we can establish a useful result about the projection operator
$\mathcal{P}(\cdot).$

######  Lemma 4.7.

For two invertible matrices $\bm{X}\in\hbox{\msbm{R}}^{d\times d}$ and
$\bm{Y}\in\hbox{\msbm{R}}^{d\times d}$, we have

$\displaystyle\|\mathcal{P}(\bm{X})-\mathcal{P}(\bm{Y})\|_{F}$
$\displaystyle\leq\frac{4\|\bm{X}-\bm{Y}\|_{F}}{\sigma_{\min}(\bm{X})+\sigma_{\min}(\bm{Y})}.$

If only $\sigma_{\min}(\bm{X})$ (or $\sigma_{\min}(\bm{Y})$) is known, then we
can use

$\|\mathcal{P}(\bm{X})-\mathcal{P}(\bm{Y})\|_{F}\leq
4\sigma^{-1}_{\min}(\bm{X})\|\bm{X}-\bm{Y}\|_{F}.$

We defer the proof of Lemma 4.7 to the end of this section. Now it seems
combining Lemma 4.5 with 4.7 justifies the contraction of
$\mathcal{P}_{n}\circ{\cal L}$. The only missing piece is to ensure that each
block $[{\cal L}\bm{X}]_{i}$ has a lower bound on its smallest singular value
so that we can apply Lemma 4.7.

######  Lemma 4.8.

Suppose $\bm{X}\in{\cal N}_{\epsilon}\cap{\cal N}_{\xi,\infty}$, then

$\sigma_{\min}\left([{\cal L}\bm{X}]_{i}\right)\geq 1-\epsilon^{2}d$

provided that

$\sigma\leq\frac{\epsilon^{2}d}{2\xi}\cdot\frac{\sqrt{n}}{\sqrt{d}(\sqrt{d}+\sqrt{\log
n})}.$

One can easily realize that the dependence of $\sigma$ on $d$ is sub-optimal
by a factor of $\sqrt{d}.$ This is where the bottleneck is.

######  Lemma 4.9 (Contraction mapping).

Suppose $\bm{X}$ and $\bm{Y}$ are in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$, then we have

$\displaystyle d_{F}(\mathcal{P}_{n}({\cal L}\bm{X}),\mathcal{P}_{n}({\cal
L}\bm{Y}))$ $\displaystyle\leq\frac{4}{1-\epsilon^{2}d}\cdot d_{F}({\cal
L}\bm{X},{\cal L}\bm{Y})$
$\displaystyle\leq\frac{4}{1-\epsilon^{2}d}\left(2\epsilon\sqrt{d}+3\sigma\sqrt{\frac{d}{n}}\right)\cdot
d_{F}(\bm{X},\bm{Y}).$

We define

$\rho=\frac{4}{1-\epsilon^{2}d}\left(2\epsilon\sqrt{d}+3\sigma\sqrt{\frac{d}{n}}\right).$

Under

$\epsilon\sqrt{d}<\frac{1}{32},\quad\sigma\leq\min\left\\{\frac{1}{72}\sqrt{\frac{n}{d}},~{}\frac{\epsilon^{2}d}{2\xi}\cdot\frac{\sqrt{n}}{\sqrt{d}(\sqrt{d}+4\sqrt{\log
n})}\right\\},$

then $\rho<1/2.$

###### Proof of Lemma 4.8 and 4.9.

Over $\bm{X}\in\mathcal{N}={\cal N}_{\epsilon}\cap{\cal N}_{\xi,\infty}$, we
have ${\cal L}\bm{X}$ and its $i$th block as

${\cal
L}\bm{X}=\frac{1}{n}(\bm{Z}\bm{Z}^{\top}+\sigma\bm{W})\bm{X},\quad[{\cal
L}\bm{X}]_{i}=\frac{1}{n}\bm{Z}^{\top}\bm{X}+\frac{\sigma}{n}\bm{W}_{i}^{\top}\bm{X}.$

Note that if $d_{F}(\bm{X},\bm{Z})\leq\epsilon\sqrt{nd}$,
$\sigma_{\min}(\bm{Z}^{\top}\bm{X})\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n$
holds. As a result,

$\displaystyle\sigma_{\min}([{\cal L}\bm{X}]_{i})$
$\displaystyle\geq\frac{1}{n}\sigma_{\min}(\bm{Z}^{\top}\bm{X})-\frac{\sigma}{n}\left\|\bm{W}_{i}^{\top}\bm{X}\right\|$
$\displaystyle=\left(1-\frac{\epsilon^{2}d}{2}\right)-\frac{\sigma}{n}\cdot\xi\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$ $\displaystyle\geq 1-\epsilon^{2}d$

when

$\sigma\leq\frac{\epsilon^{2}\sqrt{nd}}{2\xi(\sqrt{d}+4\sqrt{\log n})}.$

Similarly, we have $\sigma_{\min}([{\cal L}\bm{Y}]_{i})\geq 1-\epsilon^{2}d.$

Now we are ready to obtain the contraction property of
$\mathcal{P}_{n}\circ{\cal L}$ on
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$. We pick $\bm{Q}$ as the
orthogonal matrix $\bm{Q}$ which minimizes

$d_{F}({\cal L}\bm{X},{\cal
L}\bm{Y})=\min_{\bm{Q}\in\operatorname{O}(d)}\|{\cal L}\bm{X}-{\cal
L}\bm{Y}\bm{Q}\|_{F}.$

Then

$\displaystyle d_{F}(\mathcal{P}_{n}({\cal L}\bm{X}),\mathcal{P}_{n}({\cal
L}\bm{Y}))$ $\displaystyle\leq\|\mathcal{P}_{n}({\cal
L}\bm{X})-\mathcal{P}_{n}({\cal L}\bm{Y}\bm{Q})\|_{F}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\|\mathcal{P}([{\cal
L}\bm{X}]_{i})-\mathcal{P}([{\cal L}\bm{Y}\bm{Q}]_{i})\|_{F}^{2}}$ (Lemma 4.7)
$\displaystyle\leq\frac{4}{1-\epsilon^{2}d}\sqrt{\sum_{i=1}^{n}\|[{\cal
L}\bm{X}]_{i}-[{\cal L}\bm{Y}\bm{Q}]_{i})\|_{F}^{2}}$
$\displaystyle=\frac{4}{1-\epsilon^{2}d}\|{\cal L}\bm{X}-{\cal
L}\bm{Y}\bm{Q}\|_{F}$ $\displaystyle=\frac{4}{1-\epsilon^{2}d}d_{F}({\cal
L}\bm{X},{\cal L}\bm{Y})$ (Lemma 4.5)
$\displaystyle\leq\frac{4}{1-\epsilon^{2}d}\left(2\epsilon\sqrt{d}+3\sigma\sqrt{\frac{d}{n}}\right)d_{F}(\bm{X},\bm{Y}).$

∎

###### Proof of Lemma 4.5.

Under $d_{F}(\bm{X},\bm{Z})\leq\epsilon\sqrt{nd}$ and
$d_{F}(\bm{Y},\bm{Z})\leq\epsilon\sqrt{nd}$, it holds that

$\sigma_{\min}(\bm{X}^{\top}\bm{Z})\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n,\quad\sigma_{\min}(\bm{Y}^{\top}\bm{Z})\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n.$

Also by triangle inequality, we have

$d_{F}(\bm{X},\bm{Y})\leq
2\epsilon\sqrt{nd},\quad\sigma_{\min}(\bm{X}^{\top}\bm{Y})\geq\left(1-2\epsilon^{2}d\right)n.$

Now we set $\bm{Q}=\mathcal{P}(\bm{Y}^{\top}\bm{X})$ which minimizes
$\|\bm{X}-\bm{Y}\bm{R}\|_{F}$ over $\bm{R}\in\operatorname{O}(d)$.

$\displaystyle d_{F}({\cal L}\bm{X},{\cal L}\bm{Y})$
$\displaystyle\leq\frac{1}{n}\|\bm{A}(\bm{X}-\bm{Y}\bm{Q})\|_{F}$
$\displaystyle\leq\frac{1}{n}\left(\left\|\bm{Z}\bm{Z}^{\top}(\bm{X}-\bm{Y}\bm{Q})\right\|_{F}+\sigma\|\bm{W}(\bm{X}-\bm{Y}\bm{Q})\|_{F}\right)$
$\displaystyle\leq\frac{1}{\sqrt{n}}\|\bm{Z}^{\top}(\bm{X}-\bm{Y}\bm{Q})\|_{F}+3\sigma\sqrt{\frac{d}{n}}\cdot
d_{F}(\bm{X},\bm{Y})$

where $\bm{A}=\bm{Z}\bm{Z}^{\top}+\sigma\bm{W}$, $\|\bm{Z}\|=\sqrt{n}$, and
$\|\bm{W}\|\leq 3\sqrt{nd}.$

The more tricky part is estimation of
$\|\bm{Z}^{\top}(\bm{X}-\bm{Y}\bm{Q})\|_{F}.$ Let
$\bm{Q}=\mathcal{P}(\bm{Y}^{\top}\bm{X})$,
$\bm{Q}_{\bm{X}}=\mathcal{P}(\bm{Z}^{\top}\bm{X})$, and
$\bm{Q}_{\bm{Y}}=\mathcal{P}(\bm{Z}^{\top}\bm{Y})$. Then

$\displaystyle\|\bm{Z}^{\top}(\bm{X}-\bm{Y}\bm{Q})\|_{F}$
$\displaystyle\leq\|(\bm{Y}-\bm{Z}\bm{Q}_{\bm{Y}})^{\top}(\bm{X}-\bm{Y}\bm{Q})\|_{F}+\|\bm{Y}^{\top}(\bm{X}-\bm{Y}\bm{Q})\|_{F}$
$\displaystyle\leq\epsilon\sqrt{nd}\|\bm{X}-\bm{Y}\bm{Q}\|_{F}+\|\bm{Y}^{\top}\bm{X}-n\bm{Q}\|_{F}$

where
$\|\bm{Y}-\bm{Z}\bm{Q}_{\bm{Y}}\|\leq\|\bm{Y}-\bm{Z}\bm{Q}_{\bm{Y}}\|_{F}\leq\epsilon\sqrt{nd}.$
For the second term,

$\displaystyle\|\bm{Y}^{\top}\bm{X}-n\bm{Q}\|_{F}^{2}$
$\displaystyle=\|\bm{Y}^{\top}\bm{X}\|_{F}^{2}-2n\|\bm{Y}^{\top}\bm{X}\|_{*}+n^{2}d$
$\displaystyle=\sum_{i=1}^{d}(n-\sigma_{i}(\bm{Y}^{\top}\bm{X}))^{2}$
$\displaystyle\leq(nd-\|\bm{Y}^{\top}\bm{X}\|_{*})^{2}$
$\displaystyle\leq(n-\sigma_{\min}(\bm{Y}^{\top}\bm{X}))\cdot(nd-\|\bm{Y}^{\top}\bm{X}\|_{*})$
$\displaystyle\leq\epsilon^{2}nd\|\bm{X}-\bm{Y}\bm{Q}\|_{F}^{2}$

where $0\leq n-\sigma_{\min}(\bm{Y}^{\top}\bm{X})\leq 2\epsilon^{2}nd$ and
$\|\bm{X}-\bm{Y}\bm{Q}\|_{F}^{2}=2(nd-\|\bm{Y}^{\top}\bm{X}\|_{*})$. As a
result,

$\|\bm{Z}^{\top}(\bm{X}-\bm{Z}\bm{Q}_{\bm{X}})\|_{F}\leq
2\epsilon\sqrt{nd}\|\bm{X}-\bm{Y}\bm{Q}\|_{F}=2\epsilon\sqrt{nd}\cdot
d_{F}(\bm{X},\bm{Y}).$

To sum up, we have

$\displaystyle d_{F}({\cal L}\bm{X},{\cal L}\bm{Y})$
$\displaystyle\leq\frac{1}{\sqrt{n}}\cdot 2\epsilon\sqrt{nd}\cdot
d_{F}(\bm{X},\bm{Y})+3\sigma\sqrt{\frac{d}{n}}\cdot d_{F}(\bm{X},\bm{Y})$
$\displaystyle\leq\left(2\epsilon\sqrt{d}+3\sigma\sqrt{\frac{d}{n}}\right)\cdot
d_{F}(\bm{X},\bm{Y}).$

∎

###### Proof of Lemma 4.7.

The proof follows from Davis-Kahan theorem. Consider the augmented matrix:

$\widetilde{\bm{X}}=\begin{bmatrix}0&\bm{X}\\\
\bm{X}^{\top}&0\end{bmatrix},\quad\widetilde{\bm{Y}}=\begin{bmatrix}0&\bm{Y}\\\
\bm{Y}^{\top}&0\end{bmatrix}.$

Let $(\bm{U}_{X},\bm{V}_{X})$ and $(\bm{U}_{Y},\bm{V}_{Y})$ be the left and
right singular vectors of $\bm{X}$ and $\bm{Y}$ respectively. Then
$\begin{bmatrix}\bm{U}_{X}\\\ \bm{V}_{X}\end{bmatrix}$ and
$\begin{bmatrix}\bm{U}_{Y}\\\ \bm{V}_{Y}\end{bmatrix}$ are the eigenvectors
associated with the top $d$ eigenvalues of $\widetilde{\bm{X}}$ and
$\widetilde{\bm{Y}}$ respectively which are also equal to the singular values
of $\bm{X}$ and $\bm{Y}$. Applying Davis-Kahan theorem gives

$\displaystyle\min_{\bm{R}\in\operatorname{O}(d)}\left\|\begin{bmatrix}\bm{U}_{X}\\\
\bm{V}_{X}\end{bmatrix}-\begin{bmatrix}\bm{U}_{Y}\\\
\bm{V}_{Y}\end{bmatrix}\bm{R}\right\|_{F}$
$\displaystyle\leq\frac{\sqrt{2}}{\sigma_{\min}(\bm{X})+\sigma_{\min}(\bm{Y})}\left\|(\widetilde{\bm{X}}-\widetilde{\bm{Y}})\begin{bmatrix}\bm{U}_{X}\\\
\bm{V}_{X}\end{bmatrix}\right\|_{F}$ $\displaystyle(\text{where
}\|\widetilde{\bm{X}}-\widetilde{\bm{Y}}\|_{F}=\sqrt{2}\|\bm{X}-\bm{Y}\|_{F})\quad$
$\displaystyle\leq\frac{\sqrt{2}}{\sigma_{\min}(\bm{X})+\sigma_{\min}(\bm{Y})}\|\widetilde{\bm{X}}-\widetilde{\bm{Y}}\|_{F}\cdot\left\|\begin{bmatrix}\bm{U}_{X}\\\
\bm{V}_{X}\end{bmatrix}\right\|$ $\displaystyle\left(\text{where
}\left\|\begin{bmatrix}\bm{U}_{X}\\\
\bm{V}_{X}\end{bmatrix}\right\|=\sqrt{2}\right)\quad$
$\displaystyle\leq\frac{2\sqrt{2}\|\bm{X}-\bm{Y}\|_{F}}{\sigma_{\min}(\bm{X})+\sigma_{\min}(\bm{Y})}$

where the spectral gap $\delta$ in Theorem 4.6 is

$\delta=\lambda_{d}(\widehat{\bm{X}})-\lambda_{d+1}(\widehat{\bm{Y}})=\sigma_{\min}(\bm{X})+\sigma_{\min}(\bm{Y})$

since the bottom $d$ eigenvalues of $\widetilde{\bm{X}}$ and
$\widetilde{\bm{Y}}$ are negative singular values of $\bm{X}$ and $\bm{Y}$
respectively. Now we estimate the distance between $\mathcal{P}(\bm{X})$ and
$\mathcal{P}(\bm{Y}):$

$\displaystyle\|\mathcal{P}(\bm{X})-\mathcal{P}(\bm{Y})\|_{F}$
$\displaystyle=\|\bm{U}_{X}\bm{V}_{X}^{\top}-\bm{U}_{Y}\bm{V}_{Y}^{\top}\|_{F}$
$\displaystyle\leq\|\bm{U}_{X}\bm{V}_{X}^{\top}-\bm{U}_{Y}\bm{R}\bm{V}_{X}^{\top}+\bm{U}_{Y}\bm{R}\bm{V}_{X}^{\top}-\bm{U}_{Y}\bm{R}\bm{R}^{\top}\bm{V}_{Y}^{\top}\|_{F}$
$\displaystyle\leq\|\bm{U}_{X}-\bm{U}_{Y}\bm{R}\|_{F}+\|\bm{V}_{X}-\bm{V}_{Y}\bm{R}\|_{F}$
$\displaystyle\leq\sqrt{2}\left\|\begin{bmatrix}\bm{U}_{X}\\\
\bm{V}_{X}\end{bmatrix}-\begin{bmatrix}\bm{U}_{Y}\\\
\bm{V}_{Y}\end{bmatrix}\bm{R}\right\|_{F}$
$\displaystyle\leq\frac{4\|\bm{X}-\bm{Y}\|_{F}}{\sigma_{\min}(\bm{X})+\sigma_{\min}(\bm{Y})}.$

∎

###  4.2 Keep the iterates in the basin of attraction

The challenging part is to keep the iterates $\bm{S}^{\ell}$ in the basin of
attraction $\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$. In
particular, it is not trivial to estimate the “correlation” between
$\bm{W}_{m}$ and $\bm{S}^{\ell}$ since $\bm{S}^{\ell}$ depends on $\bm{W}_{m}$
implicitly for all $1\leq m\leq n$. The remedy is to use the very popular
_leave-one-out_ technique by introducing an auxiliary sequence which is the
output of generalized power method based on the data matrix:

$\bm{A}^{(m)}_{ij}=\begin{cases}\bm{I}_{d}+\sigma\bm{W}_{ij},&\text{ if
}~{}i\neq m\text{ and }j\neq m,\\\ \bm{I}_{d},&\text{ if }~{}i=m\text{ or
}j=m,\end{cases}$

which is exactly equal to $\bm{A}$ except its $m$th block row and column. In
other words,

$\bm{A}^{(m)}=\bm{Z}\bm{Z}^{\top}+\sigma\bm{W}^{(m)}$ (4.5)

where

$\bm{W}^{(m)}_{ij}=\begin{cases}\bm{W}_{ij},&\text{ if }~{}i\neq m\text{ and
}j\neq m,\\\ 0,&\text{ if }~{}i=m\text{ or }j=m.\end{cases}$

Denote $\bm{S}^{\ell,m}$ as the $\ell$th iterate from the generalized power
method with

${\cal
L}^{(m)}=n^{-1}\bm{A}^{(m)}=n^{-1}\left(\bm{Z}\bm{Z}^{\top}+\sigma\bm{W}^{(m)}\right),$

which means

$\bm{S}^{\ell+1,m}=\mathcal{P}_{n}({\cal L}^{(m)}\bm{S}^{\ell,m}).$

By construction, $\\{\bm{S}^{\ell,m}\\}_{\ell=0}^{\infty}$ is  _statistically
independent_ of $\bm{W}_{m}$ and thus applying the concentration inequality to
$\|\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\|_{F}$ yields a tight bound. The missing
piece is the difference between $\bm{S}^{\ell,m}$ and $\bm{S}^{\ell}$ for all
$1\leq m\leq n$ and $\ell\geq 0.$ Note that $\bm{A}$ and $\bm{A}^{(m)}$ differ
up to only one row/column and thus we believe $\bm{S}^{\ell}$ and
$\bm{S}^{\ell,m}$ are very close. As long as
$d_{F}(\bm{S}^{\ell},\bm{S}^{\ell,m})$ is small (in particular, of order
$\sqrt{d}$), then $\|\bm{W}_{m}^{\top}\bm{S}^{\ell}\|_{F}$ is of order
$\sqrt{nd}(\sqrt{d}+\sqrt{\log n}).$

Now we first start with bounding $\|\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\|_{F}$.

######  Lemma 4.10.

For $X\sim\chi^{2}_{k}$, we have

$\hbox{\msbm{P}}(X\geq
k+t)\leq\exp\left(-\frac{1}{2}\left(t-k\log\left(1+\frac{t}{k}\right)\right)\right)$

for $t>0.$ In particular, it holds

$\hbox{\msbm{P}}(\sqrt{X}\geq\sqrt{k}+\gamma\sqrt{\log n})\leq
n^{-\gamma^{2}/2},\quad\gamma>0.$

###### Proof: .

This is a quite standard result which can be easily proven by using moment
generating function and Markov inequality. For any $\lambda>0$,

$\displaystyle\hbox{\msbm{P}}(X\geq k+t)$ $\displaystyle\leq
e^{-\lambda(k+t)}\operatorname{\hbox{\msbm{E}}}e^{\lambda
X}=e^{-\lambda(k+t)}(1-2\lambda)^{-k/2}$
$\displaystyle=\exp\left(-\lambda(k+t)-\frac{k}{2}\log(1-2\lambda)\right).$

The upper bound is minimized when choosing $\lambda=\frac{t}{2(k+t)}$, which
gives the bound.

If $t=2\gamma\sqrt{k\log n}+\gamma^{2}\log n$, then

$\displaystyle\hbox{\msbm{P}}(X\geq(\sqrt{k}+\gamma\sqrt{\log n})^{2})$
$\displaystyle\leq\exp\left(-\frac{1}{2}\left(2\gamma\sqrt{k\log
n}+\gamma^{2}\log n-k\log\frac{(\sqrt{k}+\gamma\sqrt{\log
n})^{2}}{k}\right)\right)$ $\displaystyle(\text{use}~{}\log(1+x)\leq
x,x>0))\quad$ $\displaystyle\leq\exp\left(-\frac{1}{2}\left(2\gamma\sqrt{k\log
n}+\gamma^{2}\log n-2k\cdot\frac{\gamma\sqrt{\log n}}{\sqrt{k}}\right)\right)$
$\displaystyle=n^{-\gamma^{2}/2}$ (4.6)

for any $\gamma>0.$ ∎

By construction of $\bm{S}^{\ell,m}$, we know that $\bm{S}^{\ell,m}$ is
independent of $\bm{W}_{m}$ for all $\ell$. Thus by taking a union, we have
the following lemma.

######  Lemma 4.11.

It holds uniformly that

$\max_{1\leq m\leq
n}\|\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\|_{F}\leq\sqrt{nd}(\sqrt{d}+\gamma\sqrt{\log
n})$ (4.7)

for $1\leq\ell\leq L$ with probability at least $1-Ln^{-\gamma^{2}/2+1}$. In
particular, we choose $L=n$ and $\gamma=4.$

###### Proof: .

For any fixed $\ell$ and $m$, we know that each entry of
$\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\in\hbox{\msbm{R}}^{d\times d}$ is an i.i.d.
$\mathcal{N}(0,n)$ random variable. Thus

$n^{-1}\|\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\|_{F}^{2}\sim\chi^{2}_{d^{2}}.$

Using Lemma 4.10 with $k=d^{2}$ and $t=2\gamma d\sqrt{\log n}+\gamma^{2}\log
n$ gives

$n^{-1}\|\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\|_{F}^{2}\leq(d+\gamma\sqrt{\log
n})^{2}$

with probability at least $1-n^{-\gamma^{2}/2}$. Now taking a union bound over
$1\leq m\leq n$ and $1\leq\ell\leq L$, we have

$\max_{1\leq\ell\leq L,1\leq m\leq
n}\|\bm{W}_{m}^{\top}\bm{S}^{\ell,m}\|_{F}\leq\sqrt{n}\left(d+\gamma\sqrt{\log
n}\right)\leq\sqrt{nd}(\sqrt{d}+\gamma\sqrt{\log n})$

with probability at least $1-Ln^{-\gamma^{2}/2+1}=1-n^{-\gamma^{2}/2+2}.$ ∎

Now we can see that in order to show that
$\|\bm{W}_{m}^{\top}\bm{S}^{\ell}\|_{F}$ is small, it suffices to bound the
error between $\bm{S}^{\ell}$ and $\bm{S}^{\ell,m}$ for all $1\leq m\leq n$
and $1\leq\ell\leq L$. In fact, for the initialization $\bm{S}^{0}$ and
$\bm{S}^{0,m}$, we have the following result.

######  Lemma 4.12.

Under

$\sigma<c_{0}\min\left\\{\epsilon\sqrt{\frac{n}{d}},\frac{\kappa\sqrt{n}}{\sqrt{d}+4\sqrt{\log
n}}\right\\}$

for a sufficiently small constant $c_{0}$, then the initialization satisfies:

$\displaystyle d_{F}(\bm{S}^{0},\bm{Z})$
$\displaystyle\leq\frac{\epsilon\sqrt{nd}}{2},$ (4.8) $\displaystyle
d_{F}(\bm{S}^{0},\bm{S}^{0,m})$
$\displaystyle\leq\frac{\kappa\sqrt{d}}{2},\quad 1\leq m\leq n,$ (4.9)
$\displaystyle\|\bm{W}_{m}^{\top}\bm{S}^{0}\|_{F}$
$\displaystyle\leq\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$ (4.10)

uniformly for all $1\leq i\leq n.$

Note that if we only want to prove the tightness of SDP, the initialization
step is not necessary since we can simply pick $\bm{S}^{0}=\bm{Z}$ for the
purpose of proof. The initialization step works mainly for the global
convergence of the efficient projected generalized power method. We defer the
proof of this lemma in Section 4.4. From now on, we set $\xi=3\kappa+1$ and
$\kappa>2\epsilon$ in $\mathcal{N}_{\xi,\infty}.$

######  Lemma 4.13.

Conditioned on (4.3) and (4.7), we have for $1\leq\ell\leq L$,

$\displaystyle d_{F}(\bm{S}^{\ell},\bm{S}^{\ell,m})$
$\displaystyle\leq\frac{\kappa\sqrt{d}}{2},$ (4.11) $\displaystyle\max_{1\leq
m\leq n}\left\|\bm{W}_{m}^{\top}\bm{S}^{\ell}\right\|_{F}$
$\displaystyle\leq\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n}),$ (4.12) $\displaystyle d_{F}(\bm{S}^{\ell},\bm{Z})\leq$
$\displaystyle\frac{\epsilon\sqrt{nd}}{2},$ (4.13)

if

$\sigma<\min\left\\{\frac{\epsilon^{2}d}{(3\kappa+2)\sqrt{d}},\frac{\kappa}{24}\right\\}\frac{\sqrt{n}}{\sqrt{d}+4\sqrt{\log
n}}.$

Combined with Lemma 4.9, we have

$d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell})\leq\frac{1}{2}d_{F}(\bm{S}^{\ell},\bm{S}^{\ell-1})\leq
2^{-\ell}d_{F}(\bm{S}^{1},\bm{S}^{0}),\quad 1\leq\ell\leq L-1$ (4.14)

since $\bm{S}^{\ell}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}.$

For $\ell=0,$ we will show that in the initialization section.

###### Proof of Lemma 4.13.

The proof is based on induction. First of all, the initial value $\bm{S}^{0}$
and $\bm{S}^{0,m}$ satisfy (4.11), (4.12), and (4.13) in Lemma 4.12. Suppose
all the three inequalities (4.11), (4.12), and (4.13) hold true for
$0,1,\cdots,\ell$, we will prove the case for $\ell+1.$

Step 1: Proof of (4.11). Note that $\bm{S}^{\ell}$ is in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ implies
$\sigma_{\min}([{\cal L}\bm{S}^{\ell}]_{i})>1-\epsilon^{2}d$ for all $1\leq
i\leq n$ which follows from Lemma 4.8. Applying Lemma 4.9 gives

$\displaystyle d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell+1,m})$
$\displaystyle\leq\frac{4}{1-\epsilon^{2}d}d_{F}({\cal L}\bm{S}^{\ell},{\cal
L}^{(m)}\bm{S}^{\ell,m})\leq\frac{9}{2}d_{F}({\cal L}\bm{S}^{\ell},{\cal
L}^{(m)}\bm{S}^{\ell,m})$

where $\epsilon^{2}d<1/64.$ Let
$\bm{Q}^{\ell,m}=\min_{\bm{Q}\in\operatorname{O}(d)}\|{\cal
L}\bm{S}^{\ell}-{\cal L}\bm{S}^{\ell,m}\bm{Q}\|_{F}.$ We proceed by using
triangle inequality:

$\displaystyle d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell+1,m})$
$\displaystyle\leq\frac{9}{2}\left(d_{F}({\cal L}\bm{S}^{\ell},{\cal
L}\bm{S}^{\ell,m})+d_{F}({\cal L}\bm{S}^{\ell,m},{\cal
L}^{(m)}\bm{S}^{\ell,m})\right)$ $\displaystyle\leq\frac{9}{2}d_{F}({\cal
L}\bm{S}^{\ell},{\cal
L}\bm{S}^{\ell,m})+\frac{3\sigma}{2n}\|(\bm{W}-\bm{W}^{(m)})\bm{S}^{\ell,m}\|_{F}.$
(4.15)

Since $d_{F}(\bm{S}^{\ell},\bm{S}^{\ell,m})\leq\frac{\kappa\sqrt{d}}{2}$
holds, then

$d_{F}(\bm{S}^{\ell,m},\bm{Z})\leq
d_{F}(\bm{S}^{\ell},\bm{Z})+d_{F}(\bm{S}^{\ell},\bm{S}^{\ell,m})\leq\frac{\epsilon\sqrt{nd}}{2}+\frac{\kappa\sqrt{d}}{2}\leq
0.6\epsilon\sqrt{nd}$

implies $\bm{S}^{\ell,m}\in\mathcal{N}_{\epsilon}.$ Then Lemma 4.5 implies
that

$d_{F}({\cal L}\bm{S}^{\ell},{\cal
L}\bm{S}^{\ell,m})\leq\frac{1}{9}d_{F}(\bm{S}^{\ell},\bm{S}^{\ell,m})$ (4.16)

Note that

$[(\bm{W}-\bm{W}^{(m)})\bm{S}^{\ell,m}]_{j}=\begin{cases}\bm{W}_{ji}\bm{S}_{i}^{\ell,m},&j\neq
i,\\\ \bm{W}_{m}^{\top}\bm{S}^{\ell,m},&j=i.\end{cases}$

Therefore, we have

$\displaystyle\|(\bm{W}-\bm{W}^{(m)})\bm{S}^{\ell,m}\|_{F}$
$\displaystyle\leq\|\bm{W}_{i}\bm{S}^{\ell,m}_{i}\|_{F}+\|\bm{W}_{i}^{\top}\bm{S}^{\ell,m}\|_{F}$
$\displaystyle(\text{use Lemma~{}\ref{lem:gauss}})\quad$
$\displaystyle\leq\|\bm{W}_{i}\|_{F}+\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})$
$\displaystyle\leq 3\sqrt{nd}\cdot\sqrt{d}+\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})$
$\displaystyle<4\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})$ (4.17)

where $\bm{S}_{i}^{\ell,m}$, the $i$th block of $\bm{S}^{\ell,m}$, is
$\operatorname{O}(d).$

Then combining (4.11), (4.15), (4.16) and (4.17) together gives

$\displaystyle d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell+1,m})$
$\displaystyle\leq\frac{1}{2}d_{F}(\bm{S}^{\ell},\bm{S}^{\ell,m})+\frac{3\sigma}{2n}\|(\bm{W}-\bm{W}^{(m)})\bm{S}^{\ell,m}\|_{F}$
$\displaystyle\leq\frac{1}{2}\cdot\frac{\kappa\sqrt{d}}{2}+\frac{3\sigma}{2n}\cdot
4\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})\leq\frac{\kappa\sqrt{d}}{2}$

where $\sigma\leq\frac{\kappa\sqrt{n}}{24(\sqrt{d}+4\sqrt{\log n})}.$

Step 2: Proof of (4.12). Let $\bm{R}$ be the orthogonal matrix which minimizes
$\|\bm{S}^{\ell+1}-\bm{S}^{\ell+1,m}\bm{R}\|_{F}$ over
$\bm{R}\in\operatorname{O}(d)$. Then

$\displaystyle\left\|\bm{W}_{m}^{\top}\bm{S}^{\ell+1}\right\|_{F}$
$\displaystyle\leq\left\|\bm{W}_{m}^{\top}(\bm{S}^{\ell+1}-\bm{S}^{\ell+1,m}\bm{R})\right\|_{F}+\|\bm{W}_{m}^{\top}\bm{S}^{\ell+1,m}\|_{F}$
$\displaystyle(\text{use Lemma~{}\ref{lem:gauss}})\quad$
$\displaystyle\leq\|\bm{W}_{m}\|\cdot
d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell+1,m})+\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})$
$\displaystyle\leq
3\sqrt{nd}\cdot\frac{\kappa\sqrt{d}}{2}+\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})$
$\displaystyle\leq\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n}).$

Step 3: Proof of (4.13). Since both $\bm{S}^{\ell}$ and
$\bm{Z}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$, then

$d_{F}(\bm{S}^{\ell+1},\bm{Z})=d_{F}(\mathcal{P}_{n}({\cal
L}\bm{S}^{\ell}),\mathcal{P}_{n}(\bm{Z}))\leq\frac{9}{2}\cdot d_{F}({\cal
L}\bm{S}^{\ell},\bm{Z}),\quad\bm{S}^{\ell}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$

which follows from Lemma 4.9.

For $d_{F}({\cal L}\bm{S}^{\ell},\bm{Z})$, it suffices to estimate
$\max_{1\leq i\leq n}\|[{\cal L}\bm{S}^{\ell}]_{i}-\bm{R}\|_{F}$ for some
orthogonal matrix
$\bm{R}=\mathcal{P}(\bm{Z}^{\top}\bm{S}^{\ell})\in\operatorname{O}(d).$ We
look at the $i$th block of ${\cal L}\bm{S}^{\ell}:$

$[{\cal
L}\bm{S}^{\ell}]_{i}=\frac{1}{n}\bm{Z}^{\top}\bm{S}^{\ell}+\frac{\sigma}{n}\bm{W}_{i}^{\top}\bm{S}^{\ell}$

Then

$\displaystyle\min_{\bm{R}\in\operatorname{O}(d)}\max_{1\leq i\leq n}\|[{\cal
L}\bm{S}^{\ell}]_{i}-\bm{R}\|_{F}$
$\displaystyle\leq\min_{\bm{R}\in\operatorname{O}(d)}\left\|\frac{1}{n}\bm{Z}^{\top}\bm{S}^{\ell}-\bm{R}\right\|_{F}+\frac{\sigma}{n}\max_{1\leq
i\leq n}\|\bm{W}_{i}^{\top}\bm{S}^{\ell}\|_{F}.$

For the first term, we have
$\min_{\bm{R}\in\operatorname{O}(d)}\|\bm{S}^{\ell}-\bm{Z}\bm{R}\|_{F}\leq\epsilon\sqrt{nd}/2$
which is equivalent to

$2nd-2\|\bm{Z}^{\top}\bm{S}^{\ell}\|_{*}\leq\frac{\epsilon^{2}nd}{4}\Longrightarrow\|\bm{Z}^{\top}\bm{S}^{\ell}\|_{*}\geq\left(1-\frac{\epsilon^{2}}{8}\right)nd.$

Note that

$\displaystyle\|\bm{Z}^{\top}\bm{S}^{\ell}-n\bm{R}\|_{F}^{2}$
$\displaystyle=\sum_{i=1}^{d}\left(\sigma_{i}^{2}(\bm{Z}^{\top}\bm{S}^{\ell})-2n\sigma_{i}(\bm{Z}^{\top}\bm{S}^{\ell})\right)+n^{2}d$
$\displaystyle=\sum_{i=1}^{d}(\sigma_{i}(\bm{Z}^{\top}\bm{S}^{\ell})-n)^{2}$
$\displaystyle\leq(nd-\|\bm{Z}^{\top}\bm{S}^{\ell}\|_{*})^{2}$
$\displaystyle\leq\frac{\epsilon^{4}n^{2}d^{2}}{64}$

where $0\leq\sigma_{i}(\bm{Z}^{\top}\bm{S}^{\ell})\leq n.$ This implies
$\|\bm{Z}^{\top}\bm{S}^{\ell}-n\bm{R}\|_{F}\leq\epsilon^{2}nd/8.$ Then

$\displaystyle\min_{\bm{R}\in\operatorname{O}(d)}\max_{1\leq i\leq n}\|[{\cal
L}\bm{S}^{\ell}]_{i}-\bm{R}\|_{F}$
$\displaystyle\leq\min_{\bm{R}\in\operatorname{O}(d)}\left\|\frac{1}{n}\bm{Z}^{\top}\bm{S}^{\ell}-\bm{R}\right\|_{F}+\frac{\sigma}{n}\max_{1\leq
i\leq n}\|\bm{W}_{i}^{\top}\bm{S}^{\ell}\|_{F}$
$\displaystyle(\text{use}~{}\eqref{eq:kappa2})\quad$
$\displaystyle\leq\frac{\epsilon^{2}d}{8}+\frac{\sigma}{n}\cdot\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$
$\displaystyle\leq\frac{\epsilon^{2}d}{8}+\frac{\epsilon^{2}d}{2}<\frac{\epsilon\sqrt{d}}{9}$

where $\epsilon$ is a constant satisfying $\epsilon\sqrt{d}\leq 1/32$ and

$\sigma\leq\frac{\epsilon^{2}d}{3\kappa+2}\cdot\frac{\sqrt{n}}{\sqrt{d}(\sqrt{d}+4\sqrt{\log
n})}.$

Therefore, it holds

$d_{F}(\bm{S}^{\ell+1},\bm{Z})\leq\frac{9}{2}\cdot d_{F}({\cal
L}\bm{S}^{\ell},\bm{Z})\leq\frac{9}{2}\cdot\frac{\epsilon\sqrt{nd}}{9}\leq\frac{\epsilon\sqrt{nd}}{2}.$

Now we have proven
$\bm{S}^{\ell+1}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$. By
induction, we have
$\bm{S}^{\ell}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ for all
$1\leq\ell\leq L$. Now we can immediately invoke Lemma 4.9 and get

$\displaystyle d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell})$
$\displaystyle=d_{F}(\mathcal{P}_{n}({\cal
L}\bm{S}^{\ell}),\mathcal{P}_{n}({\cal
L}\bm{S}^{\ell-1}))\leq\frac{1}{2}d_{F}(\bm{S}^{\ell},\bm{S}^{\ell-1}).$

∎

######  Lemma 4.14.

Conditioned on the Lemma 4.13, we have

$\displaystyle d_{F}(\bm{S}^{L+t},\bm{S}^{L+t-1})$ $\displaystyle\leq
2^{-t}d_{F}(\bm{S}^{L},\bm{S}^{L-1}),\quad\forall t\in\hbox{\msbm{Z}}^{+}$
(4.18)

and $\\{\bm{S}^{L+t}\\}_{t\geq 0}$ belong to
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$, i.e.,

$\displaystyle\max_{1\leq m\leq
n}\left\|\bm{W}_{m}^{\top}\bm{S}^{\ell}\right\|_{F}$
$\displaystyle\leq\left(3\epsilon+\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n}),$ (4.19) $\displaystyle d_{F}(\bm{S}^{\ell},\bm{Z})$
$\displaystyle\leq\epsilon\sqrt{nd},$ (4.20)

for all $\ell\in\hbox{\msbm{Z}}^{+}.$ Given (4.14) in Lemma 4.13, we have

$d_{F}(\bm{S}^{\ell},\bm{S}^{\ell-1})\leq
2^{-\ell}d_{F}(\bm{S}^{0},\bm{Z}),\quad\forall\ell\in\hbox{\msbm{Z}}^{+}.$

Here we set $L=n.$

###### Proof: .

We will prove (4.18) for all $t\in\hbox{\msbm{Z}}^{+}$ by induction. This is
true if $t=0$. Now we assume that this also holds for all $0\leq t\leq k$ and
prove the case for $t=k+1.$ In fact, it suffices to show that
$\bm{S}^{L+k}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$. If so, we
have

$d_{F}(\bm{S}^{L+k+1},\bm{S}^{L+k})=d_{F}(\mathcal{P}_{n}({\cal
L}\bm{S}^{L+k}),\mathcal{P}_{n}({\cal
L}\bm{S}^{L+k-1}))\leq\frac{1}{2}d_{F}(\bm{S}^{L+k},\bm{S}^{L+k-1}),$

following from Lemma 4.9.

Now we will start proving
$\bm{S}^{L+k}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$. Combining
Lemma 4.13 with the assumption indicates that

$\bm{S}^{L}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty},\quad
d_{F}(\bm{S}^{\ell},\bm{S}^{\ell-1})\leq
2^{-\ell+1}d_{F}(\bm{S}^{1},\bm{S}^{0}),\quad 1\leq\ell\leq L+k.$

By triangle inequality and the assumption that (4.18) holds for $0\leq t\leq
k$, then

$\displaystyle d_{F}(\bm{S}^{L+k},\bm{S}^{L})$
$\displaystyle\leq\sum_{j=1}^{k}d_{F}(\bm{S}^{L+j},\bm{S}^{L+j-1})\leq\sum_{j=1}^{k}2^{-j}d_{F}(\bm{S}^{L},\bm{S}^{L-1})$
$\displaystyle\leq\frac{1}{2}d_{F}(\bm{S}^{L},\bm{S}^{L-1})\leq
2^{-L}d_{F}(\bm{S}^{1},\bm{S}^{0})$ $\displaystyle\leq
2^{-L+1}\sqrt{nd}<\epsilon$

where $d_{F}(\bm{S}^{1},\bm{S}^{0})\leq 2\sqrt{nd}$ and $L$ is $n$. As a
result, we have

$\displaystyle d_{F}(\bm{S}^{L+k},\bm{Z})$ $\displaystyle\leq
d_{F}(\bm{S}^{L+k},\bm{S}^{L})+d_{F}(\bm{S}^{L},\bm{Z})\leq\epsilon+\frac{\epsilon\sqrt{nd}}{2}\leq\epsilon\sqrt{nd}$

which implies $\bm{S}^{L}\in\mathcal{N}_{\epsilon}$. Denote $\bm{R}$ as the
orthogonal matrix which minimizes $\|\bm{S}^{L+k}-\bm{S}^{L}\bm{R}\|_{F}$. For
$\|\bm{W}_{i}^{\top}\bm{S}^{L+k}\|_{F}$, we have

$\displaystyle\|\bm{W}_{m}^{\top}\bm{S}^{L+k}\|_{F}$
$\displaystyle\leq\|\bm{W}_{m}^{\top}(\bm{S}^{L+k}-\bm{S}^{L}\bm{R})\|_{F}+\|\bm{W}_{m}^{\top}\bm{S}^{L}\|_{F}$
$\displaystyle(\text{use}~{}\eqref{eq:kappa2})\quad$
$\displaystyle\leq\|\bm{W}_{m}\|\cdot
d_{F}(\bm{S}^{L+k},\bm{S}^{L})+\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$
$\displaystyle=3\epsilon\sqrt{nd}+\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$
$\displaystyle\leq\left(3\epsilon+\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$ $\displaystyle\leq\xi\sqrt{nd}(\sqrt{d}+4\sqrt{\log n})$

where $\|\bm{W}_{i}\|\leq 3\sqrt{nd}$, the bound on
$\|\bm{W}_{m}^{\top}\bm{S}^{L}\|_{F}$ follows from (4.12), and $\xi=3\kappa+1$
with $\kappa\geq 2\epsilon$.

Now we have shown that $\bm{S}^{L+k}$ and $\bm{S}^{L+k-1}$ are in the
contraction region $\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$.
Applying Lemma 4.9 finishes the proof:

$\displaystyle d_{F}(\bm{S}^{L+k+1},\bm{S}^{L+k})$
$\displaystyle=d_{F}(\mathcal{P}_{n}({\cal
L}\bm{S}^{L+k}),\mathcal{P}_{n}({\cal
L}\bm{S}^{L+k-1}))\leq\frac{1}{2}d_{F}(\bm{S}^{L+k},\bm{S}^{L+k-1}).$

∎

###  4.3 Proof of Theorem 3.1 and 3.2: Convergence to global maximizer

###### Proof of Theorem 3.1 and 3.2.

The proofs of Theorem 3.1 and 3.2 are exactly the same except the
initialization part. For the tightness of SDP, it suffices to let
$\bm{S}^{0}=\bm{Z}$ since we only need to show the global optimum of the SDP
is exactly the MLE. For the generalized power method, we show that spectral
initialization provides a sufficiently good starting point which is addressed
in Section 4.4.

To prove Theorem 3.1 and 3.2, it suffices to show that the iterates have a
limiting point $\bm{S}^{\infty}$ which satisfy
$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$ and is also located in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$, according to Theorem
4.1.

Step 1: The existence and convergence of the limiting point in
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$.

Conditioned on Lemma 4.14, it holds that
$d_{F}(\bm{S}^{\ell},\bm{S}^{\ell-1})\leq
2^{-\ell+1}d_{F}(\bm{S}^{1},\bm{S}^{0})$ for all $\ell\in\hbox{\msbm{Z}}^{+}.$
Then $\\{\bm{S}^{\ell}\\}_{\ell=0}^{\infty}$ is a Cauchy sequence since

$\displaystyle d_{F}(\bm{S}^{\ell+k},\bm{S}^{\ell})$
$\displaystyle\leq\sum_{i=\ell}^{\ell+k-1}d_{F}(\bm{S}^{i+1},\bm{S}^{i})$
$\displaystyle\leq\sum_{i=\ell}^{\ell+k-1}2^{-i}d_{F}(\bm{S}^{1},\bm{S}^{0})\leq
2^{-\ell+1}d_{F}(\bm{S}^{1},\bm{S}^{0}),\quad\forall k\in\hbox{\msbm{Z}}^{+}$
(4.21)

is arbitrarily small for any sufficiently large $\ell.$ Note that
$\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$ is a closed and compact
set in the Euclidean space. The distance function $d_{F}(\cdot,\cdot)$ is
equivalent to the Frobenius norm on the quotient space
$\operatorname{O}(d)^{\otimes n}/\operatorname{O}(d)$ where
$\operatorname{O}(d)$ is also a compact set. Thus since $\bm{S}^{\ell}$ is a
Cauchy sequence, we know there must exist a limiting point $\bm{S}^{\infty}.$
From (4.21), we also have the linear convergence of $\bm{S}^{\ell}$ to the
limiting point:

$d_{F}(\bm{S}^{\infty},\bm{S}^{\ell})\leq
2^{-\ell+1}d_{F}(\bm{S}^{1},\bm{S}_{0}).$ (4.22)

Now we want to prove that $\bm{S}^{\infty}(\bm{S}^{\infty})^{\top}$ is the
unique global maximizer to (2.3) by using Theorem 4.1.

Note that (4.19) and (4.20) hold for all $\ell$. Therefore, sending $\ell$ to
$\infty$ gives

$\max_{1\leq m\leq
n}\|\bm{W}_{m}^{\top}\bm{S}^{\infty}\|_{F}\leq\left(3\epsilon+\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+\sqrt{\log
n}),\quad d_{F}(\bm{S}^{\infty},\bm{Z})\leq\epsilon\sqrt{nd}$ (4.23)

since $\mathcal{N}_{\epsilon}$ and $\mathcal{N}_{\xi,\infty}$ are compact
sets.

Step 2: The limiting point $\bm{S}^{\infty}$ satisfies
$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$ for some block-diagonal
positive semidefinite matrix $\bm{\Lambda}.$

Note that

$d_{F}({\cal P}_{n}({\cal L}\bm{S}^{\infty}),\bm{S}^{\ell})\leq d_{F}({\cal
P}_{n}({\cal L}\bm{S}^{\infty}),{\cal P}_{n}({\cal
L}\bm{S}^{\ell}))+d_{F}({\cal P}_{n}({\cal L}\bm{S}^{\ell}),\bm{S}^{\ell})$

By letting $\ell$ go to $\infty$ and using Lemma 4.9, it holds

$\lim_{\ell\rightarrow\infty}d_{F}({\cal P}_{n}({\cal L}\bm{S}^{\infty}),{\cal
P}_{n}({\cal
L}\bm{S}^{\ell}))\leq\frac{1}{2}\lim_{\ell\rightarrow\infty}d_{F}(\bm{S}^{\infty},\bm{S}^{\ell})=0.$

For $d_{F}({\cal P}_{n}({\cal L}\bm{S}^{\ell}),\bm{S}^{\ell})$, we have

$d_{F}({\cal P}_{n}({\cal
L}\bm{S}^{\ell}),\bm{S}^{\ell})=d_{F}(\bm{S}^{\ell+1},\bm{S}^{\ell})\leq
2^{-\ell}d_{F}(\bm{S}^{1},\bm{S}^{0})\rightarrow
0,\quad\ell\rightarrow\infty,$

which follows from Lemma 4.13. Therefore, $d_{F}({\cal P}_{n}({\cal
L}\bm{S}^{\infty}),\bm{S}^{\infty})=0$ and we have ${\cal P}_{n}({\cal
L}\bm{S}^{\infty})=\bm{S}^{\infty}\bm{O}$ for some orthogonal matrix $\bm{O}.$

Note that $d_{F}(\bm{S}^{\infty},\bm{Z})\leq\epsilon\sqrt{nd}$ and
$\left\|\bm{W}_{i}^{\top}\bm{S}^{\infty}\right\|_{F}\leq\left(3\epsilon+\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+\sqrt{\log
n})$ imply $\sigma_{\min}([{\cal L}\bm{S}^{\infty}]_{i})>0$. Therefore, the
limiting point $d_{F}({\cal P}_{n}({\cal
L}\bm{S}^{\infty}),\bm{S}^{\infty})=0$ satisfies:

$\mathcal{P}([{\cal L}\bm{S}^{\infty}]_{i})=([{\cal
L}\bm{S}^{\infty}]_{i}[{\cal
L}\bm{S}^{\infty}]_{i}^{\top})^{-\frac{1}{2}}[{\cal
L}\bm{S}^{\infty}]_{i}=\bm{S}_{i}^{\infty}\bm{O},\quad\forall 1\leq i\leq n$

where $\bm{O}$ is an orthogonal matrix. It means

$[{\cal L}\bm{S}^{\infty}]_{i}=([{\cal L}\bm{S}^{\infty}]_{i}[{\cal
L}\bm{S}^{\infty}]_{i}^{\top})^{\frac{1}{2}}\bm{S}^{\infty}_{i}\bm{O}.$ (4.24)

Next, we will show that $\bm{O}=\bm{I}_{d}.$

From (4.24), we know that

$\sum_{i=1}^{n}(\bm{S}^{\infty}_{i})^{\top}[{\cal
L}\bm{S}^{\infty}]_{i}=\sum_{i=1}^{n}(\bm{S}^{\infty}_{i})^{\top}([{\cal
L}\bm{S}^{\infty}]_{i}[{\cal
L}\bm{S}^{\infty}]_{i}^{\top})^{\frac{1}{2}}\bm{S}^{\infty}_{i}\bm{O}$

For the term on the left side,

$\displaystyle\sum_{i=1}^{n}(\bm{S}^{\infty}_{i})^{\top}[{\cal
L}\bm{S}^{\infty}]_{i}$
$\displaystyle=\frac{1}{n}\sum_{i,j}(\bm{S}^{\infty}_{i})^{\top}(\bm{I}+\sigma\bm{W}_{ij})\bm{S}^{\infty}_{j}$
$\displaystyle=\frac{1}{n}(\bm{S}^{\infty})^{\top}\bm{Z}\bm{Z}^{\top}\bm{S}^{\infty}+\frac{\sigma}{n}(\bm{S}^{\infty})^{\top}\bm{W}\bm{S}^{\infty}$
$\displaystyle\succeq(n^{-1}\sigma_{\min}^{2}(\bm{Z}^{\top}\bm{S}^{\infty})-\sigma\|\bm{W}\|)\bm{I}_{d}$
$\displaystyle\geq\left(n\left(1-\frac{\epsilon^{2}d}{2}\right)^{2}-3\sigma\sqrt{nd}\right)\bm{I}_{d}\succ
0$

where

$\sigma_{\min}(\bm{Z}^{\top}\bm{S}^{\infty})\geq\left(1-\frac{\epsilon^{2}d}{2}\right)n,\quad\sigma<\frac{1}{3}\left(1-\frac{\epsilon^{2}d}{2}\right)^{2}\sqrt{\frac{n}{d}}.$

Now we let

$\bm{X}=\sum_{i=1}^{n}(\bm{S}^{\infty}_{i})^{\top}[{\cal
L}\bm{S}^{\infty}]_{i}\succ
0,\quad\bm{Y}=\sum_{i=1}^{n}(\bm{S}^{\infty}_{i})^{\top}([{\cal
L}\bm{S}^{\infty}]_{i}[{\cal
L}\bm{S}^{\infty}]_{i}^{\top})^{\frac{1}{2}}\bm{S}^{\infty}_{i}\succeq 0.$

For $\bm{X}\succ 0$ and $\bm{Y}\succeq 0$ which satisfy $\bm{X}=\bm{Y}\bm{O}$,
we will show $\bm{O}$ must be $\bm{I}_{d}.$ This follows from

$\bm{X}^{-\frac{1}{2}}\bm{Y}\bm{X}^{-\frac{1}{2}}=\bm{X}^{\frac{1}{2}}\bm{O}^{\top}\bm{X}^{-\frac{1}{2}}$

The left hand side is still positive semidefinite and all its eigenvalues are
real and nonnegative. The right hand side has eigenvalues which are in the
form of $\\{\exp(\operatorname{\mathrm{i}}\theta_{i})\\}_{i=1}^{n}$ since
$\bm{O}$ is orthogonal. Thus $\theta_{i}$ must be zero and its means
$\bm{O}=\bm{I}_{d}.$

Therefore, following from (4.24), the limiting point satisfies

$\bm{A}\bm{S}^{\infty}=\bm{\Lambda}\bm{S}^{\infty}$

where $\bm{\Lambda}_{ii}=n([{\cal L}\bm{S}^{\infty}]_{i}[{\cal
L}\bm{S}^{\infty}]_{i}^{\top})^{\frac{1}{2}}\succ 0.$ Moreover, we have shown
that $\bm{S}^{\infty}\in\mathcal{N}_{\epsilon}\cap\mathcal{N}_{\xi,\infty}$.
Applying Theorem 4.1 immediately gives the global optimality of
$\bm{S}^{\infty}(\bm{S}^{\infty})^{\top}$ in the SDP relaxation (2.3).

Step 3:  A block-wise error bound between $\bm{S}^{\infty}$ and $\bm{Z}$.

Now we will derive a block-wise error bound of $\bm{S}^{\infty}$,

$\min_{\bm{O}\in\operatorname{O}(d)}\max_{1\leq i\leq
n}\|\bm{S}^{\infty}_{i}-\bm{O}\|_{F}.$

This is bounded by $\max_{1\leq i\leq n}\|\bm{S}^{\infty}_{i}-\bm{Q}\|_{F}$
where $\bm{Q}=\mathcal{P}(\bm{Z}^{\top}\bm{S}^{\infty}).$ Note that
$\bm{S}^{\infty}$ satisfies (4.23) and Lemma 4.4 implies
$\sigma_{\min}\left(\bm{Z}^{\top}\bm{S}^{\infty}\right)\geq\left(1-\epsilon^{2}d/2\right)n$.
For each $1\leq i\leq n$, we have $\bm{S}_{i}^{\infty}=\mathcal{P}([{\cal
L}\bm{S}^{\infty}]_{i})$ and

$\displaystyle\|\bm{S}_{i}^{\infty}-\bm{Q}\|_{F}$
$\displaystyle=\|\mathcal{P}([{\cal
L}\bm{S}^{\infty}]_{i})-\mathcal{P}(n^{-1}\bm{Z}^{\top}\bm{S}^{\infty})\|_{F}$
$\displaystyle\leq\frac{4}{1-\epsilon^{2}d}\|[{\cal
L}\bm{S}^{\infty}]_{i}-n^{-1}\bm{Z}^{\top}\bm{S}^{\infty}\|_{F}$
$\displaystyle=\frac{4}{1-\epsilon^{2}d}\left\|\frac{\sigma}{n}\bm{W}_{i}^{\top}\bm{S}^{\infty}\right\|_{F}$
$\displaystyle(\text{use~{}\eqref{eq:Sinfty}})\quad$
$\displaystyle\leq\frac{4}{1-\epsilon^{2}d}\frac{\sigma}{n}\cdot\left(3\epsilon+\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+4\sqrt{\log
n})$ $\displaystyle\lesssim\sigma\sqrt{n^{-1}d}(\sqrt{d}+4\sqrt{\log n})$

which follows from Lemma 4.7 and (4.23). ∎

###  4.4 Proof of Lemma 4.12: Initialization

Recall that the initialization in Algorithm 1 involves two steps: (a) compute
the top $d$ eigenvectors $\bm{\Phi}$ of
$\bm{A}=\bm{Z}\bm{Z}^{\top}+\sigma\bm{W}$; (b) round each $d\times d$ block
$\bm{\Phi}_{i}$ of $\bm{\Phi}$ into an orthogonal matrix and use
$\bm{S}_{i}^{0}=\mathcal{P}(\bm{\Phi}_{i})$ as the initialization. Note that
Lemma 4.12 requires the initial value $\bm{S}^{0}$ to be very close to the
ground true $\bm{Z}$ and also not highly “aligned” with the noise
$\bm{W}_{m}$. It is a seemingly simple task to justify that: if the noise is
small, then applying Davis-Kahan theorem would provide a tight bound of
$\min_{\bm{Q}\in\operatorname{O}(d)}\|\bm{\Phi}-\bm{Z}\bm{Q}\|$. Then we
believe that $\mathcal{P}_{n}(\bm{\Phi})$ is also close to $\bm{Z}$. However,
due to the rounding procedure in the initialization, we actually need a more
careful analysis of the eigenvectors $\bm{\Phi}$. More precisely, the rounding
procedure equals

$\bm{S}_{i}^{0}=\mathcal{P}(\bm{\Phi}_{i})=(\bm{\Phi}_{i}\bm{\Phi}_{i}^{\top})^{-\frac{1}{2}}\bm{\Phi}_{i},\quad
1\leq i\leq n.$

which involves a block-wise inversion. Therefore, in order to obtain
$d_{F}(\bm{S}^{0},\bm{Z})\leq\epsilon\sqrt{nd}$, we actually need to establish
a block-wise bound between $\bm{\Phi}$ and $\bm{Z}$, i.e.,

$\min_{\bm{Q}\in\operatorname{O}(d)}\max_{1\leq i\leq
n}\|\bm{\Phi}_{i}-\bm{Q}\|.$

Therefore, what we need is much more than classical eigenspace perturbation
bound given by Davis-Kahan theorem [23] which provides an error bound in
$\|\cdot\|$ or $\|\cdot\|_{F}$.

The block-wise perturbation bound on the eigenvectors is a natural
generalization of recent entrywise error bound on eigenvectors arising from
spectral clustering, $\hbox{\msbm{Z}}_{2}$-synchronization, and matrix
completion. The author’s early work [34] uses the popular leave-one-out
technique to obtain such a block-wise error bound in several applications,
including the scenario discussed in this paper. One core result for the
initialization reads as follows:

######  Theorem 4.15 (Theorem 5.1 in [34]).

Suppose $(\bm{\Phi},\bm{\Lambda})$ are the top $d$ eigenvectors and
eigenvalues of $\bm{A}$ satisfying $\bm{A}\bm{\Phi}=\bm{\Phi}\bm{\Lambda}$,
$\bm{\Phi}^{\top}\bm{\Phi}=n\bm{I}_{d}$ and
$\bm{Q}=\mathcal{P}(\bm{Z}^{\top}\bm{\Phi})$. Let

$\eta:=\sigma n^{-\frac{1}{2}}(\sqrt{d}+\sqrt{\log
n}),\quad\sigma<C_{0}^{-1}\sqrt{n}(\sqrt{d}+\sqrt{\log n})^{-1}$ (4.25)

where $C_{0}>0$ is an absolute large constant. Then with probability at least
$1-O(n^{-1}d^{-1})$, it holds

$\|\bm{\Phi}_{i}-[\bm{A}\bm{Z}]_{i}\bm{Q}\bm{\Lambda}^{-1}\|\lesssim\eta\max_{1\leq
i\leq n}\|\bm{\Phi}_{i}\|,$ (4.26)

uniformly for all $1\leq i\leq n$ where $[\bm{A}\bm{Z}]_{i}$ is the $i$th
block of $\bm{A}\bm{Z}$. Moreover, we have

$|\sigma_{j}(\bm{\Phi}_{i})-1|\lesssim\eta,\qquad\forall 1\leq i\leq
n,~{}1\leq j\leq d.$ (4.27)

Interested readers may refer to [34] for more details and we do not repeat the
proof again here. For the completeness of presentation, we will discuss the
main idea of proving (4.26) and how to derive (4.27) from (4.26). Note that
our goal is to estimate each block of $\bm{\Phi}$. The idea is to apply one
step power iteration and use the outcome to approximate $\bm{\Phi}$:

$\bm{\Phi}-\bm{A}\bm{Z}\bm{Q}\bm{\Lambda}^{-1}=\bm{A}(\bm{\Phi}-\bm{Z}\bm{Q})\bm{\Lambda}^{-1}$

where $\bm{A}\bm{\Phi}=\bm{\Phi}\bm{\Lambda}^{-1}.$ Therefore, the error bound
on the $i$th block is

$\|\bm{\Phi}_{i}-[\bm{A}\bm{Z}]_{i}\bm{Q}\bm{\Lambda}^{-1}\|\leq\|[\bm{A}(\bm{\Phi}-\bm{Z}\bm{Q})]_{i}\|\|\bm{\Lambda}^{-1}\|$

Here $\lambda_{\min}(\bm{\Lambda})\geq n-\sigma\|\bm{W}\|>n/2$ follows from
Weyl’s theorem and thus $\|\bm{\Lambda}^{-1}\|\leq 2/n.$ It suffices to bound
$\|[\bm{A}(\bm{\Phi}-\bm{Z}\bm{Q})]_{i}\|$. However, the $i$th block column of
$\bm{A}$ and $\bm{\Phi}$ are  _statistically dependent_ and thus we cannot
apply concentration inequality directly to obtain a tight bound. To overcome
this issue, we apply the leave-one-out technique again: approximate
$\bm{\Phi}$ with $\bm{\Phi}^{(i)}$ which consists of the top $d$ eigenvectors
of $\bm{A}^{(i)}$ defined in (4.5):

$\displaystyle\|\bm{A}_{i}^{\top}(\bm{\Phi}-\bm{Z}\bm{Q})\|$
$\displaystyle=\|(\bm{Z}+\sigma\bm{W}_{i})^{\top}(\bm{\Phi}-\bm{Z}\bm{Q})\|$
$\displaystyle\leq\|\bm{Z}^{\top}(\bm{\Phi}-\bm{Z}\bm{Q})\|+\sigma\|\bm{W}_{i}^{\top}(\bm{\Phi}-\bm{\Phi}^{(i)})\|+\sigma\|\bm{W}_{i}^{\top}(\bm{\Phi}^{(i)}-\bm{Z}\bm{Q})\|$
$\displaystyle\leq\sqrt{n}\|\bm{\Phi}-\bm{Z}\bm{Q}\|+\sigma\|\bm{W}_{i}\|\|\bm{\Phi}-\bm{\Phi}^{(i)}\|+\sigma\|\bm{W}_{i}^{\top}(\bm{\Phi}^{(i)}-\bm{Z}\bm{Q})\|.$

The first term is bounded by using standard Davis-Kahan argument; for the
second term, we first use Davis-Kahan theorem again to bound
$\|\bm{\Phi}-\bm{\Phi}^{(i)}\|$ which is quite small and then control the term
by $\|\bm{W}_{i}\|\|\bm{\Phi}-\bm{\Phi}^{(i)}\|$; for the third term, due to
the independence between $\bm{W}_{i}$ and $\bm{\Phi}^{(i)}-\bm{Z}\bm{Q}$, one
can also get a tight bound by using concentration inequality of a Gaussian
random matrix [55]. This finishes the proof of (4.26).

With (4.26), we can derive (4.27). First of all, $\max_{1\leq i\leq
n}\|\bm{\Phi}_{i}\|=O(1)$ holds since (4.26) gives

$\max_{1\leq i\leq
n}\|\bm{\Phi}_{i}\|\lesssim\frac{1}{1-C^{\prime}\eta}\|[\bm{A}\bm{Z}]_{i}\bm{Q}\bm{\Lambda}^{-1}\|\leq
C_{0}\|[\bm{A}\bm{Z}]_{i}\|\|\bm{\Lambda}^{-1}\|\leq 4C_{0}.$

Here $C_{0}$ and $C^{\prime}$ are two constants, and the bound on
$\|[\bm{A}\bm{Z}]_{i}\|$ follows from

$\|[\bm{A}\bm{Z}]_{i}\|=\left\|\sum_{j=1}^{n}(\bm{I}_{d}+\sigma\bm{W}_{ij})\right\|\leq
n+\sigma\|\bm{W}_{i}^{\top}\bm{Z}\|\leq 2n$

if $\sigma<c_{0}\sqrt{n}/(\sqrt{d}+\sqrt{\log n})$ where
$\|\bm{W}_{i}^{\top}\bm{Z}\|=O(\sqrt{n}(\sqrt{d}+\sqrt{\log n}))$ holds with
high probability for all $1\leq i\leq n$ implied by [55, Theorem 4.4.5]. Now
we have

$\displaystyle\|\bm{\Phi}_{i}-\bm{Q}\|$
$\displaystyle\leq\|\bm{\Phi}_{i}-[\bm{A}\bm{Z}]_{i}\bm{Q}\bm{\Lambda}^{-1}\|+\|[\bm{A}\bm{Z}]_{i}\bm{Q}\bm{\Lambda}^{-1}-\bm{Q}\|$
(use (4.26))
$\displaystyle\lesssim\eta+\|(n\bm{I}_{d}+\bm{W}_{i}^{\top}\bm{Z})\bm{Q}\bm{\Lambda}^{-1}-\bm{Q}\|$
$\displaystyle\lesssim\eta+\sigma\|\bm{W}_{i}^{\top}\bm{Z}\bm{Q}\bm{\Lambda}^{-1}\|+\|\bm{Q}(n\bm{\Lambda}^{-1}-\bm{I}_{n})\|$
$\displaystyle\lesssim\eta+\sigma\|\bm{W}_{i}^{\top}\bm{Z}\|\|\bm{\Lambda}^{-1}\|+\|\bm{\Lambda}-n\bm{I}_{d}\|\|\bm{\Lambda}^{-1}\|$
$\displaystyle\lesssim\eta+\sigma\sqrt{n}(\sqrt{d}+\sqrt{\log
n})\cdot\frac{2}{n}+\sigma\|\bm{W}\|\cdot\frac{2}{n}\lesssim 6\eta$

where $\|\bm{\Lambda}-n\bm{I}_{d}\|\leq\sigma\|\bm{W}\|$. These arguments lead
to (4.27) in Lemma 4.15.

The next lemma is used to estimate the distance
$d_{F}(\bm{S}^{0},\bm{S}^{0,m})$ in (4.9). In fact, it suffices to estimate
the distance between $\bm{\Phi}$ and $\bm{\Phi}^{(m)}$, i.e., the top $d$
eigenvectors of $\bm{A}$ and $\bm{A}^{(m)}$ respectively. Note that $\bm{A}$
and $\bm{A}^{(m)}$ differ only by one block column and row, and thus their
eigenvectors are also very close, following from Davis-Kahan theorem.

######  Lemma 4.16 (Lemma 5.9 in [34]).

Let $\bm{\Phi}$ and $\bm{\Phi}^{(m)}$ be the top $d$ eigenvectors of $\bm{A}$
and $\bm{A}^{(m)}$ with
$\bm{\Phi}^{\top}\bm{\Phi}=(\bm{\Phi}^{(m)})^{\top}\bm{\Phi}^{(m)}=n\bm{I}_{d}$
respectively. Then

$\displaystyle\|\bm{\Phi}-\bm{\Phi}^{(m)}\bm{Q}_{m}\|\leq\sqrt{2}\|(\bm{I}-n^{-1}\bm{\Phi}\bm{\Phi}^{\top})\bm{\Phi}^{(m)}\|\lesssim\sigma
n^{-\frac{1}{2}}(\sqrt{d}+\sqrt{\log n})\cdot\max_{1\leq i\leq
n}\|\bm{\Phi}_{i}\|.$

where $\bm{Q}_{m}=\mathcal{P}((\bm{\Phi}^{(m)})^{\top}\bm{\Phi})$. In other
words,

$n-\sigma_{\ell}\left(\bm{\Phi}^{\top}\bm{\Phi}^{(m)}\right)\lesssim\sigma(\sqrt{d}+\sqrt{\log
n})\max_{1\leq i\leq n}\|\bm{\Phi}_{i}\|,\quad 1\leq\ell\leq d$

and

$\|(\bm{\Phi}^{\top}\bm{\Phi}^{(m)}(\bm{\Phi}^{(m)})^{\top}\bm{\Phi})^{1/2}-n\bm{I}_{d}\|\lesssim\sigma(\sqrt{d}+\sqrt{\log
n})\max_{1\leq i\leq n}\|\bm{\Phi}_{i}\|.$

###### Proof: .

The proof follows from setting $\bm{X}=\bm{A}$ and
$\bm{X}_{\bm{E}}=\bm{A}^{(m)}$ and then applying Davis-Kahan perturbation
bound in Theorem 4.6. ∎

Now we will show that the initialization step produces $\bm{S}^{0}$ which
satisfies (4.8), (4.9), and (4.10).

###### Proof of Lemma 4.12.

By Davis-Kahan’s theorem with $\bm{X}=\bm{Z}\bm{Z}^{\top}$ and
$\bm{X}_{\bm{E}}=\bm{X}+\sigma\bm{W}$, it holds that

$\displaystyle\|\bm{\Phi}-\bm{Z}\bm{Q}\|_{F}$
$\displaystyle\leq\sqrt{2}\left\|\left(\bm{I}_{nd}-\frac{1}{n}\bm{\Phi}\bm{\Phi}^{\top}\right)\bm{Z}\right\|_{F}$
$\displaystyle\leq\sqrt{2}\cdot\frac{1}{n-\sigma\|\bm{W}\|}\cdot\|(\bm{A}-\bm{Z}\bm{Z}^{\top})\bm{Z}\|_{F}$
$\displaystyle\lesssim\sigma n^{-1}\cdot\|\bm{W}\bm{Z}\|_{F}$
$\displaystyle\lesssim\sigma n^{-1}\cdot
3\sqrt{nd}\cdot\sqrt{nd}\lesssim\sigma d$

where $\|\bm{Z}\|_{F}=\sqrt{nd}$ and
$\bm{Q}=\mathcal{P}(\bm{Z}^{\top}\bm{\Phi})$. Note that all the blocks of
$\bm{\Phi}$ have smallest singular values greater than 1/2, following from
Lemma 4.15. Thus

$\displaystyle d_{F}(\bm{S}^{0},\bm{Z})$
$\displaystyle\leq\|\mathcal{P}_{n}(\bm{\Phi})-\mathcal{P}_{n}(\bm{Z}\bm{Q})\|_{F}$
$\displaystyle\leq\sqrt{\sum_{i=1}^{n}\|\mathcal{P}(\bm{\Phi}_{i})-\mathcal{P}(\bm{Q})\|_{F}^{2}}$
$\displaystyle\leq 8\sqrt{\sum_{i=1}^{n}\|\bm{\Phi}_{i}-\bm{Q}\|_{F}^{2}}$
$\displaystyle=8\|\bm{\Phi}-\bm{Z}\bm{Q}\|_{F}$ $\displaystyle\lesssim\sigma
d$

where the third equality follows from Lemma 4.9. Note that if

$\sigma\leq c_{0}\epsilon\sqrt{n/d},$

for some small constant $c_{0},$ then
$d_{F}(\bm{S}^{0},\bm{Z})\leq\epsilon\sqrt{nd}$ which gives (4.8).

Also note that Lemma 4.16 implies

$\|\bm{\Phi}-\bm{\Phi}^{(m)}\bm{Q}_{m}\|_{F}\lesssim\sigma
n^{-1/2}d^{1/2}(\sqrt{d}+\sqrt{\log n})$

where $\bm{Q}_{m}=\mathcal{P}((\bm{\Phi}^{(m)})^{\top}\bm{\Phi})$ and
$|\sigma_{j}(\bm{\Phi}_{i})-1|\lesssim\sigma n^{-1/2}(\sqrt{d}+\sqrt{\log
n})<1/2$ for all $1\leq j\leq d$ and $1\leq i\leq n.$ As a result, we have
(4.9) which follows from

$\displaystyle\|\bm{S}^{0}-\bm{S}^{0,m}\bm{Q}_{m}\|_{F}$
$\displaystyle=\|\mathcal{P}_{n}(\bm{\Phi})-\mathcal{P}_{n}(\bm{\Phi}^{(m)}\bm{Q}_{m})\|_{F}$
$\displaystyle\leq 8\|\bm{\Phi}-\bm{\Phi}^{(m)}\bm{Q}_{m}\|_{F}$
$\displaystyle\lesssim\sigma n^{-1/2}d^{1/2}(\sqrt{d}+\sqrt{\log n})$
$\displaystyle\leq\frac{\kappa\sqrt{d}}{2}$

provided that

$\sigma<c_{0}\frac{\kappa\sqrt{n}}{\sqrt{d}+\sqrt{\log n}}$

for some small constant $c_{0}.$

Then for the correlation between $\bm{W}_{m}$ and $\bm{S}^{0}$, we have

$\displaystyle\|\bm{W}_{m}^{\top}\bm{S}^{0}\|_{F}$
$\displaystyle\leq\|\bm{W}_{m}^{\top}(\bm{S}^{0}-\bm{S}^{0,m}\bm{Q}_{m})\|_{F}+\|\bm{W}_{m}^{\top}\bm{S}^{0,m}\|_{F}$
$\displaystyle\leq\|\bm{W}_{m}\|\cdot\|\bm{S}^{0}-\bm{S}^{0,m}\bm{Q}_{m}\|_{F}+\|\bm{W}_{m}^{\top}\bm{S}^{0,m}\|_{F}$
$\displaystyle\leq
3\sqrt{nd}\cdot\frac{\kappa\sqrt{d}}{2}+\sqrt{nd}(\sqrt{d}+\gamma\sqrt{\log
n})$

with probability at least $1-n^{-\gamma^{2}/2}$ following from Lemma 4.10
where all entries of
$n^{-1/2}\bm{W}_{m}^{\top}\bm{S}^{0,m}\in\hbox{\msbm{R}}^{d\times d}$ are
i.i.d. standard normal random variables and
$n^{-1}\|\bm{W}_{m}^{\top}\bm{S}^{0,m}\|_{F}^{2}\sim\chi^{2}_{d^{2}}.$ Now
taking the union bound over $1\leq m\leq n$ gives

$\displaystyle\|\bm{W}_{m}^{\top}\bm{S}^{0}\|_{F}$
$\displaystyle\leq\left(\frac{3\kappa}{2}+1\right)\sqrt{nd}(\sqrt{d}+\gamma\sqrt{\log
n})$

holds uniformly for all $1\leq m\leq n$ with probability at least
$1-n^{-\gamma^{2}/2+1}$ with $\gamma=4.$ ∎

## References

  * [1] E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer.  Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery.  IEEE Transactions on Network Science and Engineering, 1(1):10–22, 2014.
  * [2] E. Abbe, J. Fan, K. Wang, and Y. Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  Annals of Statistics, 2019.
  * [3] P.-A. Absil, R. Mahony, and R. Sepulchre.  Optimization Algorithms on Matrix Manifolds.  Princeton University Press, 2009.
  * [4] M. Arie-Nachimson, S. Z. Kovalsky, I. Kemelmacher-Shlizerman, A. Singer, and R. Basri.  Global motion estimation from point matches.  In 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization & Transmission, pages 81–88. IEEE, 2012.
  * [5] A. S. Bandeira, N. Boumal, and A. Singer.  Tightness of the maximum likelihood semidefinite relaxation for angular synchronization.  Mathematical Programming, 163(1-2):145–167, 2017.
  * [6] A. S. Bandeira, N. Boumal, and V. Voroninski.  On the low-rank approach for semidefinite programs arising in synchronization and community detection.  In Conference on Learning Theory, pages 361–382, 2016.
  * [7] F. Benaych-Georges and R. R. Nadakuditi.  The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices.  Advances in Mathematics, 227(1):494–521, 2011.
  * [8] N. Boumal.  A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints.  arXiv preprint arXiv:1506.00575, 2015.
  * [9] N. Boumal.  Nonconvex phase synchronization.  SIAM Journal on Optimization, 26(4):2355–2377, 2016.
  * [10] N. Boumal, V. Voroninski, and A. Bandeira.  The non-convex Burer-Monteiro approach works on smooth semidefinite programs.  In Advances in Neural Information Processing Systems, pages 2757–2765, 2016.
  * [11] N. Boumal, V. Voroninski, and A. S. Bandeira.  Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs.  Communications on Pure and Applied Mathematics, 73(3):581–608, 2020\.
  * [12] S. Burer and R. D. Monteiro.  A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization.  Mathematical Programming, 95(2):329–357, 2003.
  * [13] S. Burer and R. D. Monteiro.  Local minima and convergence in low-rank semidefinite programming.  Mathematical Programming, 103(3):427–444, 2005.
  * [14] E. J. Candes, X. Li, and M. Soltanolkotabi.  Phase retrieval via wirtinger flow: Theory and algorithms.  IEEE Transactions on Information Theory, 61(4):1985–2007, 2015\.
  * [15] K. N. Chaudhury, Y. Khoo, and A. Singer.  Global registration of multiple point clouds using semidefinite programming.  SIAM Journal on Optimization, 25(1):468–501, 2015.
  * [16] Y. Chen and E. J. Candès.  The projected power method: An efficient algorithm for joint alignment from pairwise differences.  Communications on Pure and Applied Mathematics, 71(8):1648–1714, 2018.
  * [17] Y. Chen, Y. Chi, J. Fan, C. Ma, and Y. Yan.  Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization.  SIAM Journal on Optimization, 30(4):3098–3121, 2020.
  * [18] Y. Chen, J. Fan, C. Ma, and K. Wang.  Spectral method and regularized MLE are both optimal for top-k ranking.  Annals of Statistics, 47(4):2204, 2019.
  * [19] Y. Chen, L. Guibas, and Q. Huang.  Near-optimal joint object matching via convex relaxation.  Proceedings of the 31st International Conference on Machine Learning, 32(2):100–108, 2014.
  * [20] Y. Chen, C. Suh, and A. J. Goldsmith.  Information recovery from pairwise measurements.  IEEE Transactions on Information Theory, 62(10):5881–5905, 2016\.
  * [21] M. Cucuringu.  Synchronization over $\hbox{\msbm{Z}}_{2}$ and community detection in signed multiplex networks with constraints.  Journal of Complex Networks, 3(3):469–506, 2015.
  * [22] M. Cucuringu, Y. Lipman, and A. Singer.  Sensor network localization by eigenvector synchronization over the euclidean group.  ACM Transactions on Sensor Networks (TOSN), 8(3):1–42, 2012.
  * [23] C. Davis and W. M. Kahan.  The rotation of eigenvectors by a perturbation III.  SIAM Journal on Numerical Analysis, 7(1):1–46, 1970.
  * [24] F. Dellaert, D. M. Rosen, J. Wu, R. Mahony, and L. Carlone.  Shonan rotation averaging: Global optimality by surfing $\text{SO}(p)^{n}$.  In European Conference on Computer Vision, pages 292–308. Springer, 2020.
  * [25] S. Deng, S. Ling, and T. Strohmer.  Strong consistency, graph Laplacians, and the stochastic block model.  arXiv preprint arXiv:2004.09780, 2020.
  * [26] J. Eldridge, M. Belkin, and Y. Wang.  Unperturbed: spectral analysis beyond davis-kahan.  In F. Janoos, M. Mohri, and K. Sridharan, editors, Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pages 321–358. PMLR, 07–09 Apr 2018.
  * [27] J. Fan, W. Wang, and Y. Zhong.  An $\ell_{\infty}$ eigenvector perturbation bound and its application to robust covariance estimation.  Journal of Machine Learning Research, 18(207):1–42, 2018.
  * [28] A. Giridhar and P. R. Kumar.  Distributed clock synchronization over wireless networks: Algorithms and analysis.  In Proceedings of the 45th IEEE Conference on Decision and Control, pages 4915–4920. IEEE, 2006.
  * [29] M. X. Goemans and D. P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  Journal of the ACM (JACM), 42(6):1115–1145, 1995.
  * [30] M. Grant and S. Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1, 2014.
  * [31] Q.-X. Huang and L. Guibas.  Consistent shape maps via semidefinite programming.  Computer Graphics Forum, 32(5):177–186, 2013.
  * [32] G. Lerman and Y. Shi.  Robust group synchronization via cycle-edge message passing.  arXiv preprint arXiv:1912.11347, 2019.
  * [33] Y. Li, C. Ma, Y. Chen, and Y. Chi.  Nonconvex matrix factorization from rank-one measurements.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1496–1505. PMLR, 2019.
  * [34] S. Ling.  Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods.  arXiv preprint arXiv:2008.05341, 2020.
  * [35] S. Ling.  Solving orthogonal group synchronization via convex and low-rank optimization: Tightness and landscape analysis.  arXiv preprint arXiv:2006.00902, 2020.
  * [36] S. Ling, R. Xu, and A. S. Bandeira.  On the landscape of synchronization networks: A perspective from nonconvex optimization.  SIAM Journal on Optimization, 29(3):1879–1907, 2019.
  * [37] H. Liu, M.-C. Yue, and A. Man-Cho So.  On the estimation performance and convergence rate of the generalized power method for phase synchronization.  SIAM Journal on Optimization, 27(4):2426–2446, 2017.
  * [38] H. Liu, M.-C. Yue, and A. M.-C. So.  A unified approach to synchronization problems over subgroups of the orthogonal group.  arXiv preprint arXiv:2009.07514, 2020.
  * [39] C. Ma, K. Wang, Y. Chi, and Y. Chen.  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.  Foundations of Computational Mathematics, pages 1–182, 2018.
  * [40] S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira.  Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality.  In Conference on Learning Theory, pages 1476–1515, 2017.
  * [41] Y. Nesterov and A. Nemirovskii.  Interior-Point Polynomial Algorithms in Convex Programming.  SIAM, 1994.
  * [42] O. Ozyesil, V. Voroninski, R. Basri, and A. Singer.  A survey of structure from motion.  Acta Numerica, 26:305–364, 2017.
  * [43] D. Pachauri, R. Kondor, and V. Singh.  Solving the multi-way matching problem by permutation synchronization.  In Advances in Neural Information Processing Systems, pages 1860–1868, 2013.
  * [44] A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra.  Message-passing algorithms for synchronization problems over compact groups.  Communications on Pure and Applied Mathematics, 2016.
  * [45] A. Perry, A. S. Wein, A. S. Bandeira, A. Moitra, et al.  Optimality and sub-optimality of PCA I: Spiked random matrix models.  The Annals of Statistics, 46(5):2416–2451, 2018.
  * [46] K. Rohe, S. Chatterjee, B. Yu, et al.  Spectral clustering and the high-dimensional stochastic blockmodel.  The Annals of Statistics, 39(4):1878–1915, 2011.
  * [47] E. Romanov and M. Gavish.  The noise-sensitivity phase transition in spectral group synchronization over compact groups.  Applied and Computational Harmonic Analysis, 2019.
  * [48] D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard.  SE-Sync: A certifiably correct algorithm for synchronization over the special euclidean group.  The International Journal of Robotics Research, 38(2-3):95–125, 2019.
  * [49] Y. Shen, Q. Huang, N. Srebro, and S. Sanghavi.  Normalized spectral map synchronization.  In Advances in Neural Information Processing Systems, pages 4925–4933, 2016.
  * [50] Y. Shkolnisky and A. Singer.  Viewing direction estimation in cryo-EM using synchronization.  SIAM Journal on Imaging Sciences, 5(3):1088–1110, 2012.
  * [51] A. Singer.  Angular synchronization by eigenvectors and semidefinite programming.  Applied and Computational Harmonic Analysis, 30(1):20–36, 2011\.
  * [52] A. Singer et al.  Mathematics for cryo-electron microscopy.  Proceedings of the International Congress of Mathematicians (ICM), 3:3981–4000, 2018.
  * [53] A. Singer and Y. Shkolnisky.  Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming.  SIAM Journal on Imaging Sciences, 4(2):543–572, 2011.
  * [54] R. Szeliski.  Computer Vision: Algorithms and Applications.  Springer Science & Business Media, 2010.
  * [55] R. Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47.  Cambridge University Press, 2018.
  * [56] U. Von Luxburg.  A tutorial on spectral clustering.  Statistics and Computing, 17(4):395–416, 2007.
  * [57] I. Waldspurger and A. Waters.  Rank optimality for the Burer-Monteiro factorization.  SIAM Journal on Optimization, 30(3):2577–2602, 2020.
  * [58] L. Wang and A. Singer.  Exact and stable recovery of rotations for robust synchronization.  Information and Inference: A Journal of the IMA, 2(2):145–193, 2013\.
  * [59] Z. Wen and W. Yin.  A feasible method for optimization with orthogonality constraints.  Mathematical Programming, 142(1-2):397–434, 2013.
  * [60] Y. Zhong and N. Boumal.  Near-optimal bounds for phase synchronization.  SIAM Journal on Optimization, 28(2):989–1016, 2018.