Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis

Introduction

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

where $g_{i}$ belongs to a given group ${\cal G}$, $w_{ij}$ is the noise, and ${\cal E}$ is the edge set of an underlying network. Depending on the specific group choices, one has found many interesting problems including $\hbox{\msbm{Z}}_{2}$-synchronization , angular synchronization , and permutation group , special orthogonal group , orthogonal group , cyclic group , and real number addition group .

Optimization plays a crucial role in solving group synchronization problems. One commonly used approach is the least squares method. However, the least squares objective arising from many of these aforementioned examples are usually highly nonconvex or even inherently discrete. This has posed a major challenge to retrieve the group elements from their highly noisy pairwise measurements because finding the least squares estimator is NP-hard in general. In the recent few years, many efforts are devoted to finding spectral relaxation and convex relaxation (in particular semidefinite relaxation) as well as nonconvex approaches to solve these otherwise NP-hard problems.

In this work, we focus on the general orthogonal synchronization problem:

where $\bm{G}_{i}$ is a $d\times d$ orthogonal matrix belonging to

Orthogonal group synchronization is frequently found in cryo-EM , computer vision and feature matching problem , and is a natural generalization of $\hbox{\msbm{Z}}_{2}$- and angular synchronization . We aim to establish a theoretical framework to understand when convex and nonconvex approaches can retrieve the orthogonal group elements from the noisy measurements. In particular, we will answer the following two core questions.

For the convex relaxation of orthogonal group synchronization,

Convex relaxation has proven to be extremely powerful in approximating or giving the exact solution to many otherwise NP-hard problems under certain conditions. However, it is not always the case that the relaxation yields a solution that matches the least squares estimator. Thus we aim to answer when one can find the least squares estimator of $O(d)$ synchronization with a simple convex program.

For the nonconvex Burer-Monteiro approach , we are interested in answering this question:

When does the Burer-Monteiro approach yield a benign optimization landscape?

Empirical evidence has indicated that the Burer-Monteiro approach works extremely well to solve large-scale SDPs in many applications despite its inherent nonconvexity. One way to provide a theoretical justification is to show that the optimization landscape is benign, i.e., there is only one global minimizer and no other spurious local minima exist.

Group synchronization problem is a rich source of many mathematical problems. Now we will give a review of the related works which inspire this work. Table 1 provides a non-exhaustive summary of important examples in group synchronization with applications.

The most commonly used approach in group synchronization is to find the least squares estimator. As pointed out earlier, finding the least squares estimator of general $O(d)$ synchronization is NP-hard. In fact, if the group is $\hbox{\msbm{Z}}_{2}$, the least squares objective function is closely related to the graph MaxCut problem, which is a well-known NP-hard problem. Therefore, alternative methods are often needed to tackle this situation. One line of research focuses on the spectral and semidefinite programming relaxation (SDP) including $\hbox{\msbm{Z}}_{2}$-synchronization , angular synchronization , orthogonal group , permutation group . Regarding the SDP relaxation, many efforts are devoted to designing approximation algorithms, such as the Goemans-Williamson relaxation for graph MaxCut. Inspired by the development of compressive sensing and low-rank recovery , we are more interested in the tightness of convex relaxation: the data are not as adversarial as expected in some seemingly NP-hard problems. Convex relaxation in these problems admits the exact solution to the original NP-hard problem under certain conditions. Following this idea, studies the SDP relaxation of $\hbox{\msbm{Z}}_{2}$-synchronization with corrupted data; the tightness of SDP for angular synchronization is first investigated in and a near-optimal performance bound is obtained in ; a very recent work gives a sufficient condition to ensure the tightness of SDP for general orthogonal group synchronization.

Despite the effectiveness of convex approaches, they are not scalable because solving large-scale SDPs are usually very expensive . It is more advantageous to keep the low-rank structure and obtain a much more efficient algorithm instead of solving large-scale SDPs directly. As a result, there is a growing interest in developing nonconvex approaches, particularly the first-order gradient-based algorithm. These methods enjoy the advantage of higher efficiency than the convex approach. However, there are also concerns about the possible existence of multiple local optima which prevent the iteration from converging to the global one. The recent few years have witnessed a surge of research in exploring fast and provably convergent nonconvex optimization approaches. Two main strategies are: (i) design a smart initialization scheme and then provide the global convergence; (ii) analyze the nonconvex optimization landscape. Examples include phase retrieval , dictionary learning , joint alignment , matrix completion and spiked tensor model . These ideas are also applied to several group synchronization problems. Orthogonal group synchronization can be first formulated as a low-rank optimization program with orthogonality constraints and then tackled with many general solvers . The works on joint alignment and on angular synchronization follow two-step procedures: first, use the spectral method for a good initialization and then show that the projected power methods have the property of global linear convergence.

Our focus here is on the optimization landscape of the Burer-Monteiro approach in solving the large SDPs arising from $O(d)$ synchronization. The original remarkable work by Burer and Monteiro shows that as long as $p(p+1)>2n$ where $p$ is the dimension of low-rank matrix and $n$ is the number of constraints, the global optima to Burer-Monteiro factorization match those of the corresponding SDP by using the idea from . Later on, show that the optimization landscape is benign, meaning that no spurious local optima exist in the nonconvex objective function if $p$ is approximately greater than $\sqrt{2n}$. This bound is proven to be almost tight in . On the other hand, it is widely believed that even if $p=O(1),$ the Burer-Monteiro factorization works provably, which is supported by many numerical experiments. We have benefitted greatly from the works regarding the Burer-Monteiro approach on group synchronization in . In , the authors prove that the optimization landscape is benign for $\hbox{\msbm{Z}}_{2}$-synchronization as well as community detection under the stochastic block model if $p=2$. The optimization landscape of angular synchronization is studied in . The work provides a lower bound for the objective function value evaluated at local optima. The bound depends on the rank $p$ and is smartly derived by using the Riemannian Hessian. However, the landscape and the tightness of the Burer-Monteiro approach for $O(d)$ synchronization have not been fully addressed yet, which becomes one main motivation for this work. It is worth noting that the Burer-Monteiro approach is closely related to the synchronization of oscillators on manifold . The analysis of the optimization landscape of the Burer-Monteiro approach in $\hbox{\msbm{Z}}_{2}$ with $p=2$ is equivalent to exploring the stable equilibria of the energy landscape associated with the homogeneous Kuramoto oscillators . This connection is also reflected in the synchronization of coupled oscillators on more general manifolds such as $n$-sphere and Stiefel manifold on arbitrary complex networks.

An important problem regarding the tightness of convex relaxation and landscape analysis is how these two properties depend on the general notion of SNR (signal-to-noise ratio). In most cases, if the noise is rather small compared to the planted signal, optimization methods should easily recover the hidden signal since the tightness of SDP and the benign landscape are guaranteed. However, as the noise strengthens, the landscape becomes bumpy and optimizing the cost function becomes challenging. This leads to the research topic on detecting the critical threshold for this phase transition. Examples can be found in many applications including eigenvectors estimation and the community detection under the stochastic block model . For $\hbox{\msbm{Z}}_{2}$- and angular synchronization, convex methods are tight all the way to the information-theoretical limit but the analysis of optimization landscape remains suboptimal . Our work on $O(d)$ synchronization will follow a similar idea and attempt to explore the critical threshold to ensure the tightness of convex relaxation and the Burer-Monteiro approach.

Our contribution is multifold. First, we prove the tightness of convex relaxation in solving the $O(d)$ synchronization problem by extending the work on $\hbox{\msbm{Z}}_{2}$- and angular synchronization. We propose a deterministic sufficient condition that guarantees the tightness of SDP and easily applies to other noise models. Our result slightly improves the very recent result on the tightness of $O(d)$ synchronization in . Moreover, we analyze the optimization landscape arising from the Burer-Monteiro approach applied to $O(d)$ synchronization. For this low-rank optimization approach, we also provide a general deterministic condition to ensure a benign optimization landscape. The sufficient condition is quite general and applicable to several aforementioned examples such as $\hbox{\msbm{Z}}_{2}$- and angular synchronization , and permutation group , and achieve the state-of-the-art results. Our result on the landscape analysis serves as another example to demonstrate the great success of the Burer-Monteiro approaches in solving large-scale SDPs.

2 Organization of this paper

The paper proceeds as follows: Section 2 introduces the background of orthogonal group synchronization and optimization methods. We show the main results in Section 3. Section 4 focuses on numerical experiments and we give the proofs in Section 5.

3 Notation

For any given matrix $\bm{X}$, $\bm{X}^{\top}$ is the transpose of $\bm{X}$; $\bm{X}\succeq 0$ means $\bm{X}$ is positive semidefinite. Denote $\|\bm{X}\|_{\operatorname{op}}$ the operator norm of $\bm{X}$, $\|\bm{X}\|_{F}$ the Frobenius norm, and $\|\bm{X}\|_{*}$ the nuclear norm, i.e., the sum of singular values. For two matrices $\bm{X}$ and $\bm{Z}$ of the same size, $\bm{X}\circ\bm{Z}$ denotes the Hadamard product of $\bm{X}$ and $\bm{Z}$, i.e., $(\bm{X}\circ\bm{Z})_{ij}=X_{ij}Z_{ij}$; $\langle\bm{X},\bm{Z}\rangle:=\operatorname{Tr}(\bm{X}\bm{Z}^{\top})$ is the inner product. “$\otimes$” stands for the Kronecker product; $\operatorname{diag}(\bm{v})$ gives a diagonal matrix whose diagonal entries equal $\bm{v}$; $\operatorname{blkdiag}(\bm{\Pi}_{11},\cdots,\bm{\Pi}_{nn})$ denotes a block-diagonal matrix whose diagonal blocks are $\bm{\Pi}_{ii}$, $1\leq i\leq n.$ Let $\bm{I}_{n}$ be the $n\times n$ identity matrix, and $\bm{J}_{n}$ be an $n\times n$ matrix whose entries are 1. We denote $\bm{X}\succeq\bm{Z}$ if $\bm{X}-\bm{Z}\succeq 0$, i.e., $\bm{X}-\bm{Z}$ is positive semidefinite. We write $f(n)\lesssim g(n)$ for two positive functions $f(n)$ and $g(n)$ if there exists an absolute positive constant $C$ such that $f(n)\leq Cg(n)$ for all $n.$

Preliminaries

We introduce the model for orthogonal group synchronization. We want to estimate $n$ matrices $\bm{G}_{1},\cdots,\bm{G}_{n}\in O(d)$ from their pairwise measurements $\bm{A}_{ij}$:

where $\bm{A}_{ij}\in\hbox{\msbm{R}}^{d\times d}$ is the observed data and $\bm{\Delta}_{ij}\in\hbox{\msbm{R}}^{d\times d}$ is the noise. Note that $\bm{G}_{i}^{-1}=\bm{G}_{i}$ holds for any orthogonal matrix $\bm{G}_{i}$. Thus in the matrix form, we can reformulate the observed data $\bm{A}$ as

where $\bm{G}^{\top}=[\bm{G}_{1}^{\top},\cdots,\bm{G}_{n}^{\top}]\in\hbox{\msbm{R}}^{d\times nd}$ and the $(i,j)$-block of $\bm{A}$ is $\bm{A}_{ij}=\bm{G}_{i}\bm{G}_{j}^{\top}+\bm{\Delta}_{ij}.$ In particular, we set $\bm{A}_{ii}=\bm{I}_{d}$ and $\bm{\Delta}_{ii}=0.$

One benchmark noise model is the group synchronization from measurements corrupted with Gaussian noise, i.e.,

where each entry in $\bm{W}_{ij}$ is an i.i.d. standard Gaussian random variable and $\bm{W}_{ij}^{\top}=\bm{W}_{ji}.$ The corresponding matrix form is

One common approach to recover $\bm{G}$ is to minimize the nonlinear least squares objective function over the orthogonal group $O(d)$:

In fact, the global minimizer equals the maximum likelihood estimator of (2.1) under Gaussian noise, i.e., assuming each $\bm{\Delta}_{ij}$ is an independent Gaussian random matrix.

Throughout our discussion, we will deal with a more convenient equivalent form. More precisely, we perform a change of variable:

where $\bm{R}_{i}$ and $\bm{G}_{i}\in O(d)$. By letting

then the updated objective function becomes

Its global minimizer equals the global maximizer to

The program (P) is a well-known NP-hard problem. We will focus on solving (P) by convex relaxation and low-rank optimization approach, and study their theoretical guarantees.

2 Convex relaxation

The convex relaxation relies on the idea of lifting: let $\bm{X}=\bm{R}\bm{R}^{\top}\in\hbox{\msbm{R}}^{nd\times nd}$ with $\bm{X}_{ij}=\bm{R}_{i}\bm{R}_{j}^{\top}$. We notice that $\bm{X}\succeq 0$ and $\bm{X}_{ii}=\bm{I}_{d}$ hold for any $\{\bm{R}_{i}\}_{i=1}^{n}\in O(d).$ The convex relaxation of $O(d)$ synchronization is

where $(i,j)$-block of $\bm{A}$ is $\bm{A}_{ij}=\bm{I}_{d}+\bm{\Delta}_{ij}\in\hbox{\msbm{R}}^{d\times d}.$ In particular, if $d=1$, this semidefinite programming (SDP) relaxation reduces to the famous Goemans-Williamson relaxation for the graph MaxCut problem . Since we relax the constraint, it is not necessarily the case that the global maximizer $\widehat{\bm{X}}$ to (SDP) is exactly rank-$d$, i.e., $\widehat{\bm{X}}=\widehat{\bm{G}}\widehat{\bm{G}}^{\top}$ for some $\widehat{\bm{G}}\in\hbox{\msbm{R}}^{nd\times d}$ with $\widehat{\bm{G}}_{i}\in O(d).$ Our goal is to study the tightness of this SDP relaxation: when the solution to (SDP) is exactly rank-$d$, i.e., the convex relaxation gives the global optimal solution to (P) which is also the least squares estimator.

3 Low-rank optimization: Burer-Monteiro approach

Note that solving the convex relaxation (SDP) is extremely expensive especially for large $d$ and $n$. Thus an efficient, robust, and provably convergent optimization algorithm is always in great need. Since the solution is usually low-rank in many empirical experiments, it is appealing to take advantage of this property: keep the iterates low-rank and perform first-order gradient-based approach to solve this otherwise computationally expensive SDP. In particular, we will resort to the Burer-Monteiro approach to deal with the orthogonal group synchronization problem. The core idea of the Burer-Monteiro approach is keeping $\bm{X}$ in a factorized form and taking advantage of its low-rank property. Recall the constraints in (SDP) read $\bm{X}\succeq 0$ and $\bm{X}_{ii}=\bm{I}_{d}$. In the Burer-Monteiro approach, we let $\bm{X}=\bm{S}\bm{S}^{\top}$ where $\bm{S}\in\hbox{\msbm{R}}^{nd\times p}$ with $p>d$. We hope to recover the group elements by maximizing $f(\bm{S})$:

In other words, we substitute $\bm{R}_{i}$ in (P) by a partial orthogonal matrix $\bm{S}_{i}\in\hbox{\msbm{R}}^{d\times p}$ with $\bm{S}_{i}\bm{S}_{i}^{\top}=\bm{I}_{d}$ and $p>d$. Therefore, $\bm{S}$ belongs to the product space of Stiefel manifold, i.e., $\operatorname{St}(d,p)^{\otimes n}:=\underbrace{\operatorname{St}(d,p)\times\cdots\times\operatorname{St}(d,p)}_{n\text{ times}}$

Running projected gradient method on this objective function (BM) definitely saves a large amount of computational resources and memory storage. However, the major issue here is the nonconvexityHere we are actually referring to the nonconvexity of $-f(\bm{S}).$ of the objective function, i.e., there may exist multiple local maximizers in (BM) and random initialization may lead to one of the local maximizers instead of converging to the global one. As a result, our second focus of this paper is to understand when the Burer-Monteiro approach works for $O(d)$ synchronization. In particular, we are interested in the optimization landscape of $f(\bm{S})$: when does there exist only one global maximizer, without any other spurious local maximizers? Moreover, is this global maximizer exactly rank-$d$, i.e., it matches the solution to (P)?

Main theorem

Here is our main theorem which provides a deterministic condition to ensure the tightness of SDP relaxation in orthogonal group synchronization.

The solutions to (P) and (SDP) are exactly the same, i.e., the global maximizer to the SDP is unique and exactly rank-$d$, if

where $\bm{\Delta}_{i}^{\top}=[\bm{\Delta}_{i1},\cdots,\bm{\Delta}_{in}]\in\hbox{\msbm{R}}^{d\times nd}$ is the $i$th block row of $\bm{\Delta}$ and $\bm{\Delta}_{i}^{\top}\bm{G}=\sum_{j=1}^{n}\bm{\Delta}_{ij}\bm{G}_{j}.$

Theorem 3.1 indicates that solving the SDP relaxation yields the global maximizer to (P) which is NP-hard in general, under the condition that the noise strength $\|\bm{\Delta}\|_{\operatorname{op}}$ is small. Moreover, this condition is purely deterministic and thus it can be easily applied to $O(d)$ synchronization under other noise models. Here we provide one such example under Gaussian random noise.

The solution to the SDP relaxation (SDP) is exactly rank-$d$ with high probability if

Our result improves the bound on $\sigma$ by a factor of $\sqrt{d}$, compared with the recent result by Zhang in which the tightness of SDP holds if

One natural question is whether the bound shown above is optimal. The answer is negative. Take the case with Gaussian noise as an example: the strength of the planted signal $\bm{G}\bm{G}^{\top}$ is $\|\bm{G}\bm{G}^{\top}\|_{\operatorname{op}}=n.$ The operator norm of the noise is

where $\|\bm{W}\|_{\operatorname{op}}=2\sqrt{nd}(1+o(1))$ is a classical result for symmetric Gaussian random matrix. For this matrix spike model, the detection threshold should be

In fact, our numerical experiments in Section 4 confirm this threshold. This indicates that our analysis still has a large room for improvement: namely improve the dependence of $\sigma$ on $n$ from $n^{1/4}$ to $n^{1/2}.$

In particular, if $d=1$, i.e., $\hbox{\msbm{Z}}_{2}$-synchronization, SDP is proven to be tight in if $\sigma<\sqrt{\frac{n}{(2+\epsilon)\log n}}$ under Gaussian noise. If $d=2$ and

where $X_{ij}$ and $Y_{ij}$ are independent standard normal, then the model is equivalent to the angular synchronization under complex normal noise which is discussed in . It is shown in that the factor $n^{1/4}$ can be improved to $n^{1/2}$ by using the leave-one-out technique. We leave the tightness analysis of the orthogonal group synchronization as a future research topic.

2 Optimization landscape of Burer-Monteiro approach

Our second main result characterizes the optimization landscape of (BM).

For the objective function $f(\bm{S})$ defined in (BM), it has a unique local maximizer which is also the global maximizer if $p\geq 2d+1$ and

and $\operatorname{Tr}_{d}(\bm{\Delta})=[\operatorname{Tr}(\bm{\Delta}_{ij})]_{ij}\in\hbox{\msbm{R}}^{n\times n}$ denotes the partial trace of $\bm{\Delta}.$ Moreover, this global maximizer is exactly rank-$d$.

Theorem 3.3 conveys two messages: one is that the optimization landscape of (BM) is benign, meaning there exists a unique local maximizer which also corresponds to the global maximizer to the SDP; moreover, it is rank-$d$, indicating the tightness of the global maximizer. The characterization of benign optimization landscape justifies the remarkable performance of the Burer-Monteiro approach.

The optimization landscape of $f(\bm{S})$ is benign if $p\geq 2d+1$ and

with high probability for some small constant $C_{0}$. In other words, $f(\bm{S})$ in (BM) has only one local maximizer which is also global and corresponds to the maximizer of the SDP relaxation (SDP) and (P).

Similar to the scenario in Theorem 3.2, this bound is suboptimal in $n$. The numerical experiments indicate that $\sigma<2^{-1}n^{1/2}d^{-1/2}$ should be the optimal scaling. However, it remains one major open problem to prove that the landscape is benign for $\sigma$ up to the order $n^{1/2}$, even in the scenario of the angular synchronization . Regarding the choice of $p$, one always wants to keep $p$ as small as possible. We believe the bound can be improved to $p\geq 2d$ or even to $p\geq d+2$ from our current bound $p\geq 2d+1$ with more careful analyses. In our numerical experiments, we have seen that $p=2d$ suffices to ensure global convergence of the generalized power method from any random initialization.

Numerics

Our first experiment is to test how the tightness of (SDP) depends on the noise strength. Consider the group synchronization problem,

where $\bm{Z}^{\top}=[\bm{I}_{d},\cdots,\bm{I}_{d}]\in\hbox{\msbm{R}}^{d\times nd}$ and $\bm{W}\in\hbox{\msbm{R}}^{nd\times nd}$ is a symmetric Gaussian random matrix. Since solving (SDP) is rather expensive, we will take an alternative way to find the SDP solution. We first use thd projected power method to get a candidate solution and then confirm it is the global maximizer of the SDP relaxation (SDP) by verifying the global optimality condition.

Proposition 5.1 indicates that $\widehat{\bm{R}}\in\hbox{\msbm{R}}^{nd\times d}$ is the unique global optimal solution to (P) and (SDP) if

where $\widehat{\bm{\Lambda}}$ is an $nd\times nd$ block-diagonal matrix with its $i$th block equal to

We employ the following generalized projected power iteration scheme:

where the initialization is chosen as $\bm{R}^{(0)}=\bm{Z}$, i.e., $\bm{R}^{(0)}_{i}=\bm{I}_{d}$. Here $\bm{U}_{i}^{(t)}$ and $\bm{V}_{i}^{(t)}$ are the left/right singular vectors of $\sum_{j=1}^{n}\bm{A}_{ij}\bm{R}_{j}^{(t)}$ respectively. More precisely, we have

and $\bm{\Lambda}_{ii}^{(t)}=\bm{U}_{i}^{(t)}\bm{\Sigma}_{i}^{(t)}(\bm{U}_{i}^{(t)})^{\top}$ is a symmetric matrix. The fixed point $\bm{R}^{(\infty)}$ of this iteration satisfies

which is actually the first-order necessary condition as discussed in Lemma 5.2. If the fixed point is found, it remains to show $\lambda_{d+1}(\bm{\Lambda}^{\infty}-\bm{A})>0$ and $(\bm{\Lambda}^{\infty}-\bm{A})\bm{R}^{(\infty)}=0$ in order to confirm $\bm{R}^{(\infty)}(\bm{R}^{(\infty)})^{\top}$ is the optimal solution to (SDP). The iteration stops when

In this experiment, we let $d=3$ or 5 and $\sigma=\kappa\sqrt{\frac{n}{d}}$. The parameters $(\kappa,n)$ are set to be $0\leq\kappa\leq 0.6$ and $100\leq n\leq 1000$. For each pair of $(\kappa,n)$, we run 20 instances and calculate the proportion of successful cases. From Figure 2, we see that if $\kappa<0.35$, the SDP is tight, i.e., it recovers the global minimizer to the least squares objective function. The phase transition plot does not depend heavily on the parameter $d$. This confirms our conjecture that $\kappa<1/2$ (modulo a log factor), the SDP relaxation is tight.

2 Phase transition plot for nonconvex low-rank optimization

Instead of applying Riemannian gradient method to (BM), we employ projected power method to show how the convergence depends on the noise level. Here the power method is viewed as projected gradient ascent method. We randomly initialize each $\bm{S}_{i}^{(0)}$ by creating a $d\times p$ Gaussian random matrix and extracting the random row space via QR decomposition. Then we perform

and the projection operator $\mathcal{P}$ is defined in (4.1).

After the iterates stabilize, we use (4.2) to verify the global optimality and tightness of the solution. Here we set $p=2d$ and for each pair of $\kappa$ and $n$, we still run 20 experiments and calculate the proportion of successful instances. Compared with Figure 2, Figure 3 provides highly similar phase transition plots for both $d=3$ and $d=5$. This is a strong indicator that the objective function is likely to have a benign landscape even if $\sigma=\Omega(\sqrt{nd^{-1}})$, which is much more optimistic than our current theoretical bound.

Proofs

The proof consists of several sections and some parts are rather technical. Thus we provide a roadmap of the proof here. For both the analysis of convex relaxation and the Burer-Monteiro factorization, the key is to analyze the objective function $f(\bm{S})$ defined in (BM) for $\bm{S}\in\operatorname{St}(d,p)^{\otimes n}$. Our analysis consists of several steps:

For (BM), we first provide a sufficient condition to certify the global optimality and tightness of $\bm{S}$ by using the duality theory in convex optimization. This is given in Proposition 5.1.

We show that $\bm{S}$ is the global maximizer of (BM) if $\bm{S}$ is a second-order critical point and is sufficiently close to the fully synchronized state, i.e., $\bm{S}_{i}=\bm{S}_{j},\forall i\neq j$. Moreover, the rank of $\bm{S}$ equals $d$ and thus it is tight. This leads to Proposition 5.4.

For convex relaxation, we show that the global maximizer of (BM) must be highly aligned with the fully synchronized state, see Proposition 5.6; for the Burer-Monteiro approach, we prove that all the second order critical points (SOCP) of (BM) must be close to the fully synchronized state, as shown in the Proposition 5.7.

Combining all the supporting results together finishes the proof.

The idea of proof is mainly inspired by which focus on the $\hbox{\msbm{Z}}_{2}$- and angular synchronization. However, due to the non-commutativity of $O(d)$ for $d\geq 3$, several parts require quite different treatments. Now we present the first proposition which gives a sufficient condition to guarantee the global optimality and tightness, and establish the equivalence of the global maximizers among the three optimization programs (P), (SDP), and (BM). Without loss of generality, we assume $\bm{A}=\bm{Z}\bm{Z}^{\top}+\bm{\Delta}$, i.e., $\bm{A}_{ij}=\bm{I}_{d}+\bm{\Delta}_{ij}$, where $\bm{Z}^{\top}=[\bm{I}_{d},\cdots,\bm{I}_{d}]\in\hbox{\msbm{R}}^{d\times nd}$ from now on.

Let $\bm{\Lambda}$ be an $nd\times nd$ block diagonal matrix $\bm{\Lambda}=\operatorname{blkdiag}(\bm{\Lambda}_{11},\cdots,\bm{\Lambda}_{nn})$. Suppose $\bm{\Lambda}$ satisfies

for some $\bm{S}\in\operatorname{St}(d,p)^{\otimes n}$, then $\bm{S}\bm{S}^{\top}\in\hbox{\msbm{R}}^{nd\times nd}$ is a global optimal solution to the SDP relaxation (SDP). Moreover, $\bm{S}$ is the unique global optimal solution to (P) if the following additional rank assumption holds

The condition (5.1) provides a sufficient condition for $\bm{X}=\bm{S}\bm{S}^{\top}$ to be one global maximizer to (SDP) and (BM). The condition (5.2) characterizes when the solution $\bm{S}\in\hbox{\msbm{R}}^{p\times nd}$ is of rank $d$ and unique. In particular, if $\operatorname{rank}(\bm{S})=d$, then $\bm{S}$ is actually the global maximizer to (P).

The next step is to show all the second order critical points, i.e., those points whose Riemannian gradient equals 0 and Hessian is positive semidefinite, are actually global maximizers if they are close to the fully synchronized state. It suffices to show that those SOCPs satisfy the global optimality condition (5.1) and (5.2). In fact, if $\bm{S}$ is a first order critical point, we immediately have $(\bm{\Lambda}-\bm{A})\bm{S}=0$ for some block-diagonal matrix $\bm{\Lambda}\in\hbox{\msbm{R}}^{nd\times nd}.$

The first order critical point of $f(\bm{S})$ satisfies:

The proof of Lemma 5.2 is given in Section 5.2. Lemma 5.2 shows that $\bm{\Lambda}_{ii}$ depends on $\bm{S}$ and is completely determined by $(\bm{\Lambda}-\bm{A})\bm{S}=0$. As a result, it suffices to prove that $\bm{\Lambda}-\bm{A}\succeq 0$ for some second order critical points which obey the proximity condition, i.e., $\bm{S}$ is sufficiently close to $\bm{Z}.$ To quantify this closeness, we introduce the following distance: given any $\bm{S}\in\operatorname{St}(d,p)^{\otimes n}$, the distance between $\bm{S}$ and the fully synchronized state is defined by

where $(\bm{Z}\bm{Q})^{\top}=[\bm{Q}^{\top},\cdots,\bm{Q}^{\top}]\in\hbox{\msbm{R}}^{p\times nd}$. For the rest of the paper, we will let $\bm{Q}$ be the $d\times p$ partial orthogonal matrix which minimizes (5.4). In fact, the minimizer equals $\bm{Q}=\mathcal{P}(\bm{Z}^{\top}\bm{S})$ where $\bm{Z}^{\top}\bm{S}=\sum_{j=1}^{n}\bm{S}_{j}\in\hbox{\msbm{R}}^{d\times p}$ and $\mathcal{P}(\cdot)$ is defined in (4.1).

A feasible solution $\bm{S}\in\hbox{\msbm{R}}^{p\times nd}\in\operatorname{St}(d,p)^{\otimes n}$ satisfies the proximity condition if

The next Proposition is the core of the whole proof, stating that any SOCPs satisfying the proximity condition (5.5) are global maximizers to (P) and (SDP).

For a second order critical point $\bm{S}$ satisfying (5.5), it is the unique global maximizer to both (P) and (SDP) if

In other words, the global optimality of $\bm{S}$ is guaranteed by

Proposition 5.4 provides a simple criterion to verify a near-fully synchronized state is the global optimal solution. However, the estimation of $\max_{1\leq i\leq n}\left\|\sum_{j\neq i}\bm{\Delta}_{ij}\bm{S}_{j}\right\|_{\operatorname{op}}$ is not tight which leads to the suboptimal bound in the main theorems. The major difficulty results from the complicated statistical dependence between $\bm{\Delta}$ and any second-order critical points $\bm{S}$. This is well worth further investigation for $O(d)$.

Now we present two propositions which demonstrate that any global maximizers and second-order critical points to (BM) satisfy (5.5) for some $\delta>0$.

For the tightness of SDP relaxation, we show that the global maximizer to (P) must satisfy (5.5) with $\delta=4$.

This proposition essentially ensures that any global maximizer to (BM) is close to the fully synchronized state and its distance depends on the noise strength.

(ii) Low-rank approach:

For the Burer-Monteiro approach, we prove that if $p\geq 2d+1$, all the local maximizers of (BM) satisfy (5.5) with $\delta$ which depends on $p$, $d$, and $\gamma$.

Suppose $p\geq 2d+1$. All the second-order critical points $\bm{S}$ of $f(\bm{S})$ in (BM) satisfy

and $\operatorname{Tr}_{d}(\bm{\Delta})=[\operatorname{Tr}(\bm{\Delta}_{ij})]_{ij}\in\hbox{\msbm{R}}^{n\times n}$ denotes the partial trace of $\bm{\Delta}.$

If $\bm{\Delta}$ is a symmetric Gaussian random matrix, then $\operatorname{Tr}_{d}(\bm{\Delta})$ is an $n\times n$ Gaussian random matrix whose entry is $\mathcal{N}(0,d)$ and $\|\operatorname{Tr}_{d}(\bm{\Delta})\|_{\operatorname{op}}=(1+o(1))\|\bm{\Delta}\|_{\operatorname{op}}$ holds.

We defer the proof of Proposition 5.1, 5.4, 5.6 and 5.7 to Section 5.3, 5.4, 5.5 and 5.6 respectively. Now we provide a proof of Theorem 3.1 and 3.3 by using the aforementioned propositions.

To prove the tightness of convex relaxation, we first consider the global maximizer to (BM) which is also a second-order critical point. By Proposition 5.6, we have $d_{F}(\bm{S},\bm{Z})\leq\delta\sqrt{n^{-1}d}\|\bm{\Delta}\|_{\operatorname{op}}$ with $\delta=4.$ With Proposition 5.4, we immediately have Theorem 3.1. ∎

To analyze the landscape of (BM), we invoke Proposition 5.7 which states that all the second-order critical points (SOCP) are essentially close to the fully synchronized state. Now it suffices to show that all SOCPs are global maximizers to (SDP) and (P) and the global maximizer is unique under the assumption of Theorem 3.3. This is fortunately guaranteed by Proposition 5.4. ∎

2 Riemannian gradient and Hessian matrix

We start with analyzing the SOCPs of $f(\bm{S})$ by first computing its Riemannian gradient and Hessian. The calculation involves the tangent space at $\bm{S}_{i}\in\operatorname{St}(d,p)$ which is given by

In other words, $\bm{S}_{i}\bm{Y}_{i}^{\top}$ is an anti-symmetric matrix if $\bm{Y}_{i}\in\hbox{\msbm{R}}^{d\times p}$ is an element in the tangent space.

Recall the objective function $f(\bm{S})=\sum_{i=1}^{n}\sum_{j=1}^{n}\langle\bm{S}_{i},\bm{A}_{ij}\bm{S}_{j}\rangle$ in (BM) where $\bm{S}_{i}\in\operatorname{St}(d,p)$. We take the gradient w.r.t. $\bm{S}_{i}$ in the Euclidean space.

The Riemannian gradient w.r.t. $\bm{S}_{i}$ is

by projecting $\frac{\partial f}{\partial\bm{S}_{i}}$ onto the tangent space $T_{\bm{S}_{i}}({\cal M})$ at $\bm{S}$, as shown in [3, Equation (3.35)]:

where $\bm{\Pi}\in\hbox{\msbm{R}}^{d\times p}$ and the matrix manifold ${\cal M}$ is $\operatorname{St}(d,p).$

Setting $\nabla_{\bm{S}_{i}}f=0$ gives $\bm{\Lambda}_{ii}$ in (5.3) and

In other words, $(\bm{\Lambda}-\bm{A})\bm{S}=0$ where $\bm{\Lambda}=\text{blkdiag}(\bm{\Lambda}_{11},\cdots,\bm{\Lambda}_{nn}).$ ∎

Next, we compute the Riemannian Hessian and prove that $\bm{\Lambda}\succeq 0$ for any second order critical point.

The quadratic form associated to the Hessian matrix of (BM) is

where $\dot{\bm{S}}^{\top}=[\dot{\bm{S}}_{1}^{\top},\cdots,\dot{\bm{S}}_{n}^{\top}]\in\hbox{\msbm{R}}^{p\times nd}$ and $\dot{\bm{S}}_{i}\in\hbox{\msbm{R}}^{d\times p}$ is an element on the tangent space of Stiefel manifold at $\bm{S}_{i}.$ In other words, if $\bm{S}$ is a second order critical point, it must satisfy:

Recall the Riemannian gradient w.r.t. $\bm{S}_{i}$ is given by

Let $\dot{\bm{S}}_{i}$ be a matrix on the tangent space at $\bm{S}_{i}$:

where $(\bm{S}+t\dot{\bm{S}}_{i})^{\top}=[\bm{S}_{1}^{\top},\cdots,(\bm{S}_{i}+t\dot{\bm{S}}_{i})^{\top},\cdots,\bm{S}_{n}^{\top}]$ and $\bm{S}_{i}\bm{S}_{i}^{\top}=\bm{I}_{d}.$ As a result, the quadratic form associated to the Riemannian Hessian is

where $\bm{S}_{i}\dot{\bm{S}}_{i}^{\top}+\dot{\bm{S}}_{i}\bm{S}_{i}^{\top}=0$ since $\dot{\bm{S}}_{i}$ is on $T_{\bm{S}_{i}}({\cal M})$.

For the mixed partial derivative, we have

Taking the sum of $\dot{\bm{S}}_{i}:\nabla^{2}_{\partial\bm{S}_{i}\partial\bm{S}_{j}}f(\bm{S}):\dot{\bm{S}}_{j}$ over $(i,j)$ gives

If $\bm{S}$ is a local maximizer of (BM), then $\dot{\bm{S}}:\nabla^{2}_{\partial\bm{S}\partial\bm{S}}f:\dot{\bm{S}}\leq 0$ holds for any $\dot{\bm{S}}\in(T_{\bm{S}_{i}}({\cal M}))^{\otimes n}.$ ∎

Suppose $\bm{S}$ is a local maximizer of (BM), then (5.10) implies that

Does it imply that $\bm{\Lambda}_{ii}\succeq\bm{I}_{d}$? The answer is yes if $p>d$. However, this is not longer true if $p=d.$ For $p=d$, we are only able to prove that the sum of the smallest two eigenvalues is nonnegative.

Suppose $\bm{S}$ is a local maximizer, then it holds

Note that $\bm{S}_{i}\in\hbox{\msbm{R}}^{d\times p}$ with $p>d$ is a “fat” matrix. It means we can always find $\bm{v}_{i}\in\hbox{\msbm{R}}^{p}$ which is perpendicular to all rows of $\bm{S}_{i}$, i.e., $\bm{S}_{i}\bm{v}_{i}=0$. Without loss of generality, we assume $\bm{v}_{i}$ is a unit vector. Now we construct $\dot{\bm{S}}_{i}$ in the following form:

where $\bm{u}_{i}$ is an arbitrary vector in $\hbox{\msbm{R}}^{d}.$ It is easy to verify that

which means $\dot{\bm{S}}_{i}$ is indeed an element in the tangent space of $\operatorname{St}(d,p)$ at $\bm{S}_{i}.$

which implies that $\bm{\Lambda}_{ii}-\bm{I}_{d}\succeq 0$ and $\bm{\Lambda}_{ii}\succeq\bm{I}_{d}.$ ∎

3 Certifying global optimality via dual certificate

To guarantee the global optimality of a feasible solution, we will employ the standard tools from the literature in compressive sensing and low-rank matrix recovery. The core part is to construct the dual certificate which confirms that the proposed feasible solution and the dual certificate yield strong duality.

We start from the convex optimization (SDP) and derive its dual program. First introduce the symmetric matrix $\bm{\Pi}_{ii}\in\hbox{\msbm{R}}^{d\times d}$ as the dual variable corresponding to the constraint $\bm{X}_{ii}=\bm{I}_{d}$ and then get the Lagrangian function. Here we switch from maximization to minimization in (SDP) by changing the sign in the objective function.

where $\bm{\Pi}=\operatorname{blkdiag}(\bm{\Pi}_{11},\cdots,\bm{\Pi}_{nn})\in\hbox{\msbm{R}}^{nd\times nd}$ and $\bm{X}\succeq 0$. If $\bm{\Pi}-\bm{A}$ is not positive semidefinite, taking the infimum w.r.t. $\bm{X}\succeq 0$ for the Lagrangian function gives negative infinity. Thus we require $\bm{\Pi}-\bm{A}\succeq 0$:

As a result, the dual program of (SDP) is equivalent to

Weak duality in convex optimization implies that $\operatorname{Tr}(\bm{\Pi})\geq\langle\bm{A},\bm{X}\rangle$. Moreover, $(\bm{X},\bm{\Pi})$ is a primal-dual optimal solution (not necessarily unique) if the complementary slackness holds

since (5.11) implies strong duality, i.e., $\operatorname{Tr}(\bm{\Pi})=\langle\bm{A},\bm{X}\rangle$ since $\bm{X}_{ii}=\bm{I}_{d}.$ In fact, this condition (5.11) is equivalent to

because both $\bm{\Pi}-\bm{A}$ and $\bm{X}$ are positive semidefinite.

Let $\bm{S}\in\hbox{\msbm{R}}^{nd\times p}$ be a feasible solution. Suppose there exists an $nd\times nd$ block diagonal matrix $\bm{\Lambda}$ and satisfies (5.1). The global optimality of $\bm{X}=\bm{S}\bm{S}^{\top}$ follows directly from (5.1) and (5.12). In addition, if the rank of $\bm{\Pi}-\bm{A}$ is $(n-1)d$, then the global optimizer to (SDP) is exactly rank-$d$. This is due to $(\bm{\Pi}-\bm{A})\bm{X}=0$, implying that the rank of $\bm{X}$ is at most $d$ but $\bm{X}_{ii}=\bm{I}_{d}$ guarantees $\operatorname{rank}(\bm{X})\geq d.$ This results in the tightness of (SDP) since the global optimal solution to the SDP is exactly rank-$d$ and thus must be the global optimal solution to (P) as well.

Now we prove that if $\operatorname{rank}(\bm{\Pi}-\bm{A})=(n-1)d$, then $\bm{X}$ is the unique maximizer. Let’s prove it by contradiction. If not, then there exists another global maximizer $\widetilde{\bm{X}}$ such that $\langle\bm{A},\widetilde{\bm{X}}\rangle=\operatorname{Tr}(\bm{\Pi})=\langle\bm{\Pi},\widetilde{\bm{X}}\rangle$ since the feasible solution $\bm{X}$ and $\widetilde{\bm{X}}$ achieve the same primal value due to the linearity of the objective function:

Since $\operatorname{rank}(\bm{\Pi}-\bm{A})=(n-1)d$, thus $\operatorname{rank}(\widetilde{\bm{X}})\leq d$. Note that each diagonal block is $\bm{I}_{d}$ and it implies $\operatorname{rank}(\widetilde{\bm{X}})=d$. This proves that $\widetilde{\bm{X}}=\bm{X}$ holds (modulo a global rotation in the column space) since $\bm{X}$ and $\widetilde{\bm{X}}$ are determined uniquely by the null space of $\bm{\Pi}-\bm{A}.$ ∎

Proposition 5.1 indicates that in order to show that a first-order critical point of $f(\bm{S})$ is the unique global maximizer to (P), it suffices to guarantee $\bm{\Lambda}-\bm{A}\succeq 0$ and $\lambda_{d+1}(\bm{\Lambda}-\bm{A})>0$. This is equivalent to $\operatorname{rank}(\bm{\Lambda}-\bm{A})=(n-1)d$ here since the first order necessary condition implies $(\bm{\Lambda}-\bm{A})\bm{S}=0$ for $\bm{\Lambda}$ defined in (5.3) which means at least $d$ eigenvalues of $\bm{\Lambda}-\bm{A}$ are zero. Now we can see that the key is to ensure $\bm{\Lambda}-\bm{A}\succeq 0$ for some first-order critical point $\bm{S}$ (i.e., those critical points which satisfy the proximity condition). Define the certificate matrix

for any given $\bm{S}.$ From the definition, we know that any first-order critical points satisfy $\bm{C}\bm{S}=0.$

4 Proof of Proposition 5.4

Suppose the proximity condition (5.5) holds, we have

This Lemma says that if $\bm{S}$ is sufficiently close to $\bm{Z}$, then $\bm{Z}^{\top}\bm{S}$ is approximately an identity.

where $\|\bm{S}\|_{F}^{2}=\|\bm{Z}\bm{Q}\|_{F}^{2}=nd.$ Note that

where $\|\bm{Z}^{\top}\bm{S}\|_{*}$ denotes the nuclear norm of $\bm{Z}^{\top}\bm{S}\in\hbox{\msbm{R}}^{d\times p}.$ The maximum is assumed if $\bm{Q}=\bm{U}\bm{V}^{\top}$ where $\bm{U}\in\hbox{\msbm{R}}^{d\times d}$ and $\bm{V}\in\hbox{\msbm{R}}^{p\times d}$ are the left and right singular vectors of $\bm{Z}^{\top}\bm{S}.$

Note that the largest singular value of $\bm{Z}^{\top}\bm{S}$ is at most $n$ which trivially follows from triangle inequality. For the smallest singular value of $\bm{Z}^{\top}\bm{S}$, we use the following inequality

which implies $\sigma_{\min}(\bm{Z}^{\top}\bm{S})\geq n-2\delta^{2}n^{-1}d\|\bm{\Delta}\|^{2}_{\operatorname{op}}.$ ∎

Suppose a second-order critical point $\bm{S}$ satisfies the proximity condition. Then

where $\bm{\Delta}_{i}$ is the $i$th block column of $\bm{\Delta}.$

Suppose $\bm{S}$ is a SOCP with $d_{F}(\bm{S},\bm{Z})\leq\delta\sqrt{n^{-1}d}\|\bm{\Delta}\|_{\operatorname{op}}$. We have

from Lemma 5.11 and 5.10. The first order necessary condition (5.9) implies

where $\bm{S}_{i}\bm{S}_{i}^{\top}=\bm{I}_{d}$. Therefore, the singular values of $\sum_{j=1}^{n}\bm{A}_{ij}\bm{S}_{j}$ and $\bm{\Lambda}_{ii}$ are the same. Moreover, due to the symmetry and $\bm{\Lambda}_{ii}\succeq 0$, its eigenvalues and singular values match:

where the lower bound is independent of $i$. The key is to bound $\left\|\sum_{j\neq i}\bm{\Delta}_{ij}\bm{S}_{j}\right\|_{\operatorname{op}}$ which is suboptimal in this analysis.

where $\bm{\Delta}_{i}^{\top}\in\hbox{\msbm{R}}^{d\times nd}$ is the $i$th row block of $\bm{\Delta}.$ The operator norm of $\|\bm{\Delta}_{i}(\bm{S}-\bm{Z}\bm{Q})\|_{\operatorname{op}}$ is bounded by

Taking the maximum over $1\leq i\leq n$ gives the desired result. ∎

With this supporting lemma, we are ready to prove Proposition 5.4.

The proof consists of two steps: first to show that $\bm{S}$ is a global maximizer to (BM) by showing that $\bm{\Lambda}-\bm{A}\succeq 0$; then prove that $\bm{S}$ is exactly rank-$d$.

Step One: show that $\bm{S}$ is a global maximizer

Remember that $\bm{C}\bm{S}=0$ if $\bm{S}\in\hbox{\msbm{R}}^{nd\times p}$ is a critical point of $f.$ Thus, to show $\bm{C}$ is positive semidefinite at critical point $\bm{S}$, it suffices to test $\bm{u}^{\top}\bm{C}\bm{u}\geq 0$ for all $\bm{u}\in\hbox{\msbm{R}}^{nd\times 1}$ which is perpendicular to each column of $\bm{S}$:

where $\bm{u}_{j}\in\hbox{\msbm{R}}^{d}$ is the $j$th block of $\bm{u}$, $1\leq j\leq n.$

Note that $\lambda_{\min}(\bm{\Lambda})=\min_{1\leq i\leq n}\lambda_{\min}(\bm{\Lambda}_{ii})$ which is given by Lemma 5.12. For $\bm{u}^{\top}\bm{Z}\bm{Z}^{\top}\bm{u}$, we use $\sum_{j=1}^{n}\bm{S}_{j}^{\top}\bm{u}_{j}=0$ and

where the last inequality uses the proximity condition. For $\lambda_{\min}(\bm{\Lambda})$, we apply Lemma 5.12 and immediately arrive at:

We have shown the solution to the Burer-Monteiro approach is equivalent to that of the SDP. Now, we will prove that the solution to the Burer-Monteiro approach is exactly rank $d$.

How to show that $\bm{C}$ is rank-$d$ deficient? It suffices to bound the dimension of its null space. In a more compact version, we have

It suffices to provide a lower bound of $\operatorname{rank}(\bm{\Lambda}-\bm{\Delta})$. In particular, we aim to show that $\bm{\Lambda}-\bm{\Delta}$ is full-rank by

Then we have $\operatorname{null}(\bm{C})\leq nd+d-\operatorname{rank}(\bm{\Lambda}-\bm{\Delta})=nd+d-nd=d.$ If $\bm{C}$ is of rank $nd-d$, then $\operatorname{rank}(\bm{S})=d$. Thus the global optimum is the same as that of (SDP) and (P). ∎

5 Proof of Proposition 5.6

It is unclear how to characterize the global maximizer to the objective function (BM). However, the global maximizer must be a 2nd critical point whose corresponding objective function value is greater than $f(\bm{S})$ evaluated at the fully synchronous state $\bm{S}_{i}=\bm{S}_{j}.$

Throughout our discussion, we let $\bm{Q}$ be the minimizer to $\min_{\bm{Q}\in\operatorname{St}(d,p)}\|\bm{S}-\bm{Z}\bm{Q}\|_{F}$. Given $\bm{S}$ which satisfies $f(\bm{S})\geq f(\bm{Z}\bm{Q})$, we have

Note that $\langle\bm{Z}\bm{Z}^{\top},\bm{Z}\bm{Z}^{\top}\rangle=n^{2}d$ and $\langle\bm{Z}\bm{Z}^{\top},\bm{S}\bm{S}^{\top}\rangle=\|\bm{Z}^{\top}\bm{S}\|_{F}^{2}.$ This gives

where $d_{F}(\bm{S},\bm{Z})=\|\bm{S}-\bm{Z}\bm{Q}\|_{F}$ and

In fact, $n^{2}d-\|\bm{Z}^{\top}\bm{S}\|_{F}^{2}$ is well controlled by $d_{F}(\bm{S},\bm{Z}):$

where $\sigma_{i}(\bm{Z}^{\top}\bm{S})$ is the $i$th largest singular value of $\bm{Z}^{\top}\bm{S}.$ On the other hand, it holds that

Remember that $0\leq\sigma_{i}(\bm{Z}^{\top}\bm{S})\leq n$ due to the orthogonality of each $\bm{S}_{i}$. Therefore, we have

which follows from (5.15). Substitute it back into (5.14), and we get

Immediately, we have the following estimate of $d(\bm{S},\bm{Z}):$

where $\|\bm{S}+\bm{Z}\bm{Q}\|_{F}\leq 2\sqrt{nd}$ follows from $\|\bm{S}\|_{F}=\|\bm{Z}\|_{F}=\sqrt{nd}.$ ∎

6 Proof of Proposition 5.7

This section is devoted to proving all the SOCPs are highly aligned with the fully synchronized state. The proof follows from two steps: (a) using the second order necessary condition to show that all SOCPs have a large objective function value; (b) combining (a) with the first order necessary condition leads to Proposition 5.7.

All the second order critical points $\bm{S}\in\operatorname{St}(d,p)^{\otimes n}$ must satisfy:

Suppose the noise is zero, then $(p-d)\|\bm{Z}^{\top}\bm{S}\|_{F}^{2}\geq(p-2d)n^{2}d+\|\bm{S}\bm{S}^{\top}\|_{F}^{2}d$ holds. It means that $\|\bm{Z}^{\top}\bm{S}\|_{F}^{2}$ is quite close to $n^{2}d$, i.e., $\{\bm{S}_{i}\}_{i=1}^{n}$ are highly aligned, if $p$ is reasonably large. The proof idea of this lemma can also be found in .

Let’s first consider the second-order necessary condition (5.10):

for all $\dot{\bm{S}}_{i}$ on the tangent space of $\operatorname{St}(p,d)$ at $\bm{S}_{i}$ where $\bm{\Lambda}_{ii}=\frac{1}{2}\sum_{j=1}^{n}(\bm{S}_{i}\bm{S}_{j}^{\top}\bm{A}_{ji}+\bm{A}_{ij}\bm{S}_{j}\bm{S}_{i}^{\top}).$ Now we pick $\dot{\bm{S}}_{i}$ as

where $\bm{\Phi}\in\hbox{\msbm{R}}^{d\times p}$ is a Gaussian random matrix, i.e., each entry in $\bm{\Phi}$ is an i.i.d. $\mathcal{N}(0,1)$ random variable. It is easy to verify that $\dot{\bm{S}}_{i}$ is indeed on the tangent space since $\bm{S}_{i}\dot{\bm{S}}_{i}^{\top}=0.$ By taking the expectation w.r.t. $\bm{\Phi}$, the inequality still holds:

It suffices to compute $\operatorname{\hbox{\msbm{E}}}\dot{\bm{S}}_{i}\dot{\bm{S}}_{j}^{\top}$ now.

where $d=\operatorname{Tr}(\bm{S}_{i}\bm{S}_{i}^{\top})$. Therefore, we have

where $\bm{A}_{ij}=\bm{I}_{d}+\bm{\Delta}_{ij}.$ From the definition of $\bm{\Lambda}_{ii}$, the left side of (5.17) equal to

Plugging the estimation back to (5.17) results in

By separating the signal from the noise, we have

where $\langle\bm{\Delta},\bm{Z}\bm{Z}^{\top}\rangle=\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{Tr}(\bm{\Delta}_{ij}).$ ∎

Any first-order critical point satisfies:

Note that the first-order necessary condition is

which implies $\sum_{j=1}\bm{S}_{i}\bm{S}_{j}^{\top}\bm{A}_{ji}=\sum_{j=1}\bm{A}_{ij}\bm{S}_{j}\bm{S}_{i}^{\top}$ by applying $\bm{S}_{i}^{\top}$ to the equation above. Then it reduces to

By separating the signal from the noise, we have

where $\|\bm{I}_{p}-\bm{S}_{i}^{\top}\bm{S}_{i}\|_{\operatorname{op}}=1.$ Taking the sum over $1\leq i\leq n$ gives

where $\bm{S}^{\top}\bm{S}=\sum_{i=1}^{n}\bm{S}_{i}^{\top}\bm{S}_{i}.$ Thus

where $\bm{Z}\bm{Z}^{\top}=\bm{J}_{n}\otimes\bm{I}_{d}\preceq n\bm{I}_{nd}.$ ∎

For any matrix $\bm{X}\in\hbox{\msbm{R}}^{nd\times nd}$, it holds that

where $\bm{S}\in\hbox{\msbm{R}}^{p\times nd}$ and $[\bm{S}\bm{S}^{\top}]_{ii}=\bm{I}_{d}.$ Here $``\circ"$ stands for the Hadamard product of two matrices.

where $\operatorname{diag}(\bm{S}\bm{S}^{\top})=\bm{I}_{nd}.$ Thus we have shown $\|\bm{X}\circ\bm{S}\bm{S}^{\top}\|_{\operatorname{op}}\leq\|\bm{X}\|_{\operatorname{op}}$. ∎

Lemma 5.13 and 5.14 imply that all the SOCPs of (BM) satisfy

where $\|\bm{S}\bm{S}^{\top}\|_{F}^{2}\geq\left\|\bm{Z}^{\top}\bm{S}\right\|_{F}^{2}-\frac{1}{n}\|\bm{\Delta}\bm{S}\|_{F}^{2}.$ This is equivalent to

Estimation of $|T_{1}|$ and $|T_{3}|$: For $T_{1}$, we simply have

Estimation of $|T_{2}|$: Define a new matrix $\widetilde{\bm{\Delta}}:=\operatorname{Tr}_{d}(\bm{\Delta})\otimes\bm{J}_{d}$ whose $(i,j)$-entry block is $\operatorname{Tr}(\bm{\Delta}_{ij})\bm{J}_{d}$ and $\|\widetilde{\bm{\Delta}}\|_{\operatorname{op}}=\|\operatorname{Tr}_{d}(\bm{\Delta})\|_{\operatorname{op}}d$. Note that

where $(\bm{S}\bm{S}^{\top}\circ\bm{S}\bm{S}^{\top})_{ij}=\bm{S}_{i}\bm{S}_{j}^{\top}\circ\bm{S}_{i}\bm{S}_{j}^{\top}$, $(\bm{Z}\bm{Z}^{\top}\circ\bm{Z}\bm{Z}^{\top})_{ij}=\bm{I}_{d}$, and $\|\bm{S}_{i}\bm{S}_{j}^{\top}\|_{F}^{2}=\langle\bm{S}_{i}\bm{S}_{j}^{\top},\bm{S}_{i}\bm{S}_{j}^{\top}\rangle=\langle\bm{S}_{i}\bm{S}_{j}^{\top}\circ\bm{S}_{i}\bm{S}_{j}^{\top},\bm{J}_{d}\rangle$. As a result, we have

Now the goal is to get an upper bound of $\|\widetilde{\bm{\Delta}}\circ(\bm{S}\bm{S}^{\top}+\bm{Z}\bm{Z}^{\top})\|_{\operatorname{op}}$. In fact, it holds

where the second inequality follows from Lemma 5.15 and $\|\widetilde{\bm{\Delta}}\|_{\operatorname{op}}=d\|\operatorname{Tr}_{d}(\bm{\Delta})\|_{\operatorname{op}}$. Therefore,

where $\gamma=\frac{\|\operatorname{Tr}(\bm{\Delta})\|_{\operatorname{op}}}{\|\bm{\Delta}\|_{\operatorname{op}}}\vee 1$ is defined in (3.1). Note that $n^{2}d-\|\bm{Z}^{\top}\bm{S}\|_{F}^{2}\geq 2^{-1}nd_{F}^{2}(\bm{S},\bm{Z})$ in (5.16). Thus for $p>2d$, we have

where $(p-d+2\gamma d)^{2}\geq(p+d)^{2}\geq 2d(p-2d)$ holds for $p\geq 2d+1$ and $\gamma\geq 1.$ ∎

7 Proof of Theorem 3.2 and 3.4

Proposition 5.4 implies that it suffices to prove

where $\max_{1\leq i\leq n}\|\bm{\Delta}_{i}\|_{\operatorname{op}}\leq\|\bm{\Delta}\|_{\operatorname{op}}.$ Now we will estimate $\|\bm{\Delta}\|_{\operatorname{op}}$ and $\max_{1\leq i\leq n}\|\bm{\Delta}_{i}^{\top}\bm{Z}\|_{\operatorname{op}}$ for $\bm{\Delta}=\sigma\bm{W}$ where $\bm{W}$ is an $nd\times nd$ symmetric Gaussian random matrix.

The proof is straightforward: to show that (5.18) holds for some $\delta$ in both convex and nonconvex cases. If $\bm{\Delta}=\sigma\bm{W}$ where $\bm{W}$ is a Gaussian random matrix, it holds that

with high probability at least $1-e^{-nd/2}$ according to [7, Proposition 3.3]. For $\bm{\Delta}_{i}^{\top}\bm{Z}$, we have

Theorem 4.4.5 in implies that the Gaussian matrix $\bm{\Delta}_{i}^{\top}\bm{Z}$ is bounded by

with probability at least $1-2n^{-2}$. By taking the union bound over all $1\leq i\leq n$, we have

with probability at least $1-2n^{-1}$. In the convex relaxation, we have $\delta=4$. Then the right hand of (5.18) is bounded by

where $\delta=4.$ The leading term is of order $\sigma^{2}\sqrt{n}d^{3/2}$ and thus $\sigma<C_{0}n^{1/4}d^{-3/4}$ guarantees the tightness of SDP.

For Burer-Monteiro approach, it suffices to estimate $\gamma$ in (3.1). The partial trace $\operatorname{Tr}_{d}(\bm{\Delta})$ is essentially equal to $\sigma\sqrt{d}\bm{W}_{GOE,n}$, which implies

with probability at least $1-e^{-n/2}$ and

where $\delta=(2+\sqrt{5})(p+d)(p-2d)^{-1}\gamma.$

Thus the right hand of (5.18) is bounded by

for some universal constant $C_{1}^{\prime}.$ The leading order term is $\sigma^{2}(p-2d)^{-1}(p+d)d\sqrt{nd}$ which implies that (5.18) holds if

for some small constant $C_{0}$. This means $\sigma^{2}<C_{0}n^{1/2}(p-2d)d^{-3/2}(p+d)^{-1}$ ensures that the optimization landscape of (BM) is benign. ∎

References