pith. machine review for the scientific record. sign in

arxiv: 2604.13915 · v1 · submitted 2026-04-15 · 🧮 math.OC · eess.SP

Recognition: unknown

Anchored Spectral Estimator for Rigid Motion Synchronization

Ziyue Zhao , Huikang Liu , Man-Chung Yue
Authors on Pith no claims yet

Pith reviewed 2026-05-10 12:18 UTC · model grok-4.3

classification 🧮 math.OC eess.SP
keywords rigid motion synchronizationanchored spectral estimatoruniform estimation error boundstwo-stage approachpoint-set registrationspectral methodsrigid motionsestimation theory
0
0 comments X

The pith

The anchored spectral estimator recovers rigid motions from noisy comparisons with uniform error bounds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the anchored spectral estimator as a new spectral method for rigid motion synchronization. It aims to recover a collection of rigid motions in d dimensions from noisy observations of their pairwise comparisons. The work proves uniform estimation error bounds that apply across the entire collection and shows through experiments that the method outperforms the common two-stage approach of estimating rotations first and translations second. A sympathetic reader cares because rigid motion synchronization underpins many tasks in robotics, computer vision, and signal processing where accurate recovery from noisy data is essential. Further tests on multiple point-set registration confirm the practical advantages.

Core claim

Motivated by geometric considerations, the anchored spectral estimator recovers the collection of rigid motions G_1^* to G_n^* from noisy observations of their comparisons G_i^{*-1} G_j^*. The estimator produces uniform error bounds on the recovered motions that hold simultaneously for all elements in the collection.

What carries the argument

The anchored spectral estimator, a spectral construction that anchors the solution to jointly handle the rotational and translational components of each rigid motion matrix instead of decoupling them.

If this is right

  • Uniform estimation error bounds apply simultaneously to all recovered rigid motions in the collection.
  • ASE produces lower errors in practice than the two-stage method that estimates rotations and translations separately.
  • On multiple point-set registration tasks, ASE outperforms existing state-of-the-art methods.
  • The approach applies directly to rigid motion problems arising in signal processing, robotics, and computer vision.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Better initial estimates from ASE could improve convergence speed and accuracy in iterative refinement algorithms used in structure-from-motion pipelines.
  • The anchoring idea might generalize to synchronization over other matrix Lie groups where rotational and translational parts are coupled.
  • The uniform bounds could be used to derive sample-size requirements for reliable synchronization in large networks of sensors or cameras.
  • Real-world tests with structured noise patterns, such as outliers from matching failures, would clarify the practical range of the geometric motivation.

Load-bearing premise

The geometric considerations that motivate the anchored spectral construction hold for the noise model and the distribution of the true rigid motions.

What would settle it

Controlled experiments with increasing numbers of motions and the assumed noise model where the maximum estimation error over the collection exceeds the derived uniform bound would falsify the theoretical claim.

read the original abstract

A rigid motion in $\mathbb{R}^d$ consists of a proper rotation and a translation, and it can be represented as a matrix in $\mathbb{R}^{(d+1)\times (d+1)}$. The problem of rigid motion synchronization aims to estimate a collection of rigid motions $G^*_1, \dots, G^*_n$ from noisy observations of their comparisons ${G^*_i}^{-1} G^*_j$. Such problems naturally arise in diverse applications across signal processing, robotics, and computer vision, and have thus attracted intense research attention in recent years. Motivated by geometric considerations, this paper develops a novel spectral approach for rigid motion synchronization, called the anchored spectral estimator (ASE). Theoretically, we establish uniform estimation error bounds for the estimators produced by ASE. Empirically, we show that ASE outperforms the widely used two-stage approach, which first estimates the rotations and then the translations. Further numerical experiments on the multiple point-set registration problem are presented to demonstrate the superiority of ASE over state-of-the-art methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper introduces the Anchored Spectral Estimator (ASE) for rigid motion synchronization, which recovers a collection of rigid motions G_1^* to G_n^* in SE(d) from noisy pairwise comparisons G_i^{*-1} G_j^*. Motivated by geometric considerations on the manifold, ASE uses an anchoring step to resolve global ambiguity and applies a spectral method. The central claims are that ASE admits uniform estimation error bounds and that it empirically outperforms the standard two-stage approach (separate rotation then translation estimation) as well as other state-of-the-art methods on multiple point-set registration tasks.

Significance. If the uniform bounds can be established under a clearly stated noise model, the anchoring construction would supply a geometrically motivated spectral estimator with non-asymptotic guarantees for a core problem in robotics and computer vision. The empirical comparisons, if controlled, would indicate practical gains over two-stage pipelines. The work's value hinges on whether the geometric assumptions translate into configuration-independent constants rather than bounds that degrade with clustered motions or anisotropic noise.

major comments (3)
  1. [Theoretical analysis] The uniform estimation error bounds are asserted to hold over all configurations of {G_i^*} and admissible noise realizations, yet the precise noise model (additive on the Lie algebra, multiplicative on the group, or otherwise) and the distribution of the true motions are not specified. Without these, it is impossible to verify that the anchored matrix possesses a spectral gap whose size is independent of the configuration and that the subsequent eigenvector perturbation analysis yields constants that do not blow up.
  2. [Theoretical analysis] Uniformity requires the bound to remain valid even when the true motions are clustered or the noise is non-isotropic; the manuscript provides no robustness checks or worst-case analysis demonstrating that the anchoring step does not introduce configuration-dependent bias that violates the claimed uniformity.
  3. [Numerical experiments] The empirical section reports superiority over the two-stage baseline, but without explicit description of the noise generation process, the range of rotation/translation magnitudes tested, or the precise implementation of the competing methods, it is difficult to determine whether the observed gains are attributable to ASE or to differences in experimental controls.
minor comments (2)
  1. [Abstract] The abstract states that uniform bounds are established but supplies neither a theorem number nor a proof sketch; adding a brief reference to the main result would improve readability.
  2. [Method] Notation for the anchored matrix and the precise definition of the spectral estimator should be introduced earlier and used consistently throughout the theoretical development.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. The comments highlight important points regarding the clarity of our theoretical assumptions and experimental details. We address each major comment below and will revise the manuscript to incorporate clarifications and additional information where appropriate.

read point-by-point responses

  1. Referee: [Theoretical analysis] The uniform estimation error bounds are asserted to hold over all configurations of {G_i^*} and admissible noise realizations, yet the precise noise model (additive on the Lie algebra, multiplicative on the group, or otherwise) and the distribution of the true motions are not specified. Without these, it is impossible to verify that the anchored matrix possesses a spectral gap whose size is independent of the configuration and that the subsequent eigenvector perturbation analysis yields constants that do not blow up.

    Authors: We appreciate this observation on the need for explicit specification. The noise model is multiplicative on the group: each observed comparison satisfies G_{ij} = G_i^{*-1} G_j^* Exp(ξ_{ij}), where ξ_{ij} ∈ se(d) are bounded perturbations (‖ξ_{ij}‖ ≤ ε) drawn from a distribution with support independent of the configuration. The true motions {G_i^*} are arbitrary (no distributional assumption), and uniformity holds over all configurations for which the comparison graph is connected with minimum degree at least 1. The anchoring step fixes the global frame at the first node, and the spectral gap of the anchored matrix is bounded below by a positive constant depending only on the minimum degree and the noise bound ε, not on clustering or specific geometry. The subsequent Davis-Kahan perturbation analysis then yields error bounds whose constants depend only on these quantities. We will add a dedicated paragraph in Section 2 explicitly stating the noise model, the connectivity assumption, and a remark confirming that the constants are configuration-independent under these conditions. revision: yes

  2. Referee: [Theoretical analysis] Uniformity requires the bound to remain valid even when the true motions are clustered or the noise is non-isotropic; the manuscript provides no robustness checks or worst-case analysis demonstrating that the anchoring step does not introduce configuration-dependent bias that violates the claimed uniformity.

    Authors: The anchoring construction is a fixed reference (node 1) chosen without reference to the data geometry, so it introduces no configuration-dependent bias; the analysis shows that the eigenvector perturbation remains controlled by the noise level ε uniformly, provided the graph remains connected. For clustered motions the spectral gap is preserved because the anchored matrix still encodes the relative geometry. However, the current proof assumes bounded isotropic noise in the Lie algebra. We agree that explicit checks for clustered configurations and anisotropic noise would strengthen the claims. We will add a new subsection with synthetic experiments under clustered point clouds and diagonal (anisotropic) noise covariances, together with a remark noting that the theoretical uniformity extends to the anisotropic case when the noise bound is taken as the maximum eigenvalue of the covariance. revision: partial

  3. Referee: [Numerical experiments] The empirical section reports superiority over the two-stage baseline, but without explicit description of the noise generation process, the range of rotation/translation magnitudes tested, or the precise implementation of the competing methods, it is difficult to determine whether the observed gains are attributable to ASE or to differences in experimental controls.

    Authors: We agree that the experimental protocol requires more detail for reproducibility. Noise is generated by sampling ξ_{ij} ∼ N(0, σ² I) in the Lie algebra with σ ranging from 0.01 to 0.2; rotation angles are drawn uniformly up to 30° and translations up to 5 units in each coordinate. The two-stage baseline and other competing methods are implemented exactly as described in their respective papers, using the same noisy comparisons and graph. We will expand the experimental setup paragraph (currently Section 4.1) with these ranges, the precise noise-generation procedure (including pseudocode), and a statement that all methods receive identical input data. revision: yes

Circularity Check

0 steps flagged

No circularity: ASE defined directly from data and anchor; bounds derived from perturbation analysis

full rationale

The paper constructs the anchored spectral estimator directly from the noisy pairwise comparisons and a chosen anchor to resolve global ambiguity. Uniform error bounds follow from eigenvector perturbation analysis on the anchored matrix under the stated geometric noise model on SE(d). No equation reduces a prediction to a fitted parameter by construction, no self-citation supplies the central uniqueness or bound, and the two-stage comparison is purely empirical. The derivation chain is self-contained once the modeling assumptions are granted.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is necessarily incomplete. The approach rests on a geometric motivation for anchoring and a standard noisy comparison model, but no explicit free parameters, axioms, or invented entities are stated.

axioms (1)
  • domain assumption Noisy observations of pairwise rigid-motion comparisons are available
    The problem formulation assumes such comparisons exist and are corrupted by noise.

pith-pipeline@v0.9.0 · 5481 in / 1150 out tokens · 24471 ms · 2026-05-10T12:18:50.681428+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Anchored Spectral Estimator for Rigid Motion Synchronization

    INTRODUCTION A rigid motion inR d consists of a proper rotation and a translation and can be represented as a(d+ 1)×(d+ 1)matrix. The problem of rigid motion synchronization is to recover a collection of rigid motionsG ∗ 1, . . . , G∗ n ∈SE(d)from the noisy observations of their pairwise comparisonsG ∗−1 i G∗ j . Since the set of rigid motions forms the s...

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    To begin, recall that a rigid motion inR d consists of a proper rotationR∈SO(d)and a translationt∈R d, and can be represented as a(d+ 1)×(d+ 1)matrix of the form R⊤ t 0 1

    A NEW SPECTRAL METHOD FORSE-Sync 2.1.SE-Sync and Its Least Squares Estimator This section formally introduces the special Euclidean group syn- chronization problem (SE-Sync) and our proposed spectral method ASE. To begin, recall that a rigid motion inR d consists of a proper rotationR∈SO(d)and a translationt∈R d, and can be represented as a(d+ 1)×(d+ 1)ma...

  3. [3]

    Specifically, we show that the (unsquared)ℓ 2 estima- tion error of the estimators ˆG1,

    ESTIMA TION ERROR BOUND The proposed ASE enjoys a strong theoretical guarantee on its esti- mation error. Specifically, we show that the (unsquared)ℓ 2 estima- tion error of the estimators ˆG1, . . . , ˆGn enjoys a uniform bound of the orderO((σ 1 +σ 2 2)( √ d+ √logn)d/ √n). To state the result, we letM t = maxi∈[n] ∥t∗ i ∥2. Theorem3.1.Consider Algorithm...

  4. [4]

    Our codes are available athttps: //github.com/ziyuezhao1/GSP-SE_D

    NUMERICAL EXPERIMENTS In this section, we conduct numerical experiments to investigate the practical performance of ASE. Our codes are available athttps: //github.com/ziyuezhao1/GSP-SE_D. 4.1. Comparison with the Two-Stage Approach We first empirically study how the estimation error of ASE varies against the noise magnitudesσ 1 andσ 2, especially in compa...

  5. [5]

    1.08 14.28 1.32 Translation ASE2.59 3.82 1.58

  6. [6]

    From Table 1, see that our proposed ASE achieves the smallest estimation error with respect to both rotation and translation

    98.8 4.72 2.38 Table 1: Average rotation error (in degrees) and average translation error (in millimeters) of different spectral approaches for multiple point-set registration. From Table 1, see that our proposed ASE achieves the smallest estimation error with respect to both rotation and translation. The 3D models constructed using our proposed ASE are s...

  7. [7]

    ASE enjoys a strong theoretical guarantee on its estimation error

    CONCLUSIONS Motivated by the symmetry issue of existing spectral estimators, this paper develops a new spectral estimator, called the anchored spec- tral estimator (ASE), for rigid motion synchronization. ASE enjoys a strong theoretical guarantee on its estimation error. Numerically, we show that ASE outperforms a two-stage approach using synthetic data a...

  8. [8]

    ACKNOWLEDGMENT Man-Chung Yue is supported in part by Hong Kong Research Grants Council under the GRF project 17309423

  9. [9]

    Cartan-Sync: Fast and global SE(d)-synchronization,

    Jesus Briales and Javier Gonzalez-Jimenez, “Cartan-Sync: Fast and global SE(d)-synchronization,”IEEE Robotics and Automation Letters, vol. 2, no. 4, pp. 2127–2134, 2017

    2017

  10. [10]

    Non- convex pose graph optimization in slam via proximal linearized riemannian admm,

    Xin Chen, Chunfeng Cui, Deren Han, and Liqun Qi, “Non- convex pose graph optimization in slam via proximal linearized riemannian admm,”Journal of Optimization Theory and Ap- plications, vol. 206, no. 3, pp. 1–43, 2025

    2025

  11. [11]

    Rotation averaging with the chordal distance: Global min- imizers and strong duality,

    Anders Eriksson, Carl Olsson, Fredrik Kahl, and Tat-Jun Chin, “Rotation averaging with the chordal distance: Global min- imizers and strong duality,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 43, no. 1, pp. 256–268, 2019

    2019

  12. [12]

    A survey of structure from motion*.,

    Onur Özye¸ sil, Vladislav V oroninski, Ronen Basri, and Amit Singer, “A survey of structure from motion*.,”Acta Numerica, vol. 26, pp. 305–364, 2017

    2017

  13. [13]

    Learning iterative robust trans- formation synchronization,

    Zi Jian Yew and Gim Hee Lee, “Learning iterative robust trans- formation synchronization,” in2021 International Conference on 3D Vision (3DV). IEEE, 2021, pp. 1206–1215

    2021

  14. [14]

    Theory of semidefinite programming for sensor network localization,

    Anthony Man-Cho So and Yinyu Ye, “Theory of semidefinite programming for sensor network localization,”Mathematical Programming, vol. 109, no. 2, pp. 367–384, 2007

    2007

  15. [15]

    Three-dimensional struc- ture determination from common lines in cryo-EM by eigen- vectors and semidefinite programming,

    Amit Singer and Yoel Shkolnisky, “Three-dimensional struc- ture determination from common lines in cryo-EM by eigen- vectors and semidefinite programming,”SIAM Journal on Imaging Sciences, vol. 4, no. 2, pp. 543–572, 2011

    2011

  16. [16]

    On the estimation performance and convergence rate of the generalized power method for phase synchronization,

    Huikang Liu, Man-Chung Yue, and Anthony Man-Cho So, “On the estimation performance and convergence rate of the generalized power method for phase synchronization,”SIAM Journal on Optimization, vol. 27, no. 4, pp. 2426–2446, 2017

    2017

  17. [17]

    Tight- ness of the maximum likelihood semidefinite relaxation for an- gular synchronization,

    Afonso S Bandeira, Nicolas Boumal, and Amit Singer, “Tight- ness of the maximum likelihood semidefinite relaxation for an- gular synchronization,”Mathematical Programming, vol. 163, pp. 145–167, 2017

    2017

  18. [18]

    Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions,

    Luca Carlone, David M Rosen, Giuseppe Calafiore, John J Leonard, and Frank Dellaert, “Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions,” in2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2015, pp. 125–132

    2015

  19. [19]

    SE-Sync: A certifiably correct algorithm for syn- chronization over the special Euclidean group,

    David M Rosen, Luca Carlone, Afonso S Bandeira, and John J Leonard, “SE-Sync: A certifiably correct algorithm for syn- chronization over the special Euclidean group,”The Interna- tional Journal of Robotics Research, vol. 38, no. 2-3, pp. 95– 125, 2019

    2019

  20. [20]

    Solving orthogonal group synchronization via convex and low-rank optimization: Tightness and landscape analysis,

    Shuyang Ling, “Solving orthogonal group synchronization via convex and low-rank optimization: Tightness and landscape analysis,”Mathematical Programming, vol. 200, no. 1, pp. 589–628, 2023

    2023

  21. [21]

    Nonconvex phase synchronization,

    Nicolas Boumal, “Nonconvex phase synchronization,”SIAM Journal on Optimization, vol. 26, no. 4, pp. 2355–2377, 2016

    2016

  22. [22]

    Improved performance guarantees for orthog- onal group synchronization via generalized power method,

    Shuyang Ling, “Improved performance guarantees for orthog- onal group synchronization via generalized power method,” SIAM Journal on Optimization, vol. 32, no. 2, pp. 1018–1048, 2022

    2022

  23. [23]

    Iterative algorithm for discrete structure recovery,

    Chao Gao and Anderson Y Zhang, “Iterative algorithm for discrete structure recovery,”The Annals of Statistics, vol. 50, no. 2, pp. 1066–1094, 2022

    2022

  24. [24]

    A unified approach to synchronization problems over subgroups of the orthogonal group,

    Huikang Liu, Man-Chung Yue, and Anthony Man-Cho So, “A unified approach to synchronization problems over subgroups of the orthogonal group,”Applied and Computational Har- monic Analysis, 2023

    2023

  25. [25]

    Optimal orthogonal group synchronization and rotation group synchronization,

    Chao Gao and Anderson Y Zhang, “Optimal orthogonal group synchronization and rotation group synchronization,”Infor- mation and Inference: A Journal of the IMA, vol. 12, no. 2, pp. 591–632, 2023

    2023

  26. [26]

    Angular synchronization by eigenvectors and semidefinite programming,

    Amit Singer, “Angular synchronization by eigenvectors and semidefinite programming,”Applied and Computational Har- monic Analysis, vol. 30, no. 1, pp. 20–36, 2011

    2011

  27. [27]

    Sen- sor network localization by eigenvector synchronization over the Euclidean group,

    Mihai Cucuringu, Yaron Lipman, and Amit Singer, “Sen- sor network localization by eigenvector synchronization over the Euclidean group,”ACM Transactions on Sensor Networks (TOSN), vol. 8, no. 3, pp. 1–42, 2012

    2012

  28. [28]

    Synchronization problems in computer vision with closed-form solutions,

    Federica Arrigoni and Andrea Fusiello, “Synchronization problems in computer vision with closed-form solutions,”In- ternational Journal of Computer Vision, vol. 128, no. 1, pp. 26–52, 2020

    2020

  29. [29]

    Spec- tral synchronization of multiple views in SE(3),

    Federica Arrigoni, Beatrice Rossi, and Andrea Fusiello, “Spec- tral synchronization of multiple views in SE(3),”SIAM Journal on Imaging Sciences, vol. 9, no. 4, pp. 1963–1990, 2016

    1963

  30. [30]

    SE(3) synchro- nization by eigenvectors of dual quaternion matrices,

    Ido Hadi, Tamir Bendory, and Nir Sharon, “SE(3) synchro- nization by eigenvectors of dual quaternion matrices,”Infor- mation and Inference: A Journal of the IMA, vol. 13, no. 3, pp. iaae014, 2024

    2024

  31. [31]

    Per- formance guarantees for spectral initialization in rotation aver- aging and pose-graph slam,

    Kevin J Doherty, David M Rosen, and John J Leonard, “Per- formance guarantees for spectral initialization in rotation aver- aging and pose-graph slam,” in2022 International Conference on Robotics and Automation (ICRA). IEEE, 2022, pp. 5608– 5614

    2022

  32. [32]

    Exact minimax optimality of spectral methods in phase synchronization and orthogonal group syn- chronization,

    Anderson Ye Zhang, “Exact minimax optimality of spectral methods in phase synchronization and orthogonal group syn- chronization,”The Annals of Statistics, vol. 52, no. 5, pp. 2112–2138, 2024

    2024

  33. [33]

    Rotation averaging,

    Richard Hartley, Jochen Trumpf, Yuchao Dai, and Hongdong Li, “Rotation averaging,”International Journal of Computer Vision, vol. 103, no. 3, pp. 267–305, 2013

    2013

  34. [34]

    Combining two-view constraints for motion estimation,

    Venu Madhav Govindu, “Combining two-view constraints for motion estimation,” inProceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. (CVPR). IEEE, 2001, vol. 2, pp. II–II

    2001

  35. [35]

    Near-optimal performance bounds for orthog- onal and permutation group synchronization via spectral meth- ods,

    Shuyang Ling, “Near-optimal performance bounds for orthog- onal and permutation group synchronization via spectral meth- ods,”Applied and Computational Harmonic Analysis, vol. 60, pp. 20–52, 2022

    2022

  36. [36]

    ReSync: Riemannian subgradient-based robust rotation synchroniza- tion,

    Huikang Liu, Xiao Li, and Anthony Man-Cho So, “ReSync: Riemannian subgradient-based robust rotation synchroniza- tion,” inProceedings of the 37th International Conference on Neural Information Processing Systems, 2023, pp. 5236–5261

    2023

  37. [37]

    The Stanford 3D Scanning Repository,

    Stanford University Computer Graphics Laboratory, “The Stanford 3D Scanning Repository,”http://graphics. stanford.edu/data/3Dscanrep/, 1996, Accessed: September 17, 2025

    1996

  38. [38]

    Method for registration of 3-D shapes,

    Paul J Besl and Neil D McKay, “Method for registration of 3-D shapes,” inSensor fusion IV: Control Paradigms and Data Structures. SPIE, 1992, vol. 1611, pp. 586–606

    1992

  39. [39]

    47, Cambridge university press, 2018

    Roman Vershynin,High-dimensional probability: An intro- duction with applications in data science, vol. 47, Cambridge university press, 2018

    2018

  40. [40]

    Introduction to the non-asymptotic analysis of random matrices

    Roman Vershynin, “Introduction to the non-asymptotic anal- ysis of random matrices,”arXiv preprint arXiv:1011.3027, 2010

    work page Pith review arXiv 2010

  41. [41]

    Perturbation theory for the singular value decomposition,

    Gilbert W Stewart, “Perturbation theory for the singular value decomposition,” 1998

    1998

  42. [42]

    For any matrixH∈R na×b, we denote byH i ∈R a×b itsi-th block row

    APPENDIX This appendix provides the proofs of Lemmas 3.1, 3.2, and 3.3. For any matrixH∈R na×b, we denote byH i ∈R a×b itsi-th block row. In particular, forH∈R n×b,H i ∈R 1×b denotes itsi- th row. For eigenvectorsΦ, we assumeΦ ⊤Φ =nI d. Using the projectionΠ SO(d), we can map anynd×dmatrix to the feasi- ble regionSO(d) n of the problemSE-Sync using the bl...

  43. [43]

    (d+√dlogn)√n with probability at least1−O(n −2). Substituting this into (8.32) yields (M2 t + 1) √ d n ∥((wt)⊤)i∥2∥Φ−Φ (i)S(i)∥F ⩽c 10(M2 t + 1)2(c1σ1 +c 2σ2Mt +c 3σ2 2)(d √ d+d √logn)√n , (8.35) where we used the fact that∥((w t)⊤)i∥2 ⩽cσ 2 √ nd⩽ n 4 (due to Lemma 8.3 and the assumption thatσ 2 ⩽c ′ √n√ d for some constant c). Recall the definition ofΦ(i...