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.
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.
I have, however, not verified the correctness of the theoretical results.
Weaknesses
Concerns regarding theory:
1. 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).
2. 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.
3. 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.
4. A discussion on computational cost of the proposed algorithm is missing.
Concerns regarding experiments:
1. 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.
2. 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.
3. 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)?
Questions
Please look in the weakness section.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
not applicable