Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LongSync, a vectorized modification of CEMP that uses cycles of length 3–6 for group (rotation) synchronization with O(n^3) cost, with sample-complexity theory under the uniform corruption model and improved distributed SfM synchronization.
Problem
Long consistent cycles are computationally intractable to use for inferring edge corruption in group synchronization, and 3-cycles are unavailable in sparse, bipartite, or lattice viewing graphs (e.g., distributed SfM).
Approach
Replace the averaging of cycle inconsistency measures in CEMP with a weighted quadratic average of squared chordal distances, which is linear in the cycle products and lets the sum over all cycles be computed via matrix powers and Hadamard operations, reducing complexity from O(n^c) to O(n^3) for c≤6.
Key results
- On UBCM with bipartite graphs, LongSync with 4-cycles almost exactly recovers rotations while other methods remain far from ground truth.
- Distributed LongSync outperforms other distributed methods on 13 of 15 PhotoTourism datasets, taking less than 6% of full MPLS runtime on the largest dataset.
- Theory gives sample complexity O(p^{-(c-1)/(c-2-ε)} q_g^{-7(c-1)/(3(c-2))}), improving prior CEMP bounds and approaching the information-theoretic bound as c grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LongSync with 4-cycles to initialize IRLS instead of a random spanning tree | IRLS rotation synchronization · Uniform corruption model | mean rotation estimation error | Helped |
| Increase LongSync cycle length from 4 to 5 (ablation) | LongSync + IRLS · Uniform corruption model | mean rotation estimation error | Helped |
| Use 4-cycle LongSync weights for edge averaging and initialization | Distributed synchronization · Uniform bipartite corruption model | mean rotation estimation error | Helped |
| Use LongSync with graph processing rather than the best of IRLS(New) and MultiSync(New) | Distributed synchronization · PhotoTourism (Notre Dame) | mean rotation error: 28.6% | Helped |
| Use LongSync with graph processing rather than the best of IRLS(New) and MultiSync(New) | Distributed synchronization · PhotoTourism (Notre Dame) | median rotation error: 46.4% | Helped |
| Add the new graph processing method (ablation) | LongSync · PhotoTourism (14 of 15 datasets) | mean rotation error: 59.2% | Helped |
| Add the new graph processing method (ablation) | LongSync · PhotoTourism (14 of 15 datasets) | median rotation error: 28.5% | Helped |
| Replace CEMP with LongSync using 3-cycles for intra-cluster edge filtering (ablation) | PhotoTourism graph processing · PhotoTourism | rotation estimation performance | No clear effect |
| Use LongSync with graph processing rather than other distributed methods | Distributed synchronization · PhotoTourism | median rotation error | Mixed |
Surprising findings
- LongSync with 3-cycles alone already attains a sample complexity better than prior CEMP theory under the uniform corruption model.
Limitations
- A gap remains between the sample complexity and the information-theoretic bound.
- The graph preprocessing method is heuristic and its parameters are chosen manually.
- Evaluation is limited to rotation synchronization for distributed SfM; other groups are only discussed theoretically.
Experimental setup
Datasets: PhotoTourism
Benchmarks: PhotoTourism synthetic UCM synthetic UBCM
Metrics: mean error (degrees) median error (degrees) runtime ratio
Baselines: CEMP+IRLS IRLS MultiSync MultiSync (New) IRLS (New) MPLS ReSync
Builds on: CEMP MPLS IRLS MultiSync
Closest papers by meaning
- Robust Group Synchronization via Quadratic Programming (ICML 2022 · similarity 0.92)
- Message Passing Least Squares Framework and its Application to Rotation Synchronization (ICML 2020 · similarity 0.88)
- Robust Angular Synchronization via Directed Graph Neural Networks (ICLR 2024 · similarity 0.85)
- Tensor-Based Synchronization and the Low-Rankness of the Block Trifocal Tensor (NeurIPS 2024 · similarity 0.83)
- Efficiently Vectorized MCMC on Modern Accelerators (ICML 2025 · similarity 0.81)
- Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization (NeurIPS 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.