ReSync: Riemannian Subgradient-based Robust Rotation Synchronization
Authors: Huikang Liu
Xiao Li
Anthony Man-Cho So
Venue: NeurIPS 2023 poster (2023)
Keywords: Manifold optimization
Riemannian subgradient method
rotation synchronization
TL;DR: We introduce ReSync algorithm for solving robust rotation synchronization and provide strong theoretical guarantees.

Abstract: This work presents ReSync, a Riemannian subgradient-based algorithm for solving the robust rotation synchronization problem, which arises in various engineering applications. ReSync solves a least-unsquared minimization formulation over the rotation group, which is nonsmooth and nonconvex, and aims at recovering the underlying rotations directly. We provide strong theoretical guarantees for ReSync under the random corruption setting. Specifically, we first show that the initialization procedure of ReSync yields a proper initial point that lies in a local region around the ground-truth rotations. We next establish the weak sharpness property of the aforementioned formulation and then utilize this property to derive the local linear convergence of ReSync to the ground-truth rotations. By combining these guarantees, we conclude that ReSync converges linearly to the ground-truth rotations under appropriate conditions. Experiment results demonstrate the effectiveness of ReSync.

ReSync: Riemannian Subgradient-based Robust Rotation Synchronization
Huikang Liu
School of Information Management and Engineering Shanghai University of Finance and Economics liuhuikang @ shufe.edu.cn
Xiao Li"
School Data Science
The Chinese University of Hong Kong, Shenzhen lixiao wwwoocuuuhk...cc
Anthony Man-Cho So
Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong manchoso se.cuhk.cuu.bt
Abstract
This work presents ReSync, a Riemannian subgradient-based algorithm for solving the robust rotation synchronization problem, which arises in various engineering applications. ReSync solves a least-unsquared minimization formulation over the rotation group, which is nonsmooth and nonconvex, and aims at recovering the underlying rotations directly. We provide strong theoretical guarantees for ReSync under the random corruption setting. Specifically, we first show that the initialization procedure of ReSync yields a proper initial point that lies in a local region around the ground-truth rotations. We next establish the weak sharpness property of the aforementioned formulation and then utilize this property to derive the local linear convergence of ReSync to the ground-trutt -ruth rotations. By combining these guarantees, we conclude that ReSync converges linearly to the ground-truth rotations under appropriate conditions. Experiment results demonstrate the effec- tiveness ReSync.
Introduction
Rotation synchronization (RS) is a fundamental problem in many engineering applications. For instance, RS (also known "rotation averaging") is an important subproblem of structure from motion (SfM) and simultaneous localization and mapping (SLAM) in computer vision [20. 22, 17]. where the goal is to compute the absolute orientations of objects from relative rotations between pairs of objects. RS has also been applied to sensor network localization [41, 12]. signal recovery from phaseless observations [2], digital communications [36], and cryo-EM imaging [35, 33].
Practical measurements relative rotations are often incomplete and corrupted, leading to the problem of robust rotation synchronization (RRS) [28, 21, 22, 39, 9, 31]. The goal of RRS is to reconstruct set of ground-truth rotations Xi.... ......... X; ....... X E SO(d) from measurements of
"Corresponding Author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

relative rotations represented as
X
(i.5) E A, (1,5) E A, A,
AA E A.
with ratio pg. with ratio (1 p)g.
with (i,j)
(1)
0,
(i,5) E E
E
otherwise.
Here, SO(d) :- E Rixd R R I, I, det(R) = 1} denotes the rotation group (also known as the special orthogonal group), & represents the indices of all available observations, A denotes the indices of true observations, A :- E\ \ A is the indices of oulliers, Oij (O(d) is an oudying observation, and the missing observations are set to be 0 by convention: see, e.g.. [23, section 2.1J. We use q E (0, 1) to denote the observation ratio and p E (0, 1) to denote the ratio of true observations.
Related works. Due to the vast amount of research in this field, our overview will necessarily focus on theoretical investigations of RS. In the case where outliers exist in the measurement model (1), p- 1, a natural formulation is to minimize a smooth least-squares function Σ(j,jee' || |
Tu over X; SO(d), 1 S i S Spectral relaxation and semidefinite relaxation (SDR) typical approaches for addressing this problem [34, 3, 6, 5, 4, 30), where they provide strong recovery guarantees. However, these results cannot be directly applied to the corrupted model (1) due to the existence of outliers (i.e., p < 1) and the sensitivity of the least-squares solution to outlying observations.
Theoretical understanding of RRS still rather limited. One typical setting for theoretical analysis of RRS is the random corruption model (RCM); see Section 2.2. The work [39] introduces least- unsquared formulation and applies the SDR method to tackle it. Under the RCM and in the full observation case where q 1. it is shown that the minimizer of the SDR reformulation exactly recovers the underlying Gram matrix (hence the ground-truth rotations) under the conditions that the true observation ratio p 2 0.46 for SO(2) (and p 0.49 for SO(3)) and n - co. In [23], the authors established the relationship between cycle-consistency and exact recovery and introduced a message-passing algorithm. Their method is tailored to find the corruption level in the graph, rather than recovering the ground-truth rotations directly. They provided linear convergence guarantees for their algorithm once the ratios satisfy p²g² Sllog n/n) under the RCM. However, it is unclear how this message--assinng algorithm is related to other optimization procedures for solving the problem. Let us mention that they also provided guarantees for other compact groups and corruption settings. Following partly the framework established in [23], the work [32] presents an interesting nonconvex quadratic programming formulation of RRS. is shown that the global minimizer of the nonconvex formulation recovers the true corruption level (still not the ground-true rotations directly) when p²g² = 12(log n/n) under the RCM. Unfortunately, the work does not provide a concrete algorithm that provably finds a global minimizer of the nonconvex formulation. In [29], the authors introduced and analyzed depth descent algorithm for recovering the underlying rotation matrices. the context of the RCM, they showed asymptotic convergence of their algorithm to the underlying rotations without providing a specific rate. The result is achieved under the conditions that the algorithm is initialized near X+, q > Oloog n/n),, and > 1 1/(d(d 1) + 2). The latter requirement translates to p 2 3/4 for SO(2) and 2 7/8 for SO(3). primary focus of their research lies in the adversarial corruption setup rather than the RCM.
important to note, however, that the
Main contributions. Towards tackling the RRS problem under the measurement model (1), we consider the following least-unsquared formulation, which was introduced in [39] as the initial step for applying the SDR method:
minimize f(X) XERoaxd
Σ IXXX] - YYyle (3J)EE
subject to X, E SO(d), isisn.
Note that this problem is nonsmooth and nonconvex due to the unsquared Frobenius-nowe norm loss and the rotation group constraint, respectively. We design a Riemannian Subgradient synchronizatton algorithm (ReSync) for addressing problem (2); see Algorithm 1. ReSync will first call an initializa- tion procedure named Spectrin (see Algorithm 2), which is a spectral relaxation method. Then, it implements an iterative Riemannian subgradient procedure. ReSync targets at directly recovering the ground-truth rotations X* E SO(d)" rather than the Gram matrix or the corruption level. Under the RCM (see Section 2.2), we provide the following strong theoretical guarantees for ReSync:

---

(S.1) Initialization. The first step of ReSync is to call Spectrin for computing the initial point X Theoretically, we establish that X can be relatively close to X depending on p and qi see
Theorem 2.
(S.2) Weak sharpness. We then establish a problem-intee intrinsic property of the formulation (2) called weak sharpness; see Theorem 3. This property characterizes the geometry of problem (2) and is of independent interest.
(S.3) Convergence analysis. Finally, we derive the local linear rate of convergence for ReSync based on the established weak sharpness property; see Theorem 4.
The main idea is that the weak sharpness property in (S.2) helps show linear convergence of ReSync to X in (S.3). However, this result only holds locally. Thus, we need the initialization guarantee in (S.1) ) initialize our algorithm in this local region and then argue that it will not leave this region once initialized. We refer to Sections 3.1 to 3.3 for more technical challenges and our proof ideas. Combining the above theoretical results yields our overall guarantee: ReSync converges linearly to the ground-truth rotations X when p²q²= = 22(log n/n);; see Theorem 1.
Notation. Our notation is mostly standard. We use Bddx 3 X = iXi:... X,)
(O(d)" to represent the Cartesian product of all the variables X; E (Odd), 1 i < n. The same applies to the ground-truth rotations X (Xi:-..; :;;). Let & = {j (i.j) E). = (i (i. j) E A], and A & \ Ar We also define A.j A, nAj, for simplicity. For set S, we use [S] to denote its cardinality, For any matrix X, Y E BRndxd, we define the following distance up to global rotation:
dist (X, Y) |X YR [p, where R arg min
|X YY
Pso (X Y).
RESO(d)
Besides, we introduce the following distances up to the global rotation R defined above:
dist (X,Y)
Σ |X YF, dist (X,Y)
max 15i5
|X Y,R
2 Algorithm and Setup
2.1 ReSyne: Algorithm Development
In this subsection, we present ReSync for tackling the nonsmooth nonconvex formulation (2); Algorithm 1. Our algorithm has two main parts, i.e., initialization and an iterative Riemannian subgradient procedure.
Initialization. ReSync first calls a procedure Spectrin (see Algorithm 2) for initialization. Spectrin is spectral relaxation-based initialization technique. Spectrin computes the first d leading unit eigenvectors of the data matrix to form + E R udxd We multiply yn to those eigenvectors ensure that its norm matches that of SO(d)". We also construct Y which re- verses the sign of the last column of o so that the determinants of and differ by a sign.
Then, compute the projection of & and V onto SO(d)". The projection is computed in a block-wise manner, namely
3
Spectrin
A Naive
T Pso(d)) (.:), 1 1 isisn.
Datimation Erowe
where 4,, क Rdxd are the i-th block of o and क, respectively. The projection can be explicitly evaluated as
P.Q.. if (e)( O, 1sisn.
き. = P.QT. otherwise,
10
Here, P., Qi E Rdxd are the left and right singular vectors of o (with descending order of singular values), respectively, and P. is obtained by reversing the sign of the last column of P.. The initial point x is chosen as E or V depending on which is closer to SO(d)".
Figure 1: The average under 100 simulations of the ini- tial distance dist X X*) computed by Algorithm versus naive spectral ini- tialization (i.e., outputting x o directly) with p= 0.2, 9 0.2 and d = 3.
Let us mention that the computation of Y and Steps 5 - in Spectrin can practically improve the approximation error dist(X X*). We demonstrate such phenomenon in Figure 1, in which "Naive Spectrin" refers to outputing x o directly in Algorithm 2.
3

---

Riemannian subgradient update. ReSync then implements an iterative Riemannian subgradient procedure after obtaining the initial point X The key compute the search direction (Riemannian subgradient) V ( and the retraction Retr x (+) onto (d) for
S n. Towards providing concrete formulas for the Riemannian subgradient update, let us impose the Euclidean inner product B) trace A B) as the inherent Riemannian metric. Consequently, the tangent space to (O(d) at R E (O(d) is given by T = {RS : S E IR + S = 0}. The Riemannian subgradient VRJ((X) can be computed [40, Theorem 5.1]
fx,,) = Prx, (vf(Xi)), 1 i n,
(3)
where the projection can be computed as PTx, (B) (x B B B 2 for any B E Rdxd and V (X;) is the Euclidean subgradient of f with respect the i-th block variable X, Let us define fa,(X) == | Y.JlF. The Euclidean subdifferential (f();) with respect to the block variable X; is given by
X,YY,, 0f(x)) 2 Σ (X,) with (X,) = X -Y, if |X,X] Yoylo # 0, j:(E))EE
V Rdxd [ 1 otherwise.
Algorithm ReSync: Riemannian Subgradient Synchronization
Algorithm 2 Spectrin: Spectral Initialization
1: Input: Y E Rudxnd;
Require: Initialize X =Spectrin(Y)) (Algo-
2: Compute the d leading unit eigenvectors of Y: {ui...., ual:
rithm 2), where Y E Rndxnd and its (i,
th block is Yi E Rdxd
3: Set Vnluu Ug, ud] E Runddd and
Set iteration count k =
L Vnluy, u2 ........ Ud-11 uual;
2: while stopping criterion not met do
Compute
Psoraj ( and y
3: Update the step size μs;;
Pso (P):
4:
Riemannian subgradient update:
5: if |
+ S
V then -
x
h++ = Retr x (-MoV
6:
X Φ;
7: else
for si n:
8: X T
5: Update iteration count k k k
9: end if
6: end while
10: Output: Initial point X
Any element f(())) e (x( is called a Euclidean subgradient. In ReSync, one can choose an arbitrary subgradient V (X,)) E af(X.) at X,
Mimicking the gradient method to update along the search direction (X,) provides a point the tangent space Tx, at X,, which may violate the manifold constraint "X SO(d)" One common approach in Riemannian optimization is to employ a retraction operator to address the feasibility issue. For (O(d). we can use a QR decomposition- based retraction and implement the Riemannian subgradient step
X = X; - Vrf
Retrx, (-uūRf(X))
Or (X, (x)((.))).
1sism. n.
(4)
Here, Qr(B) returns the Q-factor in the thin QR decomposition of B, while the diagonal entries of the R-factor are restricted to be positive [7].
Finally, setting X; X X, XI for j such that (i.j) E, μ #4 in (3) and (4) yields
concrete implementation of Step 4 in ReSync and leads to SO(d) 3 x*+1=
for 1 < í < n.
This completes the description of one full iteration of ReSync. Note that the per-iteration complexity of the Riemannian subgradient procedure (n q). and Algorithm 2 has computational cost On
2.2 RCM Setup for Theoretical Analysis
We develop our theoretical analysis of ReSync by adopting the random corruption model (RCM). The RCM was previously used in many works to analyze the performance of various synchronization algorithms; see, e.g., [39, 19, 23, 32). Specifically, we can represent our measurement model (1) on graph G(),E), where V is a set of n nodes representing (xi and E is a set of edges

---

containing all the available measurements {Y,j.. (i.5) E E}. We assume that the graph ς follows the well-known Erdös-Rees Rényi model ((n, q), which implies that each edge (i.j) E & is observed with probability q, independently from every other edge. Each edge (i,j) E is true observation (i.e.,
(i,j) E A) with probability p and an outlier (i.e., (i,j) E A9) with probability the outliers (Ot,) ( (A are assumed to be independently and uniformly distributed on SO(d).
p. Furthermore,
Main Results
In this section, present our theoretical results for ReSync. Our main results are summarized in the following theorem, which states that our proposed algorithm can converge at a linear rate to the underlying rotations X*. Our standing assumption in this section stated below.
All our theoretical results in this section are based on the RCM; see Section 2.2.
Theorem (overall). Suppose that the ratios p and q satisfy
log
p²
-2
n
With probability at least 1 (1//n) ReSync with pst = No7", where poo = O(p² and = converges linearly to the ground-truth rotations X* (up to globul rolation), i.e.
pg 16
dist (x* x*) s E,7 dist.co (x* xx) 807 4k: 2 0.
Here, Eo- ((Vnp'g) and 80 (p²)).
The basic idea of the proof is to establish the problem-intrinsic property weak sharpness and then to derive linear convergence result. However, the result only holds locally. Thus, develop a procedure to initialize the algorithm in this local region and argue that ReSync will not leave this region afterwards. In the remaining parts of this section, implement the above ideas and highlight the challenges and approaches to overcoming them.
3.1 Analysis of SpectrIn with Leave-One-Out Technique
Theorem 2 (initialization). Let X be generated by Spectrin (see Algorithm 2). Suppose that the ratios and satisfy
llg 1
p¹q = -2
Then, with probability at least 1 - (1/n), we have
dist (x*) - -x+)= Vlog Pv/
(Vlogn Pv/ng
and
distoc X xx)==)
(5)
The works [34] and [11] show that exact reconstruction of X is informatiinn-thcorttiaall theoretically possible the condition p²g = ? n/o) holds for the cases = 2 and = 3, respectively. Though Theorem 2 does not provide exact recovery, it achieves optimal sample complexity for recon- structing an approximate solution in the infinity norm. Specifically, Theorem 2 shows that, as long as p²q 2 Cloog n/ n/n for some constant C >> 0 large enough, the -isttanncc dist, (X X²) (i.e., maxigien dist (X,, x)) can be made relatively small. However, the f dist( (X X*) is of the order (1) under such a sample complexity.
The work [26] considers orthogonal and permutation group synchronization and shows that spectral relaxation-basse methods achieve near-optimal performance bounds. Our result differs from that of [26] in twofold: 1) Our approach follows the standard Icave-one-out analysis based on the standard "Dist" (up to ((d) invariance) defined above Lemma 3 in the Appendix. Nonetheless, we have to transfer the results to "dist" due to the structure of SO (O(d) in Lemma 5, which is nontrivial step due to the specific structure of (O(d). 2) Our result can handle incomplete observations (i.e., q 1). In the case of incomplete observations, the construction in (17) the Appendix becomes more intricate; it has the additional third column, rendering the analysis of our Lemma 2 more involved.
We prove Theorem 2 with some matrix concentration bounds and the leave-one-out technique. We provide the proof sketch below and refer to Appendix A for the full derivations.
5

---

Proof outline of Theorem 2. According to (1) and the fact E(O,,) = 0 since outliers are assumed be independently and uniformly distributed on SO(d) in the RCM (see Appendix A), we know that E(Yi)) pqx; "x for all (i,j) E [n] x [n]. This motivates us introduce the noise matrix We = Y - x - X i.e.,
Y Y= P=p
W.
(6)
The condition p²q 22(lonn/n) in Theorem 2 ensures that the expectation pq." X will dominate the noise matrix W in the decomposition (6).
We first discuss how bound dist(XX xx). Notice that X and X are the d leading eigenvectors of Y (after projection onto SO(d)") and p X=T, respectively. We can then use the matrix perturbation theory (see Lemma 3) to bound dist x)) Towards this end, we need to estimate the operator norm [W]] |11,, which could be done by applying the standard matrix Bernstein concentration inequality [38] since the blocks {W,y} } are i..dd white noise with bounded operator norms and variances; see Lemma 2.
We next turn to bound the initialization error in the infinity norm, i.e., dist X X*). Let us use ( X E _ddd denote the m-th block of W Rudxd for 1 m S n. The main technical challenge lies in deriving a sharp bound for the term max (W "m.llr as it involves two dependent random quantities, i.e., the noise matrix W and the initial X that is obtained
by projecting the first d leading eigenvectors of Y onto SO(d)". To overcome such a statistical dependence, we utilize the leave-one-out technique. This technique was utilized in [42] to analyze the phase synchronization problem and was later applied to many other synchronization problems [1, 10, 15, 18, 26]. Let us define
(m)) x + ((m) with (m) WH (Rg4m)) (L#m))
That is, we construct (m)) E Rndxnd by setting the m-th block-wise row and column of W to be O. Then, easy to see that (m)) is statistically independent of W E Rdxad, where the latter denotes the m-th block-wise row of W. Let (m)) be the d leading eigenvectors of (()),
Consequently, (()) is also independent of W Based on the above discussions, we can bound mlll in the following way:
each [I [[WXX' x")) xm)
(I X m| || X S W X (m)) F +
(X X (())
The first term || W m (m)) || can be bounded using an appropriate concentration inequality due to the statistical independence between WTT and x x("), The second term can be bounded as
W - (I I [W - ||X - - (mm) [[F,
in which Wm la can be further bounded by matrix concentration inequality (see Lemma 2) and X (m) F can be bounded using standard matrix perturbation theory (see Lemma 4).
3.2
Weak Sharpness and Exact Recovery
We next present property that is intrinsic to problem (2) in the following theorem.
Theorem (weak sharpness). Suppose that the ratios p and q satisfy
p²q² 2 log n
n
Then, with probability at least 1 1 O(1nn), for any X SO(d)" satisfying dist (X,, O(p). we have
((X)-(Xx
npu dist (X, (x)
Some remarks Theorem 3 are in order. This theorem shows that problem (2) possesses the weak sharpness property [8], which intrinsic to the problem and independent of the algorithm used to solve it. It is known that with this property, various subgradient-type methods can achieve linear convergence [14, 25]. We will establish a similar linear convergence result for ReSync in the next subsection based Theorem 3.
The weak sharpness property shown in Theorem 3 is of independent interest, as could be helpful when analyzing other optimization algorithms (not just ReSync) for solving problem (2). Currently,

---

only few applications are known to produce sharp optimization problems, such as robust low-rank matrix recovery [25]. robust phase retrieval [16], and robust subspace recovery [24]. Furthermore, sharp instances of manifold optimization problems are especially scarce. Hence, Theorem 3 extends the list of optimization problems that possess the weak sharpness property and contributes to the growing literature on the geometry of structured nonsmooth nonconvex optimization problems.
is worth noting that Theorem 3 also establishes the exact recovery property of the formulation (2). Specifically, up to a global rotation, the ground-truth X is guaranteed to be the unique global minimizer of f over the region SO(d)" {X dist ) = (pp)). Consequently, recovering the underlying X reduces to finding the global minimizer of f over the aforementioned region. As we will show in the next subsection, ReSync will converge linearly to the global minimizer X when initialized in this region. However, the initialization requirement is subject to the stronger condition p²q = (log n/n) on the ratios p and g. which is ensured by Theorem
We list our main ideas for proving Theorem 3 below. The full proof can be found in Appendix B.
Proof outline of Theorem 3. Note that the objective function f can be decomposed into two parts:
g(X)
A(X)
f(x)
Σ |x x; X; xiIl++ ((J)EA
Σ
X -
(K))EA=
It is easy to that 9(X*) 0 and g(X) 2 0. Based on the fact that the true observation is uniformly distributed in all the indices, we have E (g(X)) pq EisiJsh || x X;,I 2 xx);; np7 dist. (X, (XX)); ) see Appendix B.2 for the last inequality. A traditional way to lower bounding g(X) using (()( for all X E (O) is to apply concentration inequality and an epsilon-net covering argument. Unfortunately, the sample complexity condition y²y² S2llog n//n) does not lead to high probability result in this way. Instead, our approach is to apply the concentration theory on the cardinalities of index sets rather than on X directly; see the following lemma.
Lemma 1 (concentration of cardinalities of index sets). Given any S2 //ng
Vllog
).
with probability
at least (1/nn), we have
(1 - c)nq S E. & (1+6) e)nq,
(1 -1-e) c)mpg I |Al S (1 +empg,
(1 - e)mpu? < E n1 S (1+ e)mpq,
(1 ()=e)mp?y? N A S (1 + eemppu
for any S i,j S n. See Section 1 for the notation.
We then provide a sharp lower bound on g(X) based on Lemma 1.
Proposition 1. Under the conditions of Theorem 3, with probability at least 1 O(1/n), we have
3npg disti (X,X)) VX E SO(d)".
g(X) 2
(10)
16
Next, lower bound h(X)- h((x)) ElisEE (1X X, O,illo - |x X3 - Oigll=) we first bound
X X Oi
h(X) - 1(x') N Σ
x X X, x; x;
X Xj O
where the inequality comes from the convexity of the norm function U + |U|| whenever X X3- Oz # Then, using the orthogonality of each block of X", we further have
h M(X) 1(X*)
Σ
1|- - X; Xj IF X;
I X;0 X
x,x; 1))
(11)
(.:)).AA
Recall that since the outliers {Oijkanned are independently and uniformly dis- tributed on SO(d), so are (X; X; Josese. This observation indicates that (a))) are i..dd random matrices. Hence, by in- voking concentration results that utilize the randomness of the outliers (O,)) and the cardinalities (i,j) A we obtain the following result.
[I X X; / - X |F
O;O,,;;
7

---

Proposition 2. Under the conditions of Theorem 3. with probability at least 1 O(1/n), we have
7Pd dist (X,X)
h(X) (X*)
(12)
16
for all X SO(d)" satisfying dist. [X, X²) (pp).
Combining Proposition and Proposition gives Theorem 3.
3.3 Convergence Analysis and Proof Theorem
Let us now turn utilize the weak sharpness property shown in Theorem establish the local linear convergence of ReSync. As quick corollary of Theorem 3, we have the following result.
Corollary 1. Under the conditions of Theorem with probability least O(1/n), for any X E SO(d)" satisfying do (X, X = Opp,, we have
(FRf(X), X
rtp4 dist (x, A VRf((X) E ŌRf(X).
(13)
16
This condition indicates that any Riemannian subgradient ( provides a descent direction pointing towards X However, it only holds for X (O(d)" satisfying dist X*) O(p). Our key idea for establishing local convergence is to show that the Riemannian subgradient update in ReSync is a contraction operator in both the Euclidean and infinity norm- corm-induced distances using Corollary 1, i.c., if X lies in the local region, then X ++1 also lies in the region. This idea motivates us define sequences of neighborhoods as follows:
(14) Here, Es = Eu. 6% = 507 where Co. 6g. and y E (0, 1) will be specified later. Thus, these two sequences sets {W+} and {N& will linearly shrink to the ground-truth. It remains to show that X E NWW. oo. then x E NN++1 nW which is summarized the following theorem.
No {X d & Ex} and N/t {X dist (X, (X,X*) S 8x}.
Theorem 4 (convergence analysis). Suppose that dg = O(p²) and Eo = =Vvnpooo) Sery = 1 16 and 24 5y/n in ReSync. If x E N N& for any k 2 0, then with probability at least 1- O(1nn), we have
x E m
Proof outline of Theorem 4. The proof consisted of parts. On the hand, need show that X W/+11 which be achieved by applying Corollary 1. On the other hand, in order to show that k+1 E < we need good estimate of each block of (x)( See Appendix C.
Having developed the necessary tools, we are now ready to prove Theorem 1.
Proof of Theorem 1. Based Theorem 2, we know that X EVP n.o. if and ón satisfy
Eo = 0
Vlog n PVq
v vlog n Pv/ng
and 50 = o
(15)
According to Theorem 4, by choosing dg = (p²²) and E ( (nppg), condition (15) holds when p²q² Ω (logn/n). This completes the proof of Theorem
Experiments
In this section, conduct experiments ReSync for solving the RRS problem both synthetic and real data, providing empirical support for our theoretical findings. Our experiments are conducted on personal computer with 2.90GHz 8-core CPU and 32GB memory. All our experiment results are averaged over 20 independent trials. Our code is available at https: https://github com/Huiiang2019/ ReSync.
4.1 Synthetic Data
We consider the rotation group SO(3) in all our experiments. We generate Xi,.... X by first generating matrices of the same dimension with i..d. standard Gaussian entries and then projecting

---

161
101
daag -X1/
MaACK XX'Vvv
daie -X//UR
330
103
300
(a) 400
(b) 11
600
800 (c)
(d) n 1000
Figure 2: Convergence of ReSync with p = q = (logn/n) n 1/3
MPLES CEMP GCW L
XI/VE
dallk XTIVS
DESC
13
2.5
(a) g 0.2, 0
0.0
(b) - 0.2, 1.0
(c) = 0.2, 0.0
(d) 0.2, = 1.0
Figure 3: Comparison with state-of-the-art synchronization algorithms.
each of them onto SO(3). The underlying graph, outliers, and relative rotations in the measurement model (1) are generated according to the RCM described in Section 2.2. In our experiments, we also consider the case where the true observations are contaminated by additive noise, namely, (oJ))4 in (1) is generated using the formula
YJJ- = Pso(3) (x: X; + GGG.)) for (i.j) E A,
(16)
where G., consists of i..dd entries following the standard Gaussian distribution and controls the variance level of the noise.
Convergence verification of ReSyne. We evaluate the convergence performance of ReSync with 0 in (16). We p which satisfies p²g = log nt/n. We use the initial step size μ40 1/npy and the decaying factor {0.7, 0.8, 0.85, 0.90, 0.95, 0.98] 3 in ReSync. We test the performance for various selected from (400, 600, 800, 1000]. Figure 2 displays the experiment results. can be observed that (i) ReSync converges linearly to ground-truth rotations for wide range of y and (ii) smaller ? often leads to faster convergence speed. These corroborate our theoretical findings. However, it is worth noting that excessively small y values may result in an early stopping phenomenon (c.g., Y S. 0.8 when = 400). In addition. ReSync performs better with larger n, as it allows for a smaller 7 (e.g., 7 0.7 when n 1000) and hence converges the ground- -oound-truth rotations faster.
the noise level
(log n/n) in the measurement model (1),
Comparison with the state-of-the-arts. We next compare ReSync with otate-of-the-art syn- chronization algorithms, including IRLS L12 [9], MPLS [31], CEMP GCCW [23, 32], DESC [32], and LUD [39]. We obtain the implementation of the first four algorithms from https: //github. ceatthub..om/CCooo hemm/ooeeWyeth/DDee
while LUD's implementation is obtained through private munication with its authors. In our comparisons, we use their default parameter settings. For ReSync, we set the initial step size to μo 1/nopq and the decaying factor ? 0.95, as suggested by the previous experiment. We fix n = 200 and vary the true observation ratio (or the observation ratio Q) while keeping 0.2 (or p 0.2) fixed. We display the experiment results for 0 and in Figures 3a and 3b, respectively. where p is selected from {0.2, 0.3, 0.4. 1}. When = 0. ReSync achieves competitive performance compared to other robust synchronization algorithms. When the additive noise level is a 1, ReSync outperforms other algorithms. In Figures 3c and 3d, we present the results with varying chosen from (0.2, 0.3, 0.4,..., .,, 1} for noise-free (a = 0) and noisy (o 1) cases, respectively. In the noise-free case, DESC performs best when 0.5, while ReSync slightly outperforms others when y 2 0.5. In the noisy case, clear that ReSync achieves the best performance for large range of

---

4.2 Real Data
We consider the global aligmment problem of dineesioiln scans from the Lucy dataset, which is down-sampled version of the dataset containing 368 scans with a total number of 3.5 million triangles. We refer [39] for more details about the experiment setting. We apply three algorithms LUD [39], DESC [32] and our ReSync this dataset since they have the best performance on noisy synthetic data, As Figure shows, ReSyne outperforms the other two methods.
0.399456
200
100
0
0.5
1.5
25
0.346297
300
200
100
0.5
1.5
25
300
ReSync 0.316819
200
100
0
0.5
1.5
25
Figure 4: Histogram of the unsquared residuals of LUD, DESC, and ReSync for the Lucy dataset.
5 Conclusion and Discussions on Limitations
In this work, we introduced ReSync, a Riemannian subgradient-based algorithm with spectral initialization for solving RRS. We established strong theoretical results for ReSync under the RCM. In particular, we first presented an initialization guarantee for Spectrin, which is a procedure embedded in ReSync for initialization. Then, we established a problem-intrinsic property called weak sharpness for our nonsmooth nonconvex formulation, which is of independent interest. Based on the established weak sharpness property, we derived linear convergence of ReSync to the underlying rotations once it is initialized in a local region. Combining these theoretical results demonstrates that ReSync converges linearly to the ground-truth rotations under the RCM.
Limitations. Our overall guarantee in Theorem requires the sample complexity of p²q² Q(log n n/n). which does not match the currently best known lower bound p²q 22 n/n) for exact recovery [34, 11]. We showed in Theorem 2 that approximate recovery with an optimal sample complexity is possible. Moreover, we showed in Theorem that exact recovery with p² 22ll nt/n) is possible if we have global minimizer of the objective function of problem (2) within certain local region. However, due to the nonconvexity of problem (2), it is non-trivial to obtain the said minimizer. We circumvented this difficulty by establishing the linear convergence of ReSync to a desired minimizer in Theorem Nevertheless, strong requirement on initialization is needed, which translates to the weaker final complexity result of p q² Silog n/n).
Although our theory allows for p - 0 as n - oo, our argument relies heavily the randomness of the outliers {O.,} and the absence of additive noise. In practice, adversarial outliers that arbitrarily corrupt a measurement and additive noise contamination are prevalent. It remains unknown how well ReSync performs in such scenarios.
The above challenges are significant areas for future research and improvements.
10

---

Acknowledgments and Disclosure of Funding
The authors thank Dr. Zengde Deng (Cainiao Network) and Dr. Shixiang Chen (University of Science and Technology of China) for providing helpful advice. They also thank the reviewers for their insightful comments, which have helped greatly to improve the quality and presentation of the manuscript.
Huikang Liu is supported in part by the National Natural Science Foundation of China (NSFC) Grant 72192832. Xiao Li is supported in part by the National Natural Science Foundation of China (NSFC) under grants 12201534 and 72150002, and in part by the Shenzhen Science and Technology Program under grants RCBS2021 TESS202206090033 060910370801 and 1 supported in part by the Hong Kong Research Grants Council (RGC) General Research Fund (GRF) project CUHK 14205421.
Anthony Man-Cho So is
References
[1] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of Statistics, 1444444452-1474 2020.
[2] Boris Alexeev, Afonso S Bandeira, Matthew Fickus, and Dustin G Mixon. Phase retrieval with polarization. SIAM Journal on Imaging Sciences, 7(1):35-66 66, 2014.
[3] Mica Arie-Nachimson, Shahar Z Kovalsky, Ira Sennllmacher-Shiizemmne Amit Singer, and Ronen Basri. Global motion estimation from point matches. 2012 2nd International Conference on 3D Imaging, Modeling. Processing, Visualization & Transmission, pages 81-88.
IEEE, 2012.
[4] Afonso S Bandeira. Random Laplacian matrices and convex relaxations. Foundations of Computational Mathematics, 18(2):345-379, 2018.
[5] Afonso Bandeira, Nicolas Boumal, and Amit Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163(1-2):145- 167, 2017.
[6] Afonso Bandeira, Amit Singer, and Daniel A Spielman. Cheeger inequality for the graph connection Laplacian. SIAM Journal on Matrix Analysis and Applications, 1414):1611-1630, 2013.
[7] N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre. Manopt, a Matlab toolbox for optimization on manifolds. Journal of Machine Learning Research, 15())1145--1459 2014.
[8] James V Burke and Michael C Ferris. Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization, 31(55) 1993.
[9] Avishek Chatterjee and Venu Madhav Govindu. Robust relative rotation averaging. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4))958-99) -900,97222200 2017.
[10] Yuxin Chen, Jianqing Fan, Cong Ma. and Kaizheng Wang. Spectral method and regularized MLE are both optimal for top-K ranking, Annals of Statistics, 47(4):2204-2235 2019.
[11] Yuxin Chen and Andrea J Goldsmith. Information recovery from pairwise measurements. In
2014 IEFE International Symposium on Information Theory, pages 2012-2016. IEFF, 2014.
[12] Mihai Cucuringu, Yaron Lipman, and Amit Singer. Sensor network localization by eigenvector synchronization the Euclidean group. ACM Transactions Sensor Networks, 8(3):1-42, 2012.
[13] Chandler Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. III. SIAM Journal Numerical Analysis, 7(1):1-46, 1970.
[14] Damek Davis, Dmitriy Drusvyatskiy, Kellie J MacPhee, and Courtney Paquette. Subgradient methods for sharp weakly convex functions. Journal of Optimization Theory and Applications, 179(3):962-99) 2018.
11

---

[15] Shaofeng Deng, Shuyang Ling, and Thomas Strohmer. Strong consistency, graph Laplacians, and the stochastic block model. Journal of Machine Learning Research, 22(1):5210- 5253, 2021.
[16] John C Duchi and Feng Ruan. Solving (most) of of quadratic equalities: Composite optimization for robust phase retrieval. Information and Inference: A Journal of the IMA, 8()):471-52,, 2019.
[17] Anders Eriksson, Carl Olsson, Fredrik Kahl, and Tat-Jun Chin. Rotation averaging with the chordal distance: Global minimizers and strong duality. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(1):256-268, 2019.
[18) Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An 1.0 eigenvector perturbation bound and its application to robust covariance estimation. Journal of Machine Learning Research, 18(207):142,, 2018.
[19] Tingran Gao and Zhizhen Zhao. Multi Multi- fuquuny phase synchronization. In Proceedings of the 36th International Conference on Machine Learning, pages 2132-2141. PMLR, 2019.
[20] Venu Madhav Govindu. Lie-algebraic averaging for globally consistent motion estimation. In CVPR 2004, volume I, pages H-I. IEEE, 2004.
[21] Richard Hartley, Khurrum Aftab, and Jochen Trumpf. LI rotation averaging using the Weiszfeld algorithm. In CVPR 2011, pages 3041-3048. IEEE, 2011.
[22] Richard Hartley, Jochen Trumpf, Yuchao Dai, and Hongdong Li. Rotation averaging. Interna- tional Journal of Computer Vision, 103(3);667300) 2013.
[23] Gilad Lerman and Yunpeng Shi. Robust group synchronization via cycle-edge message passing. Foundations of Computational Mathematics, 1266):166511741 2022.
[24] Xiao Li, Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, and Anthony Man-Cho So. Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM Journal on Optimization, 1103):1005-16444 2021.
[25] Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and René Vidal. Nonconvex robust low-rank matrix recovery. SIAM Journal on Optimization, 30(1):660-66) 686, 2020.
[26] Shuyang Ling. Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods. Applied and Computational Harmonic Analysis, 60:20- 52, 2022.
[27] Huikang Liu, Man-Chung Yue, and Anthony Man-Cho So. A unified approach synchroniza- tion problems over subgroups of the orthogonal group. Applied and Computational Harmonic Analysis, 66:320-372, 2023.
[28] Daniel Martinec and Tomas Pajdla. Robust rotation and translation estimation in multiview reconstruction. In CVPR 2007, pages 1-8. IEEE, 2007.
[29] Tyler Maunu and Gilad Lerman. Depth descent synchronization in SO (D). International Journal of Computer Vision, (31:44668-998) 2023.
[30] David M Rosen, Luca Carlone, Afonso Bandeira, and John J Leonard. SE-Syne: A certifiably correct algorithm for synchronization over the special euclidean group. International Journal of Robotics Research, 38(2-3))95-125, 2019.
[31] Yunpeng Shi and Gilad Lerman. Message passing least squares framework and its application to rotation synchronization. In Proceedings of the 37th International Conference Machine Learning, pages 8796-8806. PMLR, 2020.
[32] Yunpeng Shi, Cole M Wyeth, and Gilad Lerman. Robust group synchronization via quadratic programming. In Proceedings of the 39th International Conference on Machine Learning, pages 20095-20105. PMLR. 2022.
12

---

[33] Yoel Shkolnisky and Amit Singer. Viewing direction estimation in cryo-EM using synchroniza- tion. SIAM Journal on Imaging Sciences, 5(3):1088-1110, 2012.
[34] Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harronic Analysis, 30(1):20-36, 2011.
[35] Amit Singer, Zhizhen Zhao, Yoel Shkolnisky, and Ronny Hadani. Viewing angle classification of cryo-electron microscopy images using eigenvectors. SIAM Journal on Imaging Sciences, 4(2):723-759, 2011.
[36] Anthony Man-Cho So. Probabilistic analysis of the semidefinite relaxation detector in digital communications. In Proceedings of the 21st annual ACM-SIAM Symposium on Discrete Algorithms, pages 698-711. SIAM, 2010.
[37] Gilbert W Stewart and Ji-guang Sun. Matrix Perturbation Theory. Academic Press, 1990.
[38] Joel Tropp. An Introduction Matrix Concentration Inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
[39] Lanhui Wang and Amit Singer. Exact and stable recovery of rotations for robust synchronization. Information and Inference: A Journal of the IMA, 2(2): 193,,199900000 2013.
[40] Wei Hong Yang, Lei-Hong Zhang, and Ruyi Song. Optimality conditions for the nonlinear programming problems on Riemannian manifolds. Pacific Journal of Optimization, 10(2):415- 434, 2014.
[41] Stella Yu. Angular embedding: A robust quadratic criterion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(1):158-173 2011.
[42] Yiqiao Zhong and Nicolas Boumal. Near-optimal bounds phase synchronization. SIAM Journal Optimization, 28(2):989-1011 2018.
13

---

Contents
1
Introduction
2
Algorithm and Setup
2.1
ReSyne: Algorithm Development
2.2
RCM Setup for Theoretical Analysis
3
Main Results
3.1
Analysis of Spectrin with Leave-One-Out Technique
3.2
Weak Sharpness and Exact Recovery
3.3
Convergence Analysis and Proof of Theorem
8
Experiments
4.1
Synthetic Data
4.2 Real Data
10
Conclusion and Discussions on Limitations
10
A Full Proof of Theorem
15
A.1 Initialization Error in Euclidean Norm
16
A.2 Initialization Error in Infinity Norm
17
B Full Proof of Theorem
18
B.1 Proof of Lemma
18
B.2 Proof of Proposition
18
B.3 Proof of Proposition 2.
19
Full Proof Theorem
C.1 Proof of Corollary 1
21
C.2 Proof of Contraction
22
14

---

A Full Proof of Theorem 2
In this section, we present the full proof of Theorem 2. We will use the notation defined in the proof outline of Theorem 2 in Section 3.1.
Firstly, we know that
(1 pq) X x
with probablity pq-
Wiy
Oi pq x x
with probablity (1 p)q.
(17)
- x
otherwise.
Since Oij is assumed to uniformly distributed on (O(d) in the RCM, given any matrix Q E SO(d). it is easy to see that Oij Q is also uniformly distributed on (O)d), we have
i() = E(O; = E(O,,) Q, AQ E SO(d).
Let ENI E SO(d), k + I denote the diagonal matrix whose k-th and 1-th diagonal entries are -1 and others are 1, then have ((O;;) E(Oi,) EsI, which implies
dE₂):;)) B(O;)) (Ei2 E2 +
Eai) = (d - (0))))(Ois)).
Thus, we have E(O;,) 0. Then, it is easy to see that E W))) = 0 and
Var w,) (1 pp) (1 4)p²g + p) + I² I= - p'))
(18)
Based on the above calculations, we can derive the following Lemma, which is direct result of the matrix Bernstein inequality [38]. Similar results can also be found in [42, Lemma 9], [27, Proposition 3], and [26, Eq. (5.12)].
Lemma 2. With probability at least (1/nn), the following holds for any m E [n]:
[W|22 O (Vnglogn).
| (m(m))l l|2 O (Vnqlogn). W = O (Vnqlogn)
Proof. Note that W Eicr W where Wii)) e Radxnd denotes the matrix with the (i,j) and (j.2)-th block equal to Wi and W and others equal to 0. So (W(+)) are iidd centered and bounded random matrices. Besides, we have
||BWW 1l1
Σ LE (W())) 2(n 1)ll Var W O(nq).
According to the matrix Bernstein inequality [38], we have that [ 1|2 = O (vng log n) holds with probability at least - (1/n"). The above argument also holds for each W (m)) then taking a union bound over the choice of E [n]] yields the second result. For W.. we have
W max 1|
[uull2 2 max [Wmull: W
||
which gives the last result.
The following lemma follows from [13]; see also [26, Theorem A.2]. [42, Lemma 11] is a special case where Before that, we need introduce the distance up to global orthogonal matrix:
Dist (X,Y² Y) X Y YR'le where R = arg min X Y I Pora (xT))
REO(d)
Lemma DaaissKahan sin θ Theorem). Suppose that A, E Caxn are Hermitian matrices and À A E. Let = (A) >at (A) be the gap between the d-th eigenvalue and + 1-th eigenvalue of A for some S d S n 1. Furthermore, let U, Ú be the d-leading eigenvectors of A and Å, respectively, which are normalized such that U
|| = Vnd. Then, we have
2 EU
Dist(U,ū) < 8
(19)
E
15

---

A.1
Initialization Error in Euclidean Norm
Based on Lemma 2 and Lemma 3, we have the following bound on Dist. Note that the notations +, V, $ V used the following analysis are defined in Spectrin (i.e., Algorithm 2).
Lemma 4. Let 4 and T (m) be the d-leading eigenvectors of Y and Y (m), respectively, which are Vnd. Then, we have
normalized such that || = -| (m)
|| =
v Vlog nt
Dist Φb xx =
and Dist x(m)) = O(1)
(20)
PV4
hold with probability least 1 (11nn)
Proof. Let us Choose (m)) and E AW (m W- (w((m) in Lemma then A Y. U ((m) and Ü Φ. Since {(m) is independent of A AW()), similar Lemma 2, we apply the matrix Bernstein inequality [38] to obtain, with probability at least 1 O(1/n²), that
EEU F = (( (mm))) || = 0 logoon) n).
In addition, (m) = pq
X X X T (m)) implies that
8 >a (Y A i (m)) 2 X-1) where the second inequality holds due to Xa(X--xT) n and the last inequality is from Ad X = n and Lemma 2. Based on the condition that p²q = log as long as
2 npy - O( ng log n).
p²q Clogn for some large enough constant C, we have
1
E l npq O(V logogn)
E
npg O(V log log n)
2 npp.
where the second inequality holds because of E by applying Lemma 3, get
2 +
W( = ((v ng log n). Hence,
V2 EU
O
(Vng ng loglogn))
Dist o (m))
= O()
(21)
E
npg
where the last inequality because of P Q2 v log n/n). Similarly, by choosing A pqx* X and E W, we can show that
W
X o (ovVoog Pvq
Vlogn
Dist +, x*)
ppp OVyng logn)
npg
Here, the last inequality holds because |||]| = O log (see Lemma 2) and the fact that X || = Vnd.
Following the same analysis as in Lemma 4, we also able to show that Dist V X*)
where V reverses the sign of the last column of & so that the determinants of 4b and V differ by a sign. However, Lemma 4 only provides the upper bound on "Dist", i.e., the distance up to orthogonal matrix. The following lemma translates the result that on "dist".
O Alg
Pv
Lemma 5. Suppose that g p-- @1FF
|| I
- le,, where T6 = Pssoaa
and = Pso (L)
then we have
< Vlogn p
dist 4, X*) Dist( p. xx) o
Proof. Based on the structure of (d)) and SO it is easy to see that
Dist 4b x*) min (dist 4 X*), dist (V) X))
Our remaining task is to prove Dist 4 X dist ④b x*) based on the condition that | + F
V L/.. If Dist db, X*) dist V X ). then we have
o v llggn
Dist (b, X*) dist v X
IV
16

---

where the first inequality holds because L is the projection of v on SO(d)". It is easy to see that
f|| + v V/r || Psocay + {)][ + + P P(otd);so(d)" (+)]l 2 2yn.
The equality holds because the mapping that reverses the sign of the last column of matrix is bijection between (O(d) and O(d) \ (O(d), and the inequality holds since the minimum distance
between (O(d) and ((d) SO(d) is 2. Under the condition that p²q = Ω
2 as long as
q²q
C'lggn for some large enough constant C, could have c +
V l
26
0
1 PV7
2/Ti, which contradict the above inequality, Thus, we have
dist ④. x') Dist Φ, x-) -0 ( (Vlogm)
Pv/9
A.2 Initialization Error in Infinity Norm
Next, based the Davis-Kahan theorem, can bound the distance between X and X in the infinity norm, which is stated in the following result.
Lemma 6. Let & be the d-leading eigenvectors of Y. Then, we have
(Vlog pynqq
dist Φ x²
(22)
holds with probability at least 1 - O(1/n).
Proof. Let I argmin
T (m))
We can compute
W ml
|
W T
o (m)
"1 || + | m ( - + (m)
(23)
W Φ (mm)
W m 1mll2 1 (mm)
II
F.
The fact that (m)) is independent from W implies
| m (m²)
|| O
O(vnq log n), so we have
( || O nggog) (1 + 0(1) ng
(24)
Next, let II = argmin || X F. then we have
Y m pq T
(W m npq pq
( X'II' + (W
Since & is the d-leading eigenvector of Y, we have Y + with Σ E Rdxd consisting of the d-leading eigenvalues of Y. Applying the standard eigenvalue perturbation theory, e.g., [37, Theorem 4.1 1], we have
ΣΣ npg ||2 = O O(v ng log n))
Based on the assumption that p²g 52 log
we can show that Σ > IopeT. Note that Y +Σ
implies o m
(Y Σ for each [n.. then have
4
P < 3mp4
+ m S
pp
$ mmll
(W$)),m
m
S 22 2vd,
3npq
3npg
where the last inequality holds because (24). Therefore, for each m E [n]].
X [pq 3mju
4
X-
4 Jn
X Emlle S 4vd
and
m
3
upq(# $m X m IT*) = $ (npq E) + + E - npq X
m
o (bpq)
E) + ( m
npg X II.
This further implies mpq Φ X
II"
Σ mpq 2 |F pq X x o - X (W ) l
F
<2 W + Vapgi
X X r + O O nq((ogn)
where the last inequality holds because of Lemma 2 and Lemma 4. This completes the proof.
17

---

Finally, since X = Pso(dd" (D), according to Lemma 2 in [27]. we have
dist x*) S dist Φ, x*) and dist x*) 2 2ist ($, x'),
which complete the proof of Theorem 2.
B Full Proof of Theorem
In this section, provide the full proof of Lemma Proposition 1, and Proposition 2, which finishes the proof of Theorem 3. To simplify the notation and the theoretical derivations, we assume without loss of generality that X I for all 1 S i S one separately rotate the space that each variable X; lies in such that the corresponding ground-truth X is rotated to identity [39, Lemma 4.1J. Consequently, we have Yi for (i, A.
B.1 Proof of Lemma
For each S sis 1 - Eissen 1),, where (-) denotes the indicator function w.r.t & Based on our model, Σisjen l (), follows the binomial distribution B(n, q). According to the Bernstein inequality [38], for any constant E (0, 1), have
2 9²
Pr
Σ ISiS"
Ie(() ng 2 enq
$ 2xxp
Eisisa F (i)) + +eng/3
je2n²02 ng + eng/3 /
(- (-geng)
3
= 2xxp
S 2exp
The last inequality holds because of < 1. Therefore,
Pr
U Isisn
{ ngl 2 eng]
S
2n exp
3
2nq
2 n2
(25)
8
where the last inequality holds because we assume that
VBlogn Vrpu
Similarly, we have
Pr
npal 2 enpq) s 2n exp (lAi
(-8 Enpo
(-
3
S
2
(26)
Isisn
n2
Pr
f1 n Asl npu? - 2
enpo?)
s 2n² exp
(
--
@mpo?
3 npga
I
(27)
Isigsa
8
and
3 nnpp
2
Pr U
{1Aip] - -mppp ż enprga]
S 2n exp
-
9²
(28)
ISijsh
8
Hence, complete the proof of Lemma I once 4.
B.2 Proof of Proposition 1
We can first compute
Σ
|X
X1 5
Σ
(I|X:
XxI1F ||X, Xx((F)
Ass
154jj5
151,5n
kEdly
(29)
$ (1 el=pppppq
1
Σ
Σ -1|X- X + |X,, Xxlle).
ISijEn kEAi
Here, the first inequality comes from the triangle inequality, while the second one follows from Lemma 1. Now, invoking Lemma 1, which tells |Ax < (1 + c)mpq, gives
Σ 1X
Xx|[=
Σ Σ
|X:
X
ISiJEREEAy
ISiSnREA RE JEAÀ
(1 + E)rpa
Σ
Σ
X
XxIlF
18

---

(1 + e)mpa Σ
1x, -xllF=
(G,))A
By symmetry, we conclude that
Σ Σ (II; XxIr+IIx, XxllF) S 2 + c)npg
Σ
||: - x,llm
(30)
IS An,
(iJ)EA
Furthermore, we claim the following bound for any X SO(d)":
Σ
|X X,y1 F 2 dist (X, X))
(31)
Combining (29), (30), (31), and the fact g(X) = Ee.DEE X; X,|1 establishes Proposition 1.
||
Hence, it remains to show (31). First of all, according to the triangle inequality, we have
Σ 1sig5n
|
1|r 2
Σ Isisn
nxx, Σ x S
= n Σ X Isisn
X F,
(32)
where X x - X, can be taken as a diagonal matrix (since the Frobenius norm is invariant up to a global rotation) with its first (d 1) diagonal entries being positive. Finally, applying the following lemma to (32) provides (31).
Lemma 7. For any A E (O(d) and B Diag(bi,..... ..., ba) satisfying bi...., ba- E [0, 1] and
ba E [1,,1), we have
|| A
B F
2 2
1 I|
Proof. It is equivalent to show that ||A
B B 2 1 A 1 1/ Since A E SO(d), we simplify as
d + A, I 4B +
B 2
Σ 1 A 4b,) 2b 2 0.
(33)
To prove (33) holds for all A E SO(d), we choose A argmin AeSO(d) (A, I-AB) Pso (4B-
I). It is easy to see that Á is also diagonal matrix. For any 1 5 d - 1, we have
2(b: 1)2
A 1;
1 (1 4b;) + 2b}
26 + 4b,,
A --
So it is always nonnegative since b. 2 0 for any
< < d 1. For the last summation in (33).
on the one hand, if A = then + Aat(1 4ba) + 2 = 2(bs - -1)² 2 0. On the other
hand, if Add = 11, then there exist another < k < d 1 such that Ask -1. So we have
(1 + ARt(1 4bg) - 26 + (1 - Ada(1 4bb) + 203) 263 + 26 + 4(b, + ba) > 0. The last
inequality holds because [bal S by- We complete the proof.
B.3 Proof of Proposition 2
Based on (11) and our simplification that X; = I, 1,15 S i < n, we have
O, x X, 1).
h(X) - h(x*)) 2 Σ
(34)
|1 0
(
Let A = E T-oy
Zz -
I-0g
La-(i)) - (1 p)g... and Z Bdddxdd collects each
F I. Zi in its (i, block. We can compute
x X, 1)
Σ
I
Σ
(ZB +1- (1--)),,,
11
(AJ)EA=
181
<
Σ
X, -
11)
(35)
15655
19

---

Σ IStJ5n
(Zig (X: 1) (x 1) +X: 1)T (X; 1))
To bound the first term in (35), we can proceed as
Σ (0- - 17 =
11 p)qA,
Σ x;
Σ Xi
- n²1
IS155n
1=1
i=l
(1 p)gA,
Σ X, +nl
Σ X nl
n Σ X nT
(1 D)AA
Σ
X, + nl
1=
< 1101 A)
X; +nl
X; nl
1=1
$ 2(1 p)an|IAA1E
Σ X; nI
(36)
Here, the second equality true since Σ i==
X, can be taken as a diagonal matrix. According to [39,
Lemma A. we know that |||||F- = we know that
E
1-0
311+
S - for all d 2 2. On the other hand,
R
n nf
(ist(X, x+)²
Σ
|X 1 = trace
nt -
-
22 Σ 22
(37)
i=1
i=1
where the last inequality holds because nI - Ei= X; is nonnegative diagonal matrix. Therefore, we obtain
S (1 pmqm
Σ (U- 1)
dist [X, x2
V2
IStJSn
(38)
(1
pmgm
n1
max | 1| Σ Xx Ill..
<
v2
To further bound the second term in (35), we can proceed
Σ
(Zig - (x, I) + (X: 1)T + +(X, - -1))
154J5n
<(X - In) 1-) - ("X +2 +2
Σ
Σ I8isn
Zzj. X, 1)
Isignn
(39)
2 11lpp1 X - 1 +2 Σ
Σ Zij
|X, - I|p
Isish
15j5n
< Z + 2 max
Σ ZE
Σ Isisn
X FlF:
Isisn
15JSA
where I" E Ranxdd collects n identity matrix together and the last inequality holds because |
10 = Eisisn |
1X-11', 11% S (I.x ||||||||XXXXX
- -l]e- = =2vd E || - -1]ee.
20

---

Using the randomness of Otj, we claim that with probability at least 1 4d/n, we have
Z opp I (n((1 p)q log n,
and
Σ
Zi
S
188(11 plglogn.
(40)
1515
F
Combining the above bounds gives h(X)= -h(x")
2 22vV++ 1)V 8m(1 p)g logn +
(1 - pm
V2 max |X -11lF)
Σ
||: |X: - 11/
(41)
1545n
npa
dist (X, X*);
16
where the last inequality holds because we assume p²q² = Q log
max;
|X; - I1
dista (X, x+) =Op)) and Eisisn X - /||= - dist (X, X*)
Finally, it remains to show that the two inequalities in (40) holds with probability at least 4d/n. It is quick to verify that E 23)) = 0, 0 [2j I 1 (1 p)q/ A A|r 2, and
E E(ZZ) BIkDiag
Σ B(ZzzZT)). .... ΣE B(Znn Zmn))
Σ B Zij Zin)) @ In
(I-0s,(I- -1- 8 In:
n1 p)
|I-OA 1I-0i
where BIkDiag(-) means the block diagonal matrix, & means the Kronecker product and I, denotes the n-by-n identity matrix. Thus, we have Bernstein inequality [38], we have
[E [l I n11 p)q. According to the Matrix
-An(1 p)q log n
Pr (1 [ S <88(11 - plglogn) 2 2 22ddexp
n(1 (11-p)q 2 8n plglog n/3
2d
n
(42)
Here, the last inequality holds because assume 2 8n(1 log n/3 S n(1 p)g. which is true as long as 22(log n/n).
For any fixed 1 < i < n, a similar argument based on Matrix Bernstein inequality [38] shows that
-4n(1 - p)g log
Pr Σ f
Zujll F S V8n(1 - p)g log
2
2dexp
n11 p)g + / /8((1 p)q logn/3
2d
2 n²
(43)
which implies Pr (max: E, Zoill < v /8n(1 - p)g log 2 2d/n.
C Full Proof of Theorem 4
C.1 Proof of Corollary
Combining the convexity of ff and Theorem 3, we have
Σ
X X; f(x*) f(x) (v)(x),'--XX vVS(x) [x(x).
15t5n
(44)
21

---

for all X E SO(d)" satisfying further compute
= =O(p). For any Rx((X)= E (x)(X), we can
V x-) Σ
(xi), (x;-X) (xxx)
IsiSn
Σ
|V
1P (X: - -x;)lr-
15i5n
On the one hand, notice that
P x (X, - X;) =X,- - X P Pix, (X:-X;) X;)
=X, (X, X;) (X:-x;) x.) 12
=X,(X; - ()))(, -x;)/2,
which implies
IP X;)II - -X - (x) -X,I, S 1 < -
- 1
On the other hand, according to Lemma I, with probability at least 1 - ((L/n), for any i E [n].
[(xx(l S |V
Σ Ja (X.)
S Σ
s slE,1 S 2n4,
JE&
JEE,
where (X,) E. satisfies [iV X,) F S 1. Hence, we have
( S nq Σ
|X - X S
T:p
Σ X -X,1
16
ssisn
for any X such that dist.o ( (x, x*) v te- Invoking the above bounds into (44) yields the desired result
(vR((X),--X0) X - =(,(x))((x)) x
2
Σ
|x
-1;1--
16
15i5n
C.2 Proof of Contraction
Let us first present some preliminary results, which will be used in our later derivations. By noticing that f((,,) = Ejee, (X,) where Vis (X,) E (Xi,, we define
(i(X,) = Σ Vii (X.), VI(X,)
Σ (X.)
JEA:
JEENAA
Recall that V R xx) = Prx, (X.)) and R = PTx, (Vh(),)). Similarly, we have
VS(X,) = Vg X,) + V)(X,) and (x)) = ( + (X,)). Furthermore, the QR decomposition-
retraction satisfies the second-order boundedness property, i.e., there exists some . 2 such that
X 1; |||etrx (-uNVRs(xt)) X;I
(45)
< <IIx (xt)) - + M (
Recall that V &x((( = { + RRh(X (+)), we have
[xx]((())|= W |iog X )ll |( I
(46)
< 5v 25nng + (1 + e)mpp S (1 + 26)np4,
where the second inequality comes from
Σ (x,)
S Σ
| SlAi (11+s(1e))mp)))
EEA.
GEA.
F
22

---

and Lemma 10 and the last inequality is due to the choice 60 - <<pp²/5 (i.e., du = O(p))) Thus, by choosing 1 O dz ), and dn (p²), the second-order term M / (x, 0 which is a very high-order error. In the following analysis, we will ignore this term to simplify our derivations.
Using the above preliminaries and Corollary 1, we are ready to establish two key lemmas, which show that if X E N n n then X E NN (Lemma 8) and X E Nk+1 (Lemma 9), respectively. This completes the proof of Theorem 4.
Lemma 8. With high probability, suppose that X* E N n. pe O (2), and
6a 0(p)), and Eo - O (V/npddo),
(47)
then X E N
Proof. By ignoring the high-order error term in (45), in order bound compute
| - X ||3 we first
X k+1
X+1
| x; S
Σ
x pe (x(((( 1
Isisa
||
x x1 - 2 ( [
x x
+
(RI((*))
Then, according to Corollary 1, we have
(ūnf(x²), x
X N kpy
Σ
X - x;11 >
npg
Σ
X X
16
166
I ISiSn
Ssisn
npq
X
X * PN
165
where the second inequality holds because above two inequalities gives
| -x;1pe S 5x (i.e., X E N
Combining the
X
s++1
X
11
S
1 - p4
npq
- | + 2 V fl )|
86k
1 (1 8
mg)
X1 + (1+ 22n=n2n 2²
where the last inequality is due to (46). Since μı = ( and Eu = a @uppoo (i.e., EK = @(Vnpgox), we have n n²p²0² N² = O(pnE2) which implies
| 1 < [1
pq
c
pq
5k
22
(1
pq
Ct =
8
16
16
This completes the proof.
Lemma 9. With high probability, suppose that X E N N be uh 0 and
8n = 0(p2) and 3 = (vvippooo),
(48)
then X E NN+1
Proof. As stated the beginning of Appendix B, assume without loss of generality that R = I and X; = I for all 1 < i S n. We divide the index set [n]] into three sets
Ij { ||x - I < 5x }.
6%
36
I = i
<
x
k - I
[p S
4
4
4
{
35k
and
Ig =
i
<
| - -11e= S 8807
4
For any i E I, IZ, we have
36g
- k - - Vx((t) - I| < X I1 + pk (xF(( |
-
+ 2pauaa S 6x+1.
4
(49)
where the last inequality holds because we choose μn 0 (4) <
6x
16n
23

---

It remains to consider the case i E Iz. Firstly, it is easy to see that
5x I2 Tsl
dist( X x
Σ
1
(6))l
16
iEIa Is
Note that we have 2
dist x'
I
16 %
(npp)) according to the assumption
62/16
Eo O( O(vpppbo)) Hence, for any i E Iz, we have
X Xj
X; - X, V)(X,).
(((X))
E
Σ
(50)
X
X,11æ
jEA,NL
JEANZ
Since [Zg UZsl = ((pp)), we can choose to properly such that [22 UZsl S empg. Then, we have
[4& I1 S I2 I S enpg and |4 nII 2 |A| - |A, I1 2 (1 2c)mpq.
Let us Vg (X;) to denote the first term on the RHS of (50). We have
X; Xj
X
I I-X, X;
(x,) Σ
Σ
+
X;
X
Xylle
|X Xi11r
jEA,CL
JEANI
(51)
I I-X; X,
o o I) +
Σ
X
X,Ile'
JEAnZ,
1 where EjEdinZ, 1xyl=;
For the last term in the above equation, we have
Σ
X-X; X,ررæ
Σ
I- X
6%
Σ
1 X
|
|
-
X,1Iæ
4
JEA:NT,
JEAiNZ,
JEA.NT
In addition, the projection of X; I onto the cotangent space can be bounded as
||PT (X, 1) = |I(x; 12 = /2,
which implies that V RR.
(X:) = -PTx, (i satisfies
0 540
|V (X;) -X( D)lr S
2
2
Then, the fact (x.( VRO + +PIY (EjEA\I
X.-X,
Vx)((,) implies
IX.-X,
[izf(X,) - 1)ll S V (X,) o(x, - 1)ll= + |4 \ | + Fx)(X,)
540 enpq + 5 250ng.
s
Next, motivated by the update of ReSync, we can construct
X - V ((x") - - (1 (xx) - 1) + MA (R(((X) - o(x:- - -))),
which implies
850
x - na (RJ(Kt) - 1 S(1 - |
X - -TII Mr
+
+ enpa - 5 25nmg
4
2
<(1 ux0)or + M
+ empy + 3v /2oong
2
06.0 empa - 5 22ong)
-5p - M4
2
(52)
In order to further upper bound the above inequality, we can compute
Σ
Σ
X
X1
X I| + |X, - I
JEA,NZ
JEA,NZ
> 14: n nIn = 4(1 - 26 26)
4
58
58
24

---

where the second inequality holds because
X 1| +
| - I 1 S 55%/4 as j E LT It implies
empn 5
2(1 2c)
mmpa /v 26 2 npa
2
5
4
By plugging the above bound into (52) and ignoring the high-order error term in (45), we complete the proof.
Finally, present Lemma 10 and its proof.
Lemma 10. With high probability, the following holds for all X A
(x,) || - 28onq Vi [n].
(53)
Proof of Lemma 10. Firstly, define Ōij = Oiÿ x X then
X; 0
I - X
I I- X,
V)(X,)
Σ
Σ
X; Σ
X Oz XlIF
X - Oi
|| I -
jEE,/A.
jEE./Ai
jEE./Al
The fact that X E No. implies that |X Xjlr IF I 26,, i.e, I X ||r S 26 For any
||Ois I|| 2 25g, we have
Ög I O
I Ö,
I 1
<
|| Oijle
|[ 0
||
|I- Ozj |F
F
1-
I O
< 22/200
0
I Ozjl
where the last inequality holds because
- Ó-
1 - Öigle
Oigllr
| 0
|| -Oigle
[[- 0 11
1 - Ó:g ||
I - O Lg ||F
I 1-jyll
ÖzjllF
10; O || 0
|| - -Ojjll
x; X. ||F
S /280.
1 1-0
and
I O
I T-0
|0: - Ó || | - X, |F
I 250
|1 - |[ - - 0,l
1 O = |
Let L. & |1[0,, - I| S 26 According to the fact that [E//As) S (1+ c)nq and
the randomness of Ozj. easy to show that | S 220ngg hold for all 1 S n with high probability. Thus, by splitting the sum Ejee/A, in to two parts: j t; and j $ 4,, we have
I- O
I- Oig
Σ
Σ
S 4v 250nng.
(54)
1I O jEE,/N;
I
O |r
JEE,/A:
F
Besides, since O is uniformly distributed on SO(d), according to Lemma A. in [39], we know that IE probability,
1-0 11,00 c(d)I. Then, the matrix Bernstein's 's inequality [38] tells us that, with high
I I - 18//2
Σ
$ 22ōng..
(55)
I - Ozyllr
JEE,/D
F
25

---

This, together with (54), implies that
I On - |2//2, c(d)
Σ JEE./A.
S 55v 280nq.
1I Oiyle
P
The fact that V)(X)) Σjees/A: 1 1-0;; X; implies that 11,,,
VM(X.) - | c(d) X 55v 26nng.
(56)
We complete the proof by taking the projection operator vR)(X,, = Prx, (VI(x.) and the fact that PTx, (X;) = 0.
26


Reviews:
[{"review_id": "dMUN96nfpb", "reviewer": "Reviewer_m1vD", "summary": "The paper proposes a Riemannian subgradient based algorithm for the robust rotation synchronization (RRS) problem. RRS involves recovering the absolute rotations of objects from the possibly corrupted/noisy relative rotations between pairs of objects. The problem setting involves two ratios: q \\in [0,1] denotes the observation ratio and p \\in [0,1] denotes the true observation ratio. The paper pose the problem as a (non-convex and non-smooth) least-unsquared minimization formulation over the rotation group. The proposed method ReSync has a spectral relaxation based initialization procedure, which is followed by Riemannian subgradient iterations. The main contribution of the paper is to show that under random corruption model (RCM) setting: (a) the proposed initialization (X^0) can be relatively close to true solution (X^*), depending on p and q, and (b) given the initialization guarantee, the Riemannian subgradient descent show local linear rate of convergence. Overall, the paper show that ReSync converges linearly to the ground-truth rotations when p^7 q^2 = \\Omega(log n / n). Towards the end of the draft, the paper has few experimental results that compare the proposed algorithm against state-of-the-art.", "questions": "Please look in the weakness section.", "limitations": "not applicable", "rating": 6, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "The paper presents an interesting approach for recovering ground truth (X^*) in RRS problem. The key theoretical guarantees for ReSync comes from a) an initialization procedure SpectrIn, which ensures that the initialization X^0 is close to X^*, b) weak sharpness property of the least unsquared formulation, which is being solved via ReSync, and c) local linear convergence analysis for ReSync based on initialization and weak sharpness property. \n\nI have, however, not verified the correctness of the theoretical results.", "weaknesses": "Concerns regarding theory:\n1. The paper assumes missing observations as zero matrix, which does not lie on the SO(d) manifold. Hence, only if (i,j) belongs to available observation, Y_{ij} \\in SO(d). The paper does not provide any justification for this choice. A more suitable choice seems to be Identity matrix as it lies on SO(d). \n2. In line 178-180, it is stated that E[Y_ij] = pq X_i^*(X_j^*)^\\top for all (i,j). This does not seem correct as it is not clear how outlier points O_ij \\in SO(d) are handled while computing this expectation. \n3. While the paper cites and discusses its differences with [27] in lines 171-175, it seems that [27] should be discussed in more detail. While  [27] focuses on orthogonal group with additive Gaussian noise and permutation group with outliers, it should be noted that permutation group is a special subset of orthogonal group. Interestingly, [27] states that \"though it is not analyzed in our manuscript, the proof technique for the permutation group synchronization under uniform corruption could be directly modified to tackle this O(d) synchronization under uniform multiplicative corruption\" (in the paragraph before Section 3.2). The proof of leave-one-out technique seems to be adopted from [27]. Hence, while [27] has been cited in Section 3.1 of the paper, it does not seem to be the main contribution and could been discussed in the supplementary material. Overall, [27] deserves more discussion, especially w.r.t. the above quoted statement, and in this regard contribution of the paper should be clearly highlighted. \n4. A discussion on computational cost of the proposed algorithm is missing. \n\nConcerns regarding experiments: \n1. The paper shows only a few empirical results on synthetic datasets. While this gives some insights on how the algorithm works in lab environment, performance on real-world setting gives an idea on how the algorithm will perform when used in real applications. If space was a factor, the paper could have moved some of the proofs/proof-outlines to the supplementary section. \n2. While the paper discusses [40] and states that it \"introduces a least-unsquared formulation and applies the SDR method to tackle it\", the paper should have mentioned more directly that the main formulation (2), which papers tries to solve, was originally proposed in [40]. Hence, while the theoretical results of [40] are in q=1 setting, the paper should have empirically compared with [40] as well. Similarly, paper [30] should also be compared empirically. \n3. Experiments are done in two settings: with and without additive noise. Without additive noise setting has been theoretically analyzed in the paper. One question is that in this setting, DESC method seems to be better or similar to ReSync. Any insights as to why it does better (where it does)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable comments. We address the concerns in a point-by-point manner below. \n\n**A. Missing observations (Q1 in concerns regarding theory).** Since formulation (2) only relies on available observations, we are allowed to assign the missing entries as $\\mathbf{0}$. In theory, this setting ensures that the $d$ leading eigenvectors of $\\mathbb{E}(\\boldsymbol{Y})$ are $\\boldsymbol{X}^\\star$. However, assigning missing observations as identity matrices may not necessarily achieve this outcome when $q$ is small. This particular choice has also been utilized in previous works; see the overview in the fourth paragraph of [24, Section 2.1] (here, [24] refers to reference [24] in our manuscript). In experiments, we use the missing entries only in spectral initialization (Algorithm 2). We have also conducted a simulation to illustrate that assigning the missing observations as identity matrices will decrease the performance; see Fig. 1 in the one-page supplementary PDF of the rebuttal. \n\nWe shall add the following sentence in line 29 in the revised version: *``The missing observations are set to be $\\mathbf{0}$ by convention; see, e.g., [24, Section 2.1].''*\n\n**B. Computation of Expectation (Q2 in concerns regarding theory).** We are sorry for the confusion caused. We have used the fact $\\mathbb{E} (\\boldsymbol{O}_{ij}) = \\mathbf{0}$ since outliers are assumed to be independently and uniformly distributed on $\\operatorname{SO}(d)$ in the RCM. In the revised version, we shall replace \"our random graph setup\" in line 178 with *\"the RCM\"* to enhance clarity.\n\n**C. Connections to [27] and highlight contributions (Q3 in concerns regarding theory).** We have two major differences to [27]: 1) Nontrivial modifications due to the specific structure of $\\operatorname{SO}(d)$. Our approach follows the standard leave-one-out analysis based on the standard \"Dist\" (up to $\\operatorname{O}(d)$ invariance) defined above Lemma 3 in the Appendix. Nonetheless, we have to transfer the results to \"dist\" due to the structure of $\\operatorname{SO}(d)$ in Lemma 5, which is new. 2) Handling incomplete observation ($q<1$). In the case of incomplete observation, the constructed $\\boldsymbol{W}$ in (17) in the Appendix becomes more intricate; it has the additional third column, rendering the analysis of our Lemma 2 more involved. We shall elaborate on these discussions in the revised version. \n\nConcerning our contributions, in addition to the above nontrivial modifications in the initialization analysis, our more important contributions are found in Sections 3.2 and 3.3. These sections focus on geometric and contraction analyses, respectively, which were not present in [27].  \n\n**D. Computational cost (Q4 in concerns regarding theory).** Algorithm 2 has computational cost $\\mathcal{O}(n^3)$.  The per-iteration complexity of the Riemannian subgradient procedure is $\\mathcal{O}(n^2 q)$.  We shall add these discussions in Section 2.1 in the revised version. \n\n**E. Lack of real-world experiment results (Q1 in concerns regarding experiments).** Since the primary focus of this work is theory, we originally only conducted synthetic experiments to corroborate our theoretical findings. Per the request of the reviewer, we now implemented the experiment in [40, Fig. 7] for the real-world \"Lucy dataset\" (here, [40] refers to reference [40] in our manuscript); see Fig. 5 in the one-page supplementary PDF of the rebuttal. It can be observed that our method outperforms DESC and LUD (here, LUD refers to the algorithm in [40] and we use their implementation and default parameters). We shall add this experiment result in our revised version. \n\nMoreover, we are studying applying our algorithm to Cryo-EM imaging experiment settings (based on common-lines), which is our ongoing work. \n\n**F. References [40] and [30] (Q2 in concerns regarding experiments).** We shall add the following sentence at the beginning of line 63 in the revised version: *\"This formulation was introduced in [40] as the initial step for applying the SDR method.\"*\n\nWe have compared our algorithm with LUD in [40] (we use their implementation and default parameters) in the setting of Fig. 2 in our manuscript; see Fig. 3 in the one-page supplementary PDF of the rebuttal. LUD has competitive performance when additive noise is present, which is reasonable since LUD attempts to solve a convex relation of problem (2). We shall add these comparisons in the revised version. We do not compare with [30], as we observed that it has slightly suboptimal performance compared to CEMP and MPLS (which we included in our experiments) in its own simulation results; see [30, Fig. 4]. \n\n**G. Discussion on DESC (Q3 in concerns regarding experiments).**  In the absence of additive noise, the good-cycle condition in DESC is likely fulfilled. This, together with its carefully designed post-procedure for recovering the ground-truth rotations from the estimated corruption level, leads to highly competitive experiment performance. \n\nIn fact, our method performs better if we use larger $n$; see Fig. 4 in the one-page supplementary PDF of the rebuttal, where we use the setting of Fig. 3(a) and 3(c) in our manuscript with the only difference being $n =500$ rather than $n = 200$. \n\nWe hope that our response is satisfactory to the reviewer and that all concerns have been addressed appropriately. Should the reviewer have any further concerns, please inform us during the reviewer-author discussion period so that we can respond timely."}, {"review_id": "kCRrkKVkWr", "reviewer": "Reviewer_W8A3", "summary": "This work proposes to solve the rotation synchronization problem using Riemannian subgradient method with spectral initialization. The proposed formuation is sum of absolute deviations, which is robust to outliers. Exact recovery guarantees are provided under uniform corruption model (the graph is Erdos Renyi and probability of corruption 1-p). Numerical results show competitive performance of the proposed method compared to other state-of-the-art methods.", "questions": "I wonder how sensitive is your method to initialization? For example, given random initialization, what is the typical behavior of your algorithm in numerical experiments and what about the theoretical results?\n\n", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical result in the noiseless case (corruption only) is quite strong. That is, it shows linearly convergence to the ground truth rotations whenever n>1/(p^7q^2) up to a log factor, where p is the probability of being a clean edge (conditioned on being an edge), and q is the probability of being an edge.\n2. The numerical experiments show advantages over previous state-of-the-art methods in the presense of both corruption and noise.\n3. The proofs look correct.\n\nOverall, I enjoyed reading the paper.", "weaknesses": "1. This is not necessarily a weakness, but it would be even nicer if the authors could comment on the stability of your algorithm to noise (would it be possible to show an approximate recovery in this case)?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the supportive and valuable comments. We address the concerns in a point-by-point manner below. \n\n**A. Stability to noise.** Yes. It is possible to show stability and convergence results against additive noise, which is our ongoing work. The initialization analysis should not change much as it fits well with additive noise. Then, a crucial step involves providing a noise-perturbed version of the weak sharpness property, i.e., \n$$\n    f(\\boldsymbol{X}) - f^\\star \\geq \\mathcal{O}(npq) \\operatorname{dist}_1(\\boldsymbol{X},\\boldsymbol{X}^\\star) - \\nu,\n$$\n\nwhere the perturbation $\\nu$ is caused by additive noise. The main difficulty lies in conducting the contraction analysis, as the presence of additive noise brings additional challenges for controlling the infinity norm-induced distance. We believe it is possible to circumvent this technical difficulty by studying more carefully the property of the noise. The final result will be convergence to the neighborhood of the ground-truth rotations up to the scale of the noise. \n\n**B. Sensitivity to initialization.** We test our algorithm with random initialization using the setting of Fig. 2(a) in our manuscript; see Fig. 2 in the one-page supplementary PDF of the rebuttal. It can be observed that our algorithm continues to work. However, it requires a much larger diminishing factor $\\gamma$ of the step size, resulting in notably slower convergence. Theoretically, we do not have an idea yet of how to prove convergence guarantees with random initialization, given that the geometric property (e.g., weak sharpness) only holds locally.\n\nWe hope that our response is satisfactory to the reviewer and that all concerns have been addressed appropriately. Should the reviewer have any further concerns, please inform us during the reviewer-author discussion period so that we can respond timely."}, {"review_id": "iYoL8A1o5y", "reviewer": "Reviewer_grLa", "summary": "This paper presents a theoretical study for robust rotation synchronization with a least-unsquared minimization formulation over the rotation group.\n\nIn particular, this paper proposes a two-step algorithm called ReSync, where the first step uses spectral initialization to generate an initial guess and the second step performs Riemannian Subgradient descent from the initial guess.\n\nThe paper proves that, under suitable conditions of the random corruption model, this algorithm converges linearly to the groundtruth rotations.\n\nThe paper presents numerical experiments that verify the correctness of the theorem and compares the performance of ReSync with other state-of-the-art algorithms.", "questions": "See Weaknesses.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical contribution of this paper advances the previous state of the art.\n- Paper is well written and easy to follow, despite being a theory paper.", "weaknesses": "- I am curious if similar guarantees could be made in the case where the inlier measurements are corrupted by small (and bounded) noise? Could you guarantee the algorithm converges to a solution that has bounded error from the groundtruth rotations?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the supportive and valuable comments. We address the concern below. \n\n**A. Guarantees with additive noise.** Yes. It is possible to show the convergence results against additive noise, in which the algorithm will converge to the neighborhood of the ground-truth rotations up to the scale of the noise. The initialization analysis should not change much as it fits well with additive noise. Then, a crucial step involves providing a noise-perturbed version of the weak sharpness property, i.e., \n$$    \nf(\\boldsymbol{X}) - f^\\star \\geq \\mathcal{O}(npq) \\operatorname{dist}_1(\\boldsymbol{X},\\boldsymbol{X}^\\star) - \\nu,\n$$\n\nwhere the perturbation $\\nu$ is caused by additive noise. The main difficulty lies in conducting the contraction analysis, as the presence of additive noise brings additional challenges for controlling the infinity norm-induced distance. We believe it is possible to circumvent this technical difficulty by studying more carefully the property of the noise. This line of research is our ongoing work. \n\nWe hope that our response is satisfactory to the reviewer and that the concern has been addressed appropriately. Should the reviewer have any further concerns, please inform us during the reviewer-author discussion period so that we can respond timely."}, {"review_id": "4TNu4PZQwX", "reviewer": "Reviewer_aU9r", "summary": "The paper concerns synchronization of observed rotations with incomplete and corrupted observations. The authors construct the method ReSync that is a gradient-based algorithm for solving the problem. The paper describes the context, prior results on the synchronization problem, and the algorithm, and presents a thorough convergence analysis together with experimental evaluation.", "questions": "no questions", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- well-written and clearly presented paper\n- the presented method deals with an important problem\n- the presentation of the algorithm is followed by a thorough convergence analysis\n- the method performs well in the experimental validation", "weaknesses": "- constructing a gradient descent algorithm is not a big contribution in itself. However, I believe the geometric setting and the connection to the theoretical analysis, which is not trivial, makes the contribution important", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the supportive and valuable comments. Should the reviewer have any further concerns, please inform us during the reviewer-author discussion period so that we can respond timely. "}]

Author rebuttal:
Dear ACs and Reviewers,

This global response contains our one-page supplementary PDF of the rebuttal. All additional figures are included in this file. Please find it in the attachment. 

Best regards, 

Authors. 

Meta-review: The paper deals with the robust rotation synchronization problem. It presents an initialization strategy and algorithm with a theoretical analysis. Overall, the reviewers and the AC think that the paper merits acceptance. Please consider the reviews and make the necessary modifications.
Decision: Accept (poster)