# Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization

arXiv: https://arxiv.org/abs/2407.04260 · HTML: https://mlsanity.com/paper/2407.04260/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 50 references that are in the map.
- First posted on arXiv 5 Jul 2024.

## Builds on (most cited first, 18 of 18)

- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [Robust Camera Location Estimation by Convex Programming](https://mlsanity.com/paper/1412.0165/) (2014)
- [Learning Transformation Synchronization](https://mlsanity.com/paper/1901.09458/) (2019)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [Message Passing Least Squares Framework and its Application to Rotation Synchronization](https://mlsanity.com/paper/2007.13638/) (2020)
- [Robust Group Synchronization via Cycle-Edge Message Passing](https://mlsanity.com/paper/1912.11347/) (2019)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [ShapeFit and ShapeKick for Robust, Scalable Structure from Motion](https://mlsanity.com/paper/1608.02165/) (2016)
- [Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging](https://mlsanity.com/paper/2103.08292/) (2021)
- [Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian](https://mlsanity.com/paper/2006.06658/) (2020)
- [RAGO: Recurrent Graph Optimizer For Multiple Rotation Averaging](https://mlsanity.com/paper/2212.07211/) (2022)
- [Robust Rotation Synchronization via Low-rank and Sparse Matrix Decomposition](https://mlsanity.com/paper/1505.06079/) (2015)
- [Fast, Accurate and Memory-Efficient Partial Permutation Synchronization](https://mlsanity.com/paper/2203.16505/) (2022)
- [Distributed methods for synchronization of orthogonal matrices over graphs](https://mlsanity.com/paper/1701.07248/) (2017)
- [Estimation of Camera Locations in Highly Corrupted Scenarios: All About that Base, No Shape Trouble](https://mlsanity.com/paper/1804.02591/) (2018)
- [Synchronization over Z2 and community detection in multiplex signed networks with constraints](https://mlsanity.com/paper/1504.04061/) (2015)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Incremental Rotation Averaging Revisited](https://mlsanity.com/paper/2309.16924/) (2023)

## Built on by (most cited first, 4 of 4)

- [Tensor-Based Synchronization and the Low-Rankness of the Block Trifocal Tensor](https://mlsanity.com/paper/2409.09313/) (2024)
- [A Taxonomy of Structure from Motion Methods](https://mlsanity.com/paper/2505.15814/) (2025)
- [Higher-Order Group Synchronization](https://mlsanity.com/paper/2505.21932/) (2025)
- [QuadSync: Quadrifocal Tensor Synchronization via Tucker Decomposition](https://mlsanity.com/paper/2602.22639/) (2026)

## Abstract (arXiv)

Group synchronization plays a crucial role in global pipelines for Structure from Motion (SfM). Its formulation is nonconvex and it is faced with highly corrupted measurements. Cycle consistency has been effective in addressing these challenges. However, computationally efficient solutions are needed for cycles longer than three, especially in practical scenarios where 3-cycles are unavailable. To overcome this computational bottleneck, we propose an algorithm for group synchronization that leverages information from cycles of lengths ranging from three to six with a time complexity of order O(n3) (or O(n2.373) when using a faster matrix multiplication algorithm). We establish non-trivial theory for this and related methods that achieves competitive sample complexity, assuming the uniform corruption model. To advocate the practical need for our method, we consider distributed group synchronization, which requires at least 4-cycles, and we illustrate state-of-the-art performance by our method in this context.