A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group

Introduction

In many real-world estimation problems, the signals of interest, which are commonly referred to as ground truths, are constrained to lie in a group.Recall that a group is a pair $(\mathcal{G},\ast)$, where $\mathcal{G}$ is a set and $\ast$ is a binary operation on $\mathcal{G}$, such that (i) $\ast$ is associative (i.e., $g_{1}\ast(g_{2}\ast g_{3})=(g_{1}\ast g_{2})\ast g_{3}$ for all $g_{1},g_{2},g_{3}\in\mathcal{G}$); (ii) there exists an identity element ${\rm id}\in\mathcal{G}$ (i.e., $g\ast{\rm id}={\rm id}\ast g=g$ for all $g\in\mathcal{G}$); (iii) for each $g\in\mathcal{G}$, there exists an inverse element $g^{-1}$ of $g$ (i.e., $g\ast g^{-1}=g^{-1}\ast g={\rm id}$). For simplicity, we shall write $g_{1}g_{2}$ for $g_{1}\ast g_{2}$, where $g_{1},g_{2}\in\mathcal{G}$. Also, we shall abuse terminology and refer to $\mathcal{G}$ as the group. One such example is the group synchronization problem (or simply synchronization problem), in which the ground truth takes the form $G^{*}=(G^{*}_{1},\dots,G^{*}_{n})$ with $G^{*}_{1},\ldots,G^{*}_{n}$ being elements of a group $\mathcal{G}$ and is to be estimated from noisy measurements of a subset of all pairwise ratios of the form $G^{*}_{i}{G^{*}_{j}}^{-1}$ that are computed using the binary operation on $\mathcal{G}$. Synchronization problems have found applications across a wide range of areas, such as social science, distributed network, signal processing, computer vision, robotics, structural biology, computational genomics, and machine learning, and hence have gained much attention over the past decade. Indeed, group synchronization problems often appear as sub-tasks in many important problems from the above areas, including community detection where $\mathcal{G}$ is the Boolean group; ranking and distributed clock synchronization where $\mathcal{G}$ is the group of 2D rotations; sensor network localization and cryo-electron microscopy where $\mathcal{G}$ is the group of orthogonal matrices or special orthogonal matrices ; the pose graph estimation problem where $\mathcal{G}$ is the group of Euclidean motions; the haplotype phasing problem where $\mathcal{G}$ is the cyclic group (integers with modulo arithmetics); the multi-graph matching problem where $\mathcal{G}$ is the group of permutations. In most applications, after solving the synchronization problem, the estimated group elements will in turn be used to estimate another underlying signal, which is the ultimate target. In principle, one could estimate the underlying signal directly or jointly with the group elements. However, as pointed out in , estimating the signal given the group elements is a considerably easier task and can be addressed using well-developed techniques for inverse problems. This motivates us to focus on the synchronization problem.

Numerical approaches to synchronization problems are roughly divided into three categories: Spectral-type estimators, semidefinite programming (SDP) relaxations, and non-convex approaches. In the context of synchronization problems, a spectral-type estimator was first introduced in for phase synchronization (i.e., $\mathcal{G}$ is the group $\mathcal{SO}(2)$ of 2D rotations). It has later been generalized to synchronization problems over other subgroups of the orthogonal group (see ) and even general compact groups . The main cost of computing a spectral-type estimator comes in two parts. First, the eigenvectors corresponding to the first few eigenvalues of the graph connection Laplacian or a data matrix defined using the noisy observations are computed (see Sections 2 and 5.4 for details). Second, a certain rounding procedure is invoked to ensure that the returned estimator lies in the feasible set $\mathcal{G}^{n}$. The major advantages of spectral-type estimators are their low computational cost and ease of implementation.

In recent years, there have been attempts to solve the non-convex least squares formulation of the synchronization problem directly without relaxing it. Such a non-convex approach typically has two stages. In the first stage, a carefully designed initialization procedure is used to produce a point that is close enough to the ground truth. Then, in the second stage, an iterative procedure is used to refine the initial point. One procedure that is particularly suitable for the second stage is the generalized power method (GPM) . The idea of applying GPM to synchronization problems was first introduced in for phase synchronization and later further developed in for the joint alignment problem and in for the community detection problem. In addition, the analysis of GPM in for phase synchronization was sharpened in . The advantage of the GPM-based non-convex approach is that it is much faster and more scalable than the SDP relaxation approach, as each iteration of GPM involves only matrix-vector multiplications and projections onto the group $\mathcal{G}$. As we shall see later, these projections can be computed efficiently for many concrete groups $\mathcal{G}$ of practical relevance. Also, the GPM-based approach is easy to implement and requires no parameter tuning. It is worth noting that although spectral-type estimators have been shown to be already qualitatively optimal in certain settings , we have observed in our experiments that by refining a spectral-type estimator using GPM, the quality of the resulting estimator can be substantially better (see Section 7). In other words, we can greatly improve the performance of spectral-type estimators by paying a small amount of extra computational cost.

Interestingly, the procedures used to compute estimators of the ground truth can be viewed as approximation algorithms for the non-convex formulation of the synchronization problem at hand. For instance, it is known that the least squares formulation of synchronization over the Boolean group is equivalent to the MAX-CUT problem , while that of phase synchronization is equivalent to a complex quadratic maximization problem with unit modulus constraint . As such, the approximation accuracy of various least squares estimators (i.e., the gap between the objective value attained by the estimator in question and the optimal value of the formulation) can be determined, see, e.g., . However, since an optimal solution to the non-convex formulation is in general different from the ground truth, a more relevant and faithful measure of the quality of an estimator for a synchronization problem is the estimation error, which is defined as the deviation of the estimator from the ground truth. For synchronization over the special orthogonal group, the estimation error of various estimators has been studied in .

It should be mentioned that when $\mathcal{G}$ is the group of rotations (i.e., special orthogonal matrices), the synchronization problem is equivalent to the problem of multiple rotation averaging , and the GPM is also known as the Jacobi-type method [35, Section 7.4]. Moreover, various specialized algorithms are developed in the literature for multiple rotation averaging, such as the Weiszfeld algorithm. However, it is often difficult to extend the algorithm and/or its theory to a general subgroup of the orthogonal group. Since our paper focuses on algorithms for general subgroups, we do not go into the details of these specialized algorithms. We refer the interested reader to and the references therein.

Finally, we mention two relatively new yet effective approaches to general group synchronization problems, both of which fall into the category of message passing algorithms. First, an approximate message passing algorithm was derived in for solving synchronization over general compact groups. Based on ideas from statistical physics, the work provides a non-rigorous analysis on the asymptotic statistical guarantee of their algorithm in the large $n$ limit. Second, a powerful framework has recently been developed in for removing unreliable observations in the input data to general synchronization problems by leveraging a notion called cycle-edge consistency. It would be interesting to investigate both the theoretical and practical performance of our non-convex approach when combined with the framework in . We leave this as a future work.

In this paper, we consider synchronization problems over closed subgroups of the orthogonal group $\mathcal{O}(d)$, which include, e.g., the orthogonal group $\mathcal{O}(d)$ itself, the special orthogonal group $\mathcal{SO}(d)$, the permutation group $\mathcal{P}(d)$, and the cyclic group $\mathcal{Z}_{m}$ (see Section 2.1 for their definitions). We propose and analyze a non-convex approach for tackling this class of synchronization problems. Our main contribution is fivefold.

First, we derive a master theorem for the proposed non-convex approach. Under four assumptions that are respectively related to the subgroup, noise, measurement graph, and initialization, our master theorem establishes an upper bound on the estimation error of the iterates of GPM and hence provides performance guarantees for the proposed non-convex approach (see Theorem 1). The master theorem is applicable to general closed subgroups of the orthogonal group, measurement graphs, and noise. It also clearly reveals the roles played by these main components of a synchronization problem.

Second, we formulate two key geometric conditions on the subgroup that can be used to verify the assumptions in the master theorem. These conditions are closely related to the error-bound geometry of the subgroup, which is a classic notion in optimization and plays an important role in the analysis of various iterative methods. We also prove that the two geometric conditions hold for the orthogonal group, the special orthogonal group, the permutation group, and the cyclic group, which are all practically relevant in the context of group synchronization problems.

Third, we study random models of the measurement graph and noise. In particular, we show that if the measurement graph is the Erdős-Rényi random graph and the noise matrix is a random matrix with independent sub-Gaussian entries, then the assumptions on the measurement graph and noise in the master theorem will hold with high probability when the number $n$ of target group elements is sufficiently large. This result is useful since many well-known random variables are sub-Gaussian, including the Gaussian, uniform, Bernoulli, and any bounded random variables.

Fourth, we develop a novel spectral-type estimator, named the entropic spectral estimator, for our target class of synchronization problems. The entropic spectral estimator has an intimate connection to the classic geometric concept of metric entropy. We prove that under the above-mentioned geometric conditions and random models of the measurement graph and noise, the entropic spectral estimator will satisfy the assumption on the initialization of the non-convex approach with high probability.

Finally, through extensive numerical experiments, we study the empirical performance of our proposed non-convex approach on synchronization problems over several subgroups of the orthogonal group. The experiment results show that the proposed approach outperforms existing ones in terms of computational speed, scalability, and/or estimation error.

Although the idea of applying GPM to solve synchronization problems over closed subgroups of the orthogonal group $\mathcal{O}(d)$ is natural in view of our earlier discussion, due to the non-commutativity of $\mathcal{O}(d)$, many of the key steps in that rely on the commutativity of $\mathcal{SO}(2)$ break down. Hence, extending the theoretical results in to synchronization problems over general subgroups of $\mathcal{O}(d)$ is highly non-trivial. Furthermore, the measurement and noise settings in this paper are significantly more general than those considered in . It should also be pointed out that for cyclic synchronization $\mathcal{Z}_{m}$-sync, another non-convex approach was developed in . However, unlike the approach in , the dimension of the iterates and the computational cost of our approach do not increase with $m$. Therefore, our approach is arguably more efficient.

2 Organization

The rest of the paper is organized as follows. We formally introduce the group synchronization problem and some definitions related to it in Section 2. In Section 3, we propose a unified non-convex approach for solving synchronization problems over closed subgroups of the orthogonal group. We then prove a master theorem on the performance guarantee of the proposed approach in Section 4. In Section 5, we verify the conditions of the master theorem for various closed subgroups of the orthogonal group and standard random measurement graph and noise models. Lastly, we present results on the numerical performance of the proposed approach in Section 7 and conclude the paper in Section 8.

3 Notation

We use the following notation throughout the paper. For any $nd\times nd$ (resp. $nd\times d$) block matrix $Y$, we denote by $[Y]_{ij}$ (resp. $[Y]_{i}$) its $(ij)$-th (resp. $i$-th) $d\times d$ block. For any two matrices $X$ and $Y$, we denote their Kronecker product by $X\otimes Y$ and, if they have conformable dimensions, their inner product by $\langle X,Y\rangle=\operatorname{Tr}(X^{\top}Y)$. We use $\left\|{X}\right\|$ and $\left\|{X}\right\|_{F}$ to denote the operator norm and Frobenius norm of $X$, respectively. For any integer $k\geq 1$, we denote the $k\times k$ identity matrix by $I_{k}$. We use $c,c_{0},c_{1},\ldots$ to denote numerical constants in mathematical statements and proofs, whose values may change from appearance to appearance. For a graph with node set $[n]:=\{1,\dots,n\}$, we denote by $(i,j)$ the edge between nodes $i$ and $j$.

Group Synchronization

Let $d\geq 1$ be an integer. The basic objects in our study are the $d$-dimensional orthogonal group — i.e., the set of $d\times d$ orthogonal matrices

with matrix multiplication as the binary operation — and its closed subgroups — i.e., closed subsets of $\mathcal{O}(d)$ that form a group under matrix multiplication. These include many of the groups mentioned in Section 1, such as the orthogonal group $\mathcal{O}(d)$ itself (the Boolean group corresponds to $\mathcal{O}(1)=\{-1,+1\}$), the special orthogonal group

(which is a closed subgroup of $\mathcal{O}(2)$).

Given a closed subgroup $\mathcal{G}$ of the orthogonal group, the problem of group synchronization over $\mathcal{G}$, denoted by $\mathcal{G}$-sync, is to estimate the ground truth $G^{*}=(G_{1}^{*},\dots,G_{n}^{*})\in\mathcal{G}^{n}$ based on noisy observations of the pairwise ratios

Therefore, we can at best recover the target elements up to some unknown common transformation $Q\in\mathcal{G}$ from the right. This motivates us to define the estimation error $\varepsilon(G)$ of an estimator $G\in\mathcal{G}^{n}$ as

It is immediate from the definition that $\varepsilon(G)=\varepsilon(GQ^{\prime})$ for any $Q^{\prime}\in\mathcal{G}$.

The pair $([n],E)$ forms a graph, called the measurement graph of the synchronization problem $\mathcal{G}$-sync. There are various ways to model the noisy observations of the pairwise ratios. One way is to adopt the additive noise model

where $\{\Theta_{ij}:(i,j)\in E\}$ are the noise matrices. Such a model appears frequently in the group synchronization literature, see, e.g., . Another way is to adopt the multiplicative noise model

see, e.g., . A special case of this is the so-called outlier noise model, where $\Theta_{ij}$ ($(i,j)\in E$) is either a random element distributed uniformly (with respect to the Haar measure) over $\mathcal{G}$ or the identity element of $\mathcal{G}$. We will report numerical results of our proposed non-convex approach for both the additive and multiplicative noise models in Section 7.

Most existing works on computational approaches to synchronization problems assume that the noise matrices $\{\Theta_{ij}:(i,j)\in E\}$ are independent. We shall also make this assumption in our subsequent development. However, it is worth noting that such an assumption may not be ideal for recovery. Indeed, in applications such as cryo-electron microscopy , the noisy observations $\{C_{ij}:(i,j)\in E\}$ are usually estimated as maximizers of the cross-correlation, in which case the noise matrices are dependent. For approaches that address the case of dependent noise matrices, we refer the reader to, e.g., and the references therein.

2 Least Squares Formulation

For any closed subgroup $\mathcal{G}$ of the orthogonal group $\mathcal{O}(d)$, since $Q^{-1}=Q^{\top}$ for any $Q\in\mathcal{G}$, we can formulate the least squares estimation problem associated with $\mathcal{G}$-sync as

Any optimal solution to this problem is said to be a least squares estimator for the problem $\mathcal{G}$-sync.By the same argument as in (1), it can be seen that the least squares estimator is not unique. By the orthogonality of the blocks $[G]_{1},\ldots,[G]_{n}$, we can rewrite the above problem as

Problem (3) is non-convex and in general NP-hard, as it is equivalent to the MAX-CUT problem when $\mathcal{G}$ is the Boolean group $\mathcal{O}(1)=\{+1,-1\}$. A standard idea for tackling problem (3) is to consider its SDP relaxations , which can be solved by off-the-shelf solvers in polynomial time. However, this approach does not scale well with $n$ since it requires solving an SDP problem with an $nd\times nd$ matrix variable.

A Non-Convex Approach

Instead of convexification, we propose to tackle the non-convex problem (3) directly by a two-stage approach. An important subroutine in our approach is the projection of a $d\times d$ matrix onto the group $\mathcal{G}$. This projection, denoted by $\Pi_{\mathcal{G}}$, is defined by

The proof of Lemma 1 is straightforward and thus omitted.

We now describe the details of the two stages of our approach. The first stage aims to find a feasible point $G^{0}\in\mathcal{G}^{n}$ that has a sufficiently small estimation error $\varepsilon(G^{0})$. Theorem 1 below provides an explicit upper bound on the estimation error $\varepsilon(G^{0})$ that our non-convex approach requires. In Section 5.4, we propose a novel spectral-type estimator, called the entropic spectral estimator, for general group synchronization problems and show that under certain random models of the measurements and noise, the entropic spectral estimator satisfies the said upper bound on the estimation error with overwhelming probability. Moreover, the entropic spectral estimator can be computed efficiently. Hence, it can be used as $G^{0}$ in the first stage.

In the second stage, starting with the initial point $G^{0}$ obtained from the first stage, we iteratively refine the estimates using GPM, which is described below.

Overall, the proposed non-convex approach enjoys several computational advantages and is very efficient. For the first stage, the main cost of computing the entropic spectral estimator lies in the computation of the first $d$ eigenvectors of the matrix $C$ and the generation of independent copies of uniformly random orthogonal matrices, which can be done efficiently by a host of modern eigen-solvers and random orthogonal matrix samplers , respectively. For the second stage, we can see from Algorithm 1 that GPM does not require the tuning of any parameter and can be implemented extremely easily. The computational cost in each iteration consists of two parts: (i) $d$ matrix-vector multiplications for forming the product $CG^{t}$ and (ii) the block-wise projection $\Pi^{n}$, which can be decomposed into $n$ projections $\Pi$ onto the group $\mathcal{G}$. As we will see in Section 5.1, for the orthogonal group $\mathcal{O}(d)$, the special orthogonal group $\mathcal{SO}(d)$, and the permutation group $\mathcal{P}(d)$, the projection $\Pi$ reduces to a singular value decomposition (SVD) or a $d$-dimensional linear programming problem; for the cyclic group $\mathcal{Z}_{m}$, the projection $\Pi$ can be computed using a simple, explicit formula involving trigonometric functions. Thus, the two parts mentioned above are well-suited for parallelization and can be implemented efficiently for many closed subgroups of the orthogonal group.

A Master Theorem

The parameter $\kappa$ is related to the connectedness of the measurement graph $([n],E)$, see the discussion after Theorem 1. For any $G\in\mathcal{G}^{n}$, we define

where the last equality follows from the definition of $\Pi$ in (5). In particular, we have $\varepsilon(G)=\left\|{G-G^{*}Q_{G}}\right\|_{F}$. For simplicity, we write $Q^{t}=Q_{G^{t}}$ for all $t\geq 0$.

The following theorem is the first main theoretical result of this paper, which provides a bound on the rate at which the estimation error of the iterates generated by the proposed non-convex approach decays under certain assumptions on the subgroup, measurement graph, noise, and initialization.

there exists a constant $\alpha\geq 1$ such that for any $t\geq 0$,

$\left\|{D^{-1}\Delta}\right\|\leq\tfrac{1}{32}$ and $\left\|{\Pi^{n}\left(G^{*}+2D^{-1}\Delta G^{*}\right)-G^{*}}\right\|_{F}\leq\tfrac{(\sqrt{2}-1)\sqrt{n}}{48\alpha}$;

$\varepsilon(G^{0})\leq\tfrac{\sqrt{n}}{8\alpha}$.

Then, the iterates $\{G^{t}\}_{t\geq 1}$ generated by GPM satisfy

Let us elaborate on conditions (i)–(iv) in and the implications of Theorem 1 before giving its proof. Condition (i) reflects the geometry of the subgroup $\mathcal{G}$ through the projection map $\Pi_{\mathcal{G}}$. Indeed, as we shall see in Section 5.1, it can be interpreted as an error bound condition, which provides a measure of proximity of points in the convex hull of $\mathcal{G}$ to $\mathcal{G}$ itself. We will also show in Section 5.1 that condition (i) holds with $\alpha=1$ when $\mathcal{G}$ is the orthogonal group $\mathcal{O}(d)$, the special orthogonal group $\mathcal{SO}(d)$, or the permutation group $\mathcal{P}(d)$. We conjecture that condition (i) actually holds for arbitrary closed subgroups of the orthogonal group, see Conjecture 1. Condition (ii) is related to the measurement graph $([n],E)$ and represents the requirement that the measurement graph needs to be sufficiently connected. In particular, we have $\kappa=0$ when the measurement graph is complete (i.e., $w_{ij}=1$ for all $1\leq i<j\leq n$). Condition (iii) depends on normalized deviation matrix $D^{-1}\Delta$ and, roughly speaking, requires that the noise in the measurements cannot be too large. This condition suggests that when we quantify the information contained in the observations $\{C_{ij}:(i,j)\in E\}$, we should normalize the deviations matrices $\{\Delta_{ij}:(i,j)\in E\}$ by the degrees $\{r_{i}:i\in[n]\}$ of the nodes in the (extended) measurement graph. This is consistent with our intuition that under the same level of noise, more information is available at node $i$ if there are more observations related to $G^{*}_{i}$. For the special case of $\mathcal{SO}(2)$-sync with a complete measurement graph, a similar condition is used in the analysis of the SDP relaxation approach, see [6, Definition 3.1]. Condition (iv) captures the requirement that GPM needs to be initialized with a point $G^{0}$ of sufficiently small estimation error.

Under the setting of Theorem 1, we see that any accumulation point $G^{\infty}$ of the sequence of iterates $\{G^{t}\}_{t\geq 0}$ generated by GPM satisfy

which implies that, in the absence of noise (i.e., $\Delta=\mathbf{0}$), every accumulation point of the sequence $\{G^{t}\}_{t\geq 0}$ is, up to some common transformation, equal to the ground truth $G^{*}$. In Section 6, we will show that under standard models of noise and measurement graph, the estimation error $\left\|{\Pi^{n}\left(G^{*}+2D^{-1}\Delta G^{*}\right)-G^{*}}\right\|_{F}$ achieved by our approach is nearly optimal for both continuous and discrete subgroups of the orthogonal group.

We should also point out that the numerical constants in the statement of Theorem 1 are not important, as they can be improved by bootstrapping the analysis. The key message conveyed by Theorem 1 is that the estimation error of the iterates produced by the suitably initialized GPM decreases at least geometrically to some quantity characterized by the subgroup, measurement graph and noise.

Note that Theorem 1 does not guarantee the convergence of the sequence $\{G^{t}\}_{t\geq 0}$ generated by GPM. In the recent paper , which appeared after this paper was posted on arXiv, Ling considered the problem $\mathcal{O}(d)$-sync under the setting of complete measurement graph and additive Gaussian noise and showed that if the standard deviation of the noise is on the order of $\frac{\sqrt{n}}{\sqrt{d}(\sqrt{d}+\sqrt{\log n})}$, then GPM, when initialized by a spectral estimator, will generate iterates that converge linearly to a maximum likelihood estimator (which coincides with an optimal solution to the non-convex least squares formulation) with high probability. However, whether such a result can be extended to settings involving other closed subgroups of $\mathcal{O}(d)$ or more general measurement graphs or deterministic noise models remains open.

We first establish an useful inequality for the projection map.

Let $Q=\Pi\left(X+\Pi(X)+Y\right)$. We have

Simply algebraic manipulation on the last inequality yields

where the first inequality follows from the Cauchy-Schwarz inequality, the second from (8), and the third from (9). If $\|Q-\Pi(X)\|_{F}=0$, then $\Pi\left(X+\Pi(X)+Y\right)=\Pi(X)$ and hence the desired inequality holds trivially. If $\|Q-\Pi(X)\|_{F}\neq 0$, then we have arrived at

The inequality (10) will be used in the proof of the master theorem. Moreover, if we set $X=rQ$ for $r>0$ in (10) and take the limit $r\to 0$, then we have

The inequality (11) was established in [51, Proposition 3.3] for the special case of $\mathcal{SO}(2)$ via a completely different proof. Therefore, Lemma 2 is not only a strengthened but also a more general version of [51, Proposition 3.3]. Since [51, Proposition 3.3] has already been applied in a number of works to study phase synchronization problems or even other estimation problems , we believe that Lemma 2 will find further applications in synchronization or other estimation/optimization problems over general subgroups of the orthogonal group.

The proof of Theorem 1 also relies on the following technical lemma:

Let $\alpha\geq 1$ be given. If for some $t\geq 0$,

By the definition of $G^{t+1}$ and Lemma 1, we have

Using the definitions of $C$ in (4)and $\Delta$ in (6), it is easy to verify that $[C-\Delta]_{ij}=w_{ij}G_{i}^{*}{G^{*}_{j}}^{\top}$ for $i,j\in[n]$. It follows that

where the second equality is due to the fact that $D^{-1}$ and $\mbox{BlkDiag}(G_{1}^{*},\ldots,G_{n}^{*})$ commute and the identity

the third equality is due to the fact that $D^{-1}W(e\otimes Q^{t})=e\otimes Q^{t}$, the second-to-last inequality is due to the identities

and the last inequality is due to the assumption of the lemma and the definition of $Q^{t}$. The desired result now follows by putting (12) and (13) together. ∎

Armed with Lemma 3, we can now prove the master theorem.

We first show by induction that for any $t\geq 0$,

For $t=0$, this follows directly from the supposition that $\varepsilon(G^{0})\leq\tfrac{\sqrt{n}}{8\alpha}$. Next, we assume that $\varepsilon(G^{t})\leq\tfrac{\sqrt{n}}{8\alpha}$ for some $t\geq 0$. By Lemma 3, conditions (ii)–(iii), and the inductive hypothesis,

which yields (14). Using Lemma 3, conditions (ii)–(iii) and inequality (14), we have that

In the next section, we show that condition (i) in Theorem 1 is satisfied by various closed subgroups of the orthogonal group, while conditions (ii) and (iii) are satisfied by certain random measurement graph and random noise models. Moreover, we propose a novel spectral-type estimator and show that for the said subgroups and under the said random measurement graph and noise models, condition (iv) in Theorem 1 is satisfied by the proposed estimator. These results demonstrate the utility and power of Theorem 1.

Verifying the Conditions of the Master Theorem

In order to apply the master theorem in the last section, the subgroup $\mathcal{G}$ has to satisfy certain geometric conditions. In this section, we formulate these conditions and verify them for four specific subgroups, namely the orthogonal group $\mathcal{O}(d)$, the special orthogonal group $\mathcal{SO}(d)$, the permutation group $\mathcal{P}(d)$, and the cyclic group $\mathcal{Z}_{m}$. Along the way, we show that the projection maps associated with these subgroups can be computed in a tractable manner.

Therefore, these quantities can serve as proximity measures to $\mathcal{G}$ for points in $\text{conv}(\mathcal{G})$. We now investigate the connection between our non-convex approach to the geometry of $\mathcal{G}$, as reflected through the ratios of these proximity measures. The precise geometric conditions are given as follows.

There exists a constant $\alpha\geq 1$ such that

There exists a constant $\beta\in(0,1]$ such that

The above two conditions play an important role in our development. Indeed, if we take $X=\tfrac{1}{n}{G^{*}}^{\top}G$, then Condition 1 immediately implies that

which is precisely condition (i) in the master theorem. The usefulness of Condition 2 will become clear when we study the initialization for GPM in Section 5.4.

It is worth noting that Conditions 1 and 2 are reminiscent of error bound conditions, which have been extensively studied in the optimization literature and applied to analyze the convergence rates of various iterative methods, see, e.g., and the references therein. Roughly speaking, an error bound condition postulates that the distance function associated with some target set (often difficult to characterize theoretically and not computable in practice) is bounded above by a continuous surrogate function (often easier to characterize theoretically and compute in practice) that vanishes on the target set. In the context of synchronization problems, such a condition was first introduced in to study the optimization performance of GPM.

The main result of this subsection is summarized in the following theorem, which will be proved in a case-by-case manner.

For $\mathcal{G}=\mathcal{O}(d)$ or $\mathcal{G}=\mathcal{SO}(d)$, the projection $\Pi_{\mathcal{G}}$ can be computed in closed form via the SVD of a $d\times d$ matrix; for $\mathcal{G}=\mathcal{P}(d)$, the projection $\Pi_{\mathcal{G}}$ can be computed by solving a $d$-dimensional linear programming problem; for $\mathcal{G}=\mathcal{Z}_{m}$, the projection $\Pi_{\mathcal{G}}$ can be computed in closed form via the formula in Proposition 2. Moreover, Conditions 1 and 2 hold for the groups $\mathcal{O}(d)$, $\mathcal{SO}(d)$, $\mathcal{P}(d)$, and $\mathcal{Z}_{m}$ with

Motivated by Theorem 2, we formulate the following conjecture:

Let $\mathcal{G}$ be any closed subgroup of the orthogonal group $\mathcal{O}(d)$. Then, there exist constants $\alpha\geq 1$ and $\beta\in(0,1]$ such that

The validity of Conjecture 1 would imply that condition (i) in the master theorem is superfluous.

Now, let $X\in\text{conv}(\mathcal{O}(d))$ be arbitrary. By Carathéodory’s theorem, there exist $Q_{1},\dots,Q_{L}\in\mathcal{O}(d)$ and $\omega_{1},\dots,\,\omega_{L}\geq 0$ such that

where $\sigma_{j}(\cdot)$ denotes the $j$-th largest singular value. This implies that $I_{d}-\Sigma_{X}$ is positive semidefinite and

Thus, Condition 1 holds for $\mathcal{O}(d)$ with $\alpha=1$. Furthermore, we have

which shows that Condition 2 holds for $\mathcal{O}(d)$ with $\beta=1$.

1.2 Proof of Theorem 2: Special Orthogonal Group 𝒮​𝒪​(d)𝒮𝒪𝑑\mathcal{SO}(d)

We adopt a similar strategy to the one used in Section 5.1.1 to establish Condition 1 for $\mathcal{SO}(d)$. First, we have the following result, which gives an explicit formula for the projection $\Pi_{\mathcal{SO}(d)}$ and is known as the Kabsch algorithm .

Now, let $X\in{\rm conv}(\mathcal{SO}(d))$ be arbitrary. Using Lemma 4, we have

where the inequality follows from (15). This shows that Condition 1 holds for $\mathcal{SO}(d)$ with $\alpha=1$.

To establish Condition 2 for $\mathcal{SO}(d)$, let $X\in{\rm conv}(\mathcal{SO}(d))$ be arbitrary and consider first the case where $\det(U_{X}V_{X})=1$. Then, we have $I_{X}=I_{d}$ and $\Pi_{\mathcal{SO}(d)}(X)=\Pi_{\mathcal{O}(d)}(X)$. It follows from (LABEL:ineq:26) that

Next, consider the case where $\det(U_{X}V_{X})=-1$, i.e., $\Pi_{\mathcal{O}(d)}(X)\in\mathcal{O}(d)\setminus\mathcal{SO}(d)$. Since $X\in\text{conv}(\mathcal{SO}(d))$, by Carathéodory’s theorem, there exist $Q_{1},\dots,Q_{L}\in\mathcal{SO}(d)$ and $\omega_{1},\dots,\,\omega_{L}\geq 0$ such that

where the first equality follows from Lemma 4, the second equality follows from the assumption that $\det(U_{X}V_{X})=-1$, the first inequality follows from the fact that $\sigma_{j}(X)\leq 1$ for $j=1,\dots,d$, and the last inequality follows from (17). This shows that Condition 2 holds for $\mathcal{SO}(d)$ with $\beta=\tfrac{1}{2}$.

1.3 Proof of Theorem 2: Permutation Group 𝒫​(d)𝒫𝑑\mathcal{P}(d)

The above problem can be solved in polynomial time by linear programming or the Hungarian (also known as the Kuhn–Munkres) algorithm.

To establish Condition 1 for $\mathcal{P}(d)$, we first note that for any $Q\in\mathcal{P}(d)$, we either have $d=\operatorname{Tr}(Q)$ or $d-\operatorname{Tr}(Q)\geq 2$. It follows that

For any $Y\in\text{conv}(\mathcal{P}(d))$, by Carathéodory’s theorem, there exist $Q_{1},\dots,Q_{L}\in\mathcal{P}(d)$ and $\omega_{1},\dots,\,\omega_{L}\geq 0$ such that

Now, let $X\in\text{conv}(\mathcal{P}(d))$ be arbitrary. Since ${\Pi_{\mathcal{P}(d)}(X)}^{\top}X\in\text{conv}(\mathcal{P}(d))$, by invoking (19) with $Y={\Pi_{\mathcal{P}(d)}(X)}^{\top}X$, we obtain

This shows that Condition 1 holds for $\mathcal{P}(d)$ with $\alpha=1$.

The minimum separation of a discrete set $\mathcal{G}$ is defined as

To establish Condition 2 for $\mathcal{P}(d)$, we prove the following stronger result, which relates $\beta$ to the minimum separation and states that Condition 2 actually holds for any discrete subgroup of $\mathcal{O}(d)$.

Let $\mathcal{G}$ be a discrete subgroup of $\mathcal{O}(d)$ with at least two elements and minimum separation $\tau$. Then, Condition 2 holds for $\mathcal{G}$ with

The compactness of $\mathcal{O}(d)$ implies that $\mathcal{G}$ must be finite. Hence, we may let $\mathcal{G}=\{Q_{1},\ldots,Q_{L}\}$ with $Q_{1},\ldots,Q_{L}\in\mathcal{O}(d)$. For any $X\in\text{conv}(\mathcal{G})$, there exist $\omega_{1},\dots,\,\omega_{L}\geq 0$ such that

which, upon substitution into (20), shows that Condition 2 holds for $\mathcal{G}$ with

When $\mathcal{G}=\mathcal{P}(d)$, a simple calculation shows that $\tau=2$ . Hence, by Proposition 1, Condition 2 holds for $\mathcal{P}(d)$ with $\beta=\frac{2}{d}$.

We first prove that Condition 1 holds for $\mathcal{Z}_{m}$ for any integer $m\geq 1$. In particular, we show that

To do so, we note that every $X\in\text{conv}(\mathcal{Z}_{m})$ is of the form

For $m=1$, we have $\hat{k}(X)=0$ for any $X\in\text{conv}(\mathcal{Z}_{1})$ and hence $\Pi_{\mathcal{Z}_{1}}(X)=Q_{0}=I_{2}$. It follows that

i.e., Condition 1 holds for $\mathcal{Z}_{1}$ with $\alpha=1$. For $m=2$, if $\Re(z_{X})=x\geq 0$, then $\hat{k}(X)=0$ and $\Pi_{\mathcal{Z}_{2}}(X)=Q_{0}=I_{2}$; if $\Re(z_{X})=x<0$, then $\hat{k}(X)=1$ and $\Pi_{\mathcal{Z}_{2}}(X)=Q_{1}=-I_{2}$. Therefore, we have

which shows that Condition 1 holds for $\mathcal{Z}_{2}$ with $\alpha=1$.

Now, consider the case where $m\geq 3$. On one hand, we have

where $\left|\,\cdot\,\right|$ denotes the modulus of a complex number. On the other hand,

Therefore, in order to establish Condition 1 for $\mathcal{Z}_{m}$, we need to bound the ratio

subject to the constraint that $z=z_{X}$ for some $X\in\text{conv}(\mathcal{G})$ with $\hat{k}(X)=k$.

By symmetry, we can assume without loss of generality that $\hat{k}(X)=0$ and consider the shaded region $\mathcal{R}_{0}$ shown in Figure 1(a), which is defined by

Over the region $\mathcal{R}_{0}$, the ratio (24) reduces to

Let $z_{1}$ and $z_{2}$ be the midpoints between 1 and its two neighboring group elements $e^{2\pi\mathbf{i}/m}$ and $e^{-2\pi\mathbf{i}/m}$, respectively. We claim that any point on the line segments $[1,z_{1}]\cup[1,z_{2}]$ (see Figure 1(a)) is a maximizer of the ratio (25) over $\mathcal{R}_{0}$. To see this, we consider the polar representation $z^{\prime}=|z^{\prime}|\cdot e^{\mathbf{i}\phi}$ of the transformed variable $z^{\prime}=1-z$, which lies in the region $1-\mathcal{R}_{0}$ (see Figure 1(b)). By the angle sum formula for the regular $m$-gon, we have $\phi\in\left[-\pi\left(\frac{1}{2}-\frac{1}{m}\right),\pi\left(\frac{1}{2}-\frac{1}{m}\right)\right]$. It follows that

This shows that Condition 1 holds for $\mathcal{Z}_{m}$ (where $m\geq 3$) with $\alpha=\frac{1}{\sqrt{2}\sin\frac{\pi}{m}}$.

Next, we establish Condition 2 for $\mathcal{Z}_{m}$ with $m\geq 1$. It is trivial to show that Condition 2 holds for $\mathcal{Z}_{1}$ with $\beta=1$. For $m\geq 2$, since $\mathcal{Z}_{m}$ is a discrete subgroup of $\mathcal{O}(2)$, we compute

and apply Proposition 1 to conclude that Condition 2 holds for $\mathcal{Z}_{m}$ with

Finally, let us derive an explicit formula for the projection $\Pi_{\mathcal{Z}_{m}}$, where $m\geq 1$.

which always lies in $[0,2\pi)$. Then, for any $m\geq 1$,

where ${\rm round}(\,\cdot\,)$ rounds a number to its closest integer and $Q_{k}$ is defined in (21).

The result is trivial when $m=1$. Thus, we assume that $m\geq 2$. Then, we have

Since $\theta$ can take any value in $[0,2\pi)$ and $\frac{2k\pi}{m}$ lies in $[0,\frac{2(m-1)\pi}{m}]$, we have

Moreover, the function $\varphi\mapsto\sin\varphi$ has two peaks in $\left[0,2\pi+\frac{2(m-1)\pi}{m}\right)$, namely at $\varphi=\frac{\pi}{2}$ and $\varphi=\frac{5\pi}{2}$. It follows that

We first consider the case where $0\leq\theta\leq\frac{\pi}{2}+\frac{\pi}{m}$. Note that

we have $\text{round}\left(\frac{m}{4}-\frac{m\theta}{2\pi}\right)\in\{0,\dots,m-1\}$. Setting $k=\text{round}\left(\frac{m}{4}-\frac{m\theta}{2\pi}\right)$, we get

Next, we consider the case where $\frac{\pi}{2}+\frac{\pi}{m}<\theta<2\pi$. Note that

we have $\text{round}\left(\frac{5m}{4}-\frac{m\theta}{2\pi}\right)\in\{0,\dots,m-1\}$. Setting $k=\text{round}\left(\frac{5m}{4}-\frac{m\theta}{2\pi}\right)$, we get

2 Erdős-Rényi Measurement Graphs

Recall from our discussion in Section 4 that the parameter $\kappa$ can be viewed as a measure of the connectivity of the measurement graph $([n],E)$. In particular, when the measurement graph is complete, we have $\kappa=0$, which shows that condition (ii) in the master theorem is satisfied. As it turns out, the condition can be satisfied by measurement graphs that are much sparser. In this subsection, we show that if the measurement graph is an Erdős-Rényi random graph with observation rate $p\geq\frac{c\log n}{n}$ for some constant $c>0$ — i.e., the edge weights $\{w_{ij}:1\leq i<j\leq n\}$ are independent and identically distributed (i.i.d.) Bernoulli random variables with

— then condition (ii) in the master theorem will be satisfied with high probability. More precisely, we have the following result:

Suppose that the measurement graph is an Erdős-Rényi random graph with observation rate $p\in(0,1]$. Then, there exist constants $c_{1},c_{2}>0$ such that whenever $p\geq\frac{c_{1}\log n}{n}$, we will have $\kappa\leq\frac{1}{32}$ with probability at least $1-\frac{1}{n^{c_{2}}}$.

Using the definitions of $D$, $W$, $F$, and $\kappa$ in Section 4, we compute

where the second line follows from the fact that $(A_{1}\otimes A_{2})^{-1}=A_{1}^{-1}\otimes A_{2}^{-1}$ for any invertible matrices $A_{1}$ and $A_{2}$, the third line follows from the fact that $(A_{1}\otimes A_{2})(A_{3}\otimes A_{4})=(A_{1}A_{3})\otimes(A_{2}A_{4})$ for any matrices $A_{1},A_{2},A_{3},A_{4}$ with conformable dimensions, the fourth line follows from the bilinearity of the Kronecker product, and the last line follows from the fact that $\left\|{A_{1}\otimes A_{2}}\right\|=\left\|{A_{1}}\right\|\cdot\left\|{A_{2}}\right\|$ (these properties of the Kronecker product can be found in, e.g., [37, Chapter 4.2]). Now, we bound

Since $\bar{D}^{-1}\bar{W}$ has non-negative entries and each of its rows sums to 1, we have $\left\|{\bar{D}^{-1}\bar{W}}\right\|\leq 1$ by [36, Corollary 6.1.5]. Moreover, observe that

where $r_{i}=\sum_{j=1}^{n}w_{ij}=1+\sum_{j\not=i}w_{ij}$ for $i=1,\ldots,n$. By Chernoff’s inequality (cf. [73, Exercise 2.3.5]), for any $t\in(0,1]$, we have

Next, by adapting the results in [13, Examples 3.14 and 6.8] and [10, Corollary 3.6], we have, for any $p\geq\frac{\log n}{n}$, that

Upon setting $t=\frac{1}{66}$ and assuming that $p\geq\frac{(172\times 66)^{2}\log n}{n}$, we conclude that

with probability at least $1-\frac{1}{n^{9000}}$. ∎

3 Additive Sub-Gaussian Noise Model

Recall that under the additive noise model, the measurements are given by

The purpose of this subsection is to show that condition (iii) in the master theorem holds for a large class of noise matrices $\{\Theta_{ij}:(i,j)\in E\}$. Specifically, we focus on the case where $\{\Theta_{ij}:(i,j)\in E\}$ is a collection of independent random matrices whose entries are i.i.d. sub-Gaussian random variables.

A random variable $\xi$ is said to be sub-Gaussian with parameter $\sigma>0$ if

We first establish a tail inequality for the operator norm of the block matrix $\Delta$ (see (6) for the definition), which will be useful for verifying condition (iii) in the master theorem.

Suppose that the measurement graph is an Erdős-Rényi random graph with observation rate $p\in(0,1]$. Let $\{\Theta_{ij}:1\leq i<j\leq n\}$ be independent noise matrices that are independent of the measurement graph and whose entries are i.i.d. sub-Gaussian random variables with parameter $\sigma>0$. Then, there exist constants $c_{0},c_{1},c_{2}>0$ such that whenever $p\geq\tfrac{c_{0}(\log n)^{2}}{n}$, we have

If the sub-Gaussian entries $\{\Theta_{ij}:1\leq i<j\leq n\}$ are zero-mean Gaussian with standard deviation $\sigma>0$, then the same inequality holds under the weaker requirement $p\geq\tfrac{c_{0}\log n}{n}$.

Using (6) and (29), we can write each block in $\Delta$ as

Therefore, conditioning on the measurement graph (i.e., on the values of the random variables $\{w_{ij}:1\leq i<j\leq n\}$), $\Delta$ is an $nd\times nd$ symmetric matrix whose upper triangular entries are independent random variables. Since the operator norm $\|\cdot\|$ is a convex, 1-Lipschitz function in the matrix entries, by Talagrand’s inequality , there exist constants $c_{0},c_{1}>0$ such that

for some constant $c_{2}>0$. Substituting (31) into (30) and taking $s=\sqrt{\tfrac{\log nd}{c_{1}}}$, we find that for some constants $c_{3},c_{4}>0$, whenever $p\geq\frac{c_{3}(\log n)^{2}}{n}$,

We now bound the probabilities of the two conditioned events. Since $([\Theta]_{12})_{11}$ is a sub-Gaussian random variable with parameter $\sigma>0$, we can show by using the Markov inequality that

Next, since $\{w_{ij}:1\leq i<j\leq n\}$ are i.i.d. Bernoulli random variables with parameter $p$, by the union bound and Chernoff’s inequality [73, Theorem 2.3.1], there exist constants $c_{5},c_{6}>0$ such that whenever $p\geq\frac{c_{5}(\log n)^{2}}{n}$,

The desired inequality then follows by combining (32), (33), and (34).

The last claim under the Gaussian assumption can be proved by similarly conditioning on the event

and using [10, Corollary 3.9]. This completes the proof. ∎

The following theorem, which is a substantial generalization of [6, Proposition 3.3], shows that under the setting of Proposition 3, condition (iii) in Theorem 1 will be satisfied with high probability.

Consider the setting of Proposition 3 and let $\alpha\geq 1$ be arbitrary. Then, there exist constants $c_{0},c_{1},c_{2}>0$ such that whenever $p\geq\tfrac{c_{0}(\log n)^{2}}{n}$ and $\sigma\leq\frac{c_{1}\sqrt{pn}}{\alpha d}$, we have

If the sub-Gaussian entries $\{\Theta_{ij}:1\leq i<j\leq n\}$ are zero-mean Gaussian with standard deviation $\sigma>0$, then the same inequality holds under the weaker requirement $p\geq\tfrac{c_{0}\log n}{n}$.

Upon applying Chernoff’s inequality [73, Exercise 2.3.2], we have

The above inequality and the union bound imply that for some constants $c_{0},c_{1}>0$, whenever $p\geq\tfrac{c_{0}(\log n)^{2}}{n}$ ($p\geq\tfrac{c_{0}\log n}{n}$ in the Gaussian case), we have

This, together with Proposition 3, implies the existence of constants $c_{2},c_{3},c_{4}>0$ such that whenever $p\geq\frac{c_{2}(\log n)^{2}}{n}$ ($p\geq\tfrac{c_{2}\log n}{n}$ in the Gaussian case) and $\sigma\leq\frac{c_{3}\sqrt{pn}}{\alpha d}$, we have

with probability at least $1-\frac{c_{4}}{n}$.

Next, we bound $\left\|{\Pi^{n}\left(G^{*}+2D^{-1}\Delta G^{*}\right)-G^{*}}\right\|_{F}$. By inequality (11), we have

Since $G^{*}$ has $n$ blocks, each of which is a $d\times d$ orthogonal matrix, we have $\left\|{G^{*}}\right\|_{F}=\sqrt{nd}$. Using the inequality $\left\|{D^{-1}\Delta G^{*}}\right\|_{F}\leq\left\|{D^{-1}\Delta}\right\|\cdot\left\|{G^{*}}\right\|_{F}$, the desired bound then follows from (35). ∎

4 Entropic Spectral Initialization

In order for our non-convex approach to enjoy the theoretical guarantee offered by the master theorem, we need to initialize GPM by a point that has a sufficiently small estimation error. As it turns out, the geometry of the closed subgroup $\mathcal{G}$ contains much information that can be used to guide our construction of such a point. Specifically, by considering the error-bound geometry of $\mathcal{G}$ as encapsulated in Condition 2 and the classic notion of metric entropy of the quotient $\mathcal{O}(d)/\mathcal{G}$ of the orthogonal group $\mathcal{O}(d)$ by the closed subgroup $\mathcal{G}$,Note that the quotient $\mathcal{O}(d)/\mathcal{G}$ may not be a group in general as we do not require the subgroup $\mathcal{G}$ to be normal. we design a novel initialization procedure for GPM that produces a point satisfying condition (iv) in the master theorem. Before we present our proposed procedure, let us introduce some basic results concerning the metric entropy of the quotient $\mathcal{O}(d)/\mathcal{G}$.

Given any closed subgroup $\mathcal{G}$ of $\mathcal{O}(d)$ and any orthogonal matrix $Q\in\mathcal{O}(d)$, the (left-) coset $[Q]$ of $\mathcal{G}$ in $\mathcal{O}(d)$ is defined by

The quotient $\mathcal{O}(d)/\mathcal{G}$ is then defined as the set of all cosets of $\mathcal{G}$ in $\mathcal{O}(d)$. We can define a natural distance on $\mathcal{O}(d)/\mathcal{G}$ by

It can be easily seen that this distance is independent of the choice of the class representatives $Q_{1}$ and $Q_{2}$ of the cosets $[Q_{1}]$ and $[Q_{2}]$, respectively. Moreover, it turns $\mathcal{O}(d)/\mathcal{G}$ into a compact (under the quotient topology) metric space.

We next introduce the concepts of net and covering number, see, e.g., .

Let $(\mathcal{S},\nu)$ be a compact metric space and $\epsilon>0$ be a parameter. A subset $\mathcal{N}\subseteq\mathcal{S}$ is said to be an $\epsilon$-net of $\mathcal{S}$ if for any point $x\in\mathcal{S}$, there exists a point $y\in\mathcal{N}$ such that $\nu(x,y)\leq\epsilon$. The cardinality of the smallest $\epsilon$-net is called the $\epsilon$-covering number, denoted by $N(\mathcal{S},\epsilon)$.

The compactness of $\mathcal{S}$ implies that $N(\mathcal{S},\epsilon)$ is finite for any $\epsilon>0$. The following proposition offers an explicit and efficient construction of an $\epsilon$-net of the quotient $\mathcal{O}(d)/\mathcal{G}$.

Let $\epsilon>0$ and $Q_{1},\dots,Q_{K}$ be random orthogonal matrices that are independently and uniformly distributed on $\mathcal{O}(d)$. Then, for any $O\in\mathcal{O}(d)$, with probability at least $1-\left(1-N(\mathcal{O}(d)/\mathcal{G},\tfrac{\epsilon}{2})^{-1}\right)^{K}$, we have

Optimizing the lower bound over all possible $(\epsilon/2)$-nets $\mathcal{N}$ of $\mathcal{O}(d)/\mathcal{G}$ completes the proof. ∎

In view of Proposition 4, we are naturally interested in determining the covering number of the quotient $\mathcal{O}(d)/\mathcal{G}$, particularly when $\mathcal{G}$ is one of the four subgroups (i.e., $\mathcal{O}(d)$, $\mathcal{SO}(d)$, $\mathcal{P}(d)$, and $\mathcal{Z}_{m}$) we considered earlier. For $\mathcal{G}=\mathcal{O}(d)$, the quotient $\mathcal{O}(d)/\mathcal{O}(d)$ is the trivial group that contains only one element. Therefore, its $\epsilon$-covering number is $1$ for any $\epsilon>0$. For $\mathcal{G}=\mathcal{SO}(d)$, the quotient $\mathcal{O}(d)/\mathcal{SO}(d)$ is isomorphic to the Boolean group, which implies that its $\epsilon$-covering number is at most $2$ for any $\epsilon>0$. In what follows, we provide an estimate of the covering number of the quotient $\mathcal{O}(d)/\mathcal{G}$ when $\mathcal{G}$ is a discrete subgroup of $\mathcal{O}(d)$. In particular, such an estimate applies to the cases of $\mathcal{G}=\mathcal{P}(d)$ and $\mathcal{G}=\mathcal{Z}_{m}$.

4.2 Covering Number of the Quotient 𝒪​(d)/𝒢𝒪𝑑𝒢\mathcal{O}(d)/\mathcal{G} for Discrete 𝒢𝒢\mathcal{G}

To begin, let us introduce the concepts of packing and packing number, which are closely related to the concepts of net and covering number, respectively.

Let $(\mathcal{S},\nu)$ be a compact metric space and $\epsilon>0$ be a parameter. A subset $\mathcal{P}\subseteq\mathcal{S}$ is said to be an $\epsilon$-packing of $\mathcal{S}$ if any two points $x,y\in\mathcal{P}$ satisfy $\nu(x,y)>\epsilon$. The cardinality of the largest $\epsilon$-packing is called the $\epsilon$-packing number, denoted by $P(\mathcal{S},\epsilon)$.

Given a compact metric space $(\mathcal{S},\nu)$ and a parameter $\epsilon>0$, we have the following relationship between the covering and packing numbers, see, e.g., [70, Inequality (3)]:

This inequality can then be used to establish the following result:

Let $\mathcal{G}$ be a discrete subgroup of $\mathcal{O}(d)$ and $\epsilon>0$ be a given parameter. Then, we have

It suffices to consider the case where $\epsilon<\tau$. Let $\widetilde{\mathcal{P}}$ be a maximal $\epsilon$-packing of the quotient $\mathcal{O}(d)/\mathcal{G}$, i.e., $|\widetilde{\mathcal{P}}|=P(\mathcal{O}(d)/\mathcal{G},\epsilon)$. Then, for any distinct cosets $[Q_{1}],[Q_{2}]\in\widetilde{\mathcal{P}}$, we have

Consider the set $\mathcal{P}:=\{Q\in\mathcal{O}(d):[Q]\in\widetilde{\mathcal{P}}\}$. We claim that $\mathcal{P}$ is an $\epsilon$-packing of $\mathcal{O}(d)$. To prove this, let $Q_{1},Q_{2}\in\mathcal{P}$ be two distinct points. If $[Q_{1}]\neq[Q_{2}]$, then we have

by (38). If $[Q_{1}]=[Q_{2}]$, then $Q_{1}=Q_{2}Q^{\prime}$ for some $Q^{\prime}\in\mathcal{G}\setminus\{I_{d}\}$. It follows from Definition 1 that

Thus, the claim is established. Now, it is elementary to show that (i) for any $Q\in\mathcal{O}(d)$, we have $|[Q]|=|\mathcal{G}|$; (ii) for any two cosets $[Q_{1}],[Q_{2}]\in\mathcal{O}(d)/\mathcal{G}$, we either have $[Q_{1}]=[Q_{2}]$ or $[Q_{1}]\cap[Q_{2}]=\emptyset$. In particular, we see that $|\mathcal{P}|=|\widetilde{\mathcal{P}}|\cdot|\mathcal{G}|=P(\mathcal{O}(d)/\mathcal{G},\epsilon)\cdot|\mathcal{G}|$. Consequently, there exists a constant $c>0$ such that

where the first and third inequalities follow from (37), the second inequality follows the fact that $\mathcal{P}$ is an $\epsilon$-packing, and the last inequality follows from [70, Theorem 7]. This completes the proof. ∎

4.3 Entropic Spectral Estimator

We are now ready to develop our advertised initialization procedure for GPM. We will make use of the results in the previous subsection and the following variant of the Davis-Kahan Theorem .

This, together with the definition of $\varepsilon$ in (2), Lemma 1, inequality (11) and inequality (39), implies that $\Pi^{n}(V_{C}Q^{*})$ enjoys the estimation error bound

Unfortunately, the estimator $\Pi^{n}(V_{C}\,Q^{*})$ is not implementable as we do not know $Q^{*}$ in general. To work around this, let us construct an approximation $\widetilde{Q}$ of the unknown $Q^{*}$ as follows. Suppose that we have a finite subset $\mathcal{Q}\subseteq\mathcal{O}(d)/\mathcal{G}$ satisfying

By definition, there must exist $[\widetilde{Q}]\in\mathcal{Q}$ and $Q^{\prime}\in\mathcal{G}$ such that

Let us now study the estimation performance of $\widetilde{G}$.

Let $\eta>0$, $\epsilon\geq 0$ be given parameters and $\mathcal{Q}\subseteq\mathcal{O}(d)/\mathcal{G}$ be a finite subset of equivalent classes satisfying (41). Consider the estimator $\widetilde{G}$ defined in (43). Then,

where the first inequality follows from (43); the second inequality follows from Lemma 1 and inequality (11); the last inequality follows from (39), (42), and the fact that $\|V_{C}\|\leq 1$. This completes the proof. ∎

Since $\Pi^{n}(V_{C}QQ^{\prime})=\Pi^{n}(V_{C}Q)Q^{\prime}$ for any $Q^{\prime}\in\mathcal{G}$, the function $\psi$ is independent of the choice of the representative $Q$ of the equivalent class $[Q]$. This shows that $\psi$ is a well-defined function on $\mathcal{O}(d)/\mathcal{G}$. Partly inspired by the work , in which a randomized rounding scheme for approximating the optimal solution to certain robust non-convex quadratic optimization problem is analyzed using an $\epsilon$-net of the sphere, we propose the following estimator:

A key difference between the estimators $\widetilde{G}$ and $\widehat{G}$ is that the former requires the knowledge of an element $\widetilde{Q}$ satisfying inequality (42), whereas the latter works as long as there exists one and we do not need to know which element it is.

Let us discuss how to construct a subset $\mathcal{Q}\subseteq\mathcal{O}(d)/\mathcal{G}$ satisfying (41). When $\mathcal{G}=\mathcal{O}(d)$, there is only one equivalent class, viz., the orthogonal group $\mathcal{O}(d)$ itself. In this case, the entropic spectral estimator $\widehat{G}$ reduces to the spectral estimator in the works and . Therefore, the entropic spectral estimator can be seen as a generalization of these spectral estimators. When $\mathcal{G}=\mathcal{SO}(d)$, there are two equivalent classes: One formed by the set of orthogonal matrices with determinant $+1$ and the other with determinant $-1$. Taking the representatives $I_{d}$ and $\operatorname{Diag}(-1,1,\dots,1)$ for these two equivalent classes, respectively, the entropic estimator is either $\Pi^{n}(V_{C})$ or $\Pi^{n}(V_{C}^{\prime})$ with $V_{C}^{\prime}=V_{C}\cdot\operatorname{Diag}(-1,1,\ldots,1)$, depending on whether $\langle C\Pi^{n}(V_{C}),\Pi^{n}(V_{C})\rangle\geq\langle C\Pi^{n}(V_{C}^{\prime}),\Pi^{n}(V_{C}^{\prime})\rangle$. If $\mathcal{G}$ is a discrete subgroup of $\mathcal{O}(d)$, then we can find a desired subset $\mathcal{Q}$ by invoking Propositions 4 and 5. Specifically, these two propositions imply that there exists a constant $c>0$ such that given any $\rho\in(0,1)$, if we generate

random orthogonal matrices $Q_{1},\ldots,Q_{K}$ that are independently and uniformly distributed on $\mathcal{O}(d)$, then with probability at least $1-\rho$, the set $\mathcal{Q}=\{[Q_{1}],\dots,[Q_{K}]\}$ satisfies inequality (41).

Interestingly, Proposition 4 reveals an intimate relation between our proposed estimator and the notion of metric entropy (the logarithm of covering number): The smaller the metric entropy of the quotient $\mathcal{O}(d)/\mathcal{G}$, the fewer independent copies of uniformly distributed random orthogonal matrices we need to construct the subset $\mathcal{Q}$. This explains why we name our estimator $\widehat{G}$ the entropic spectral estimator.

The main result of this subsection is the following theorem, which concerns the estimation performance of the entropic spectral estimator.

Suppose that the group $\mathcal{G}$ satisfies Condition 2 with parameter $\beta\in(0,1]$. Let $\eta>0$ and $\epsilon\geq 0$ be given parameters. Then, the entropic spectral estimator $\widehat{G}$ returned by Algorithm 2 satisfies

Theorem 6 shows that even though we do not have access to the element $[\widetilde{Q}]\in\mathcal{Q}$ defined in (42) and hence cannot construct the estimator $\widetilde{G}$ in (43), we can get hold of another element $[\widehat{Q}]\in\mathcal{Q}$ by maximizing the least squares-based function $\psi$ over $\mathcal{Q}$ and use it to construct the estimator $\widehat{G}$, whose estimation error bound is worse than that of the estimator $\widetilde{G}$ by roughly a factor of $\frac{1}{\sqrt{\beta}}$ (recall that the parameter $\beta\in(0,1]$ is related to the geometry of the subgroup $\mathcal{G}$, see Condition 2). As shown in Theorem 2, for many groups of interest (such as the orthogonal group $\mathcal{O}(d)$, the special orthogonal group $\mathcal{SO}(d)$, and the cyclic group $\mathcal{Z}_{m}$), the parameter $\beta$ is a constant, which implies that the bounds on $\varepsilon(\widetilde{G})$ and $\varepsilon(\widehat{G})$ differ by at most a constant factor.

Let $\widetilde{G}$ be defined as in (43). By definition of the entropic spectral estimator $\widehat{G}$,

Upon letting $\Delta_{\eta}=C-\eta\cdot G^{*}{G^{*}}^{\top}$, for any $Q\in\mathcal{G}$, we have

Now, for any $G\in\mathcal{G}^{n}$, we have the identity

where $Q_{G}\in\mathcal{G}\subseteq\mathcal{O}(d)$ is defined in (7). This yields