Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization
This addresses a practical problem in distributed synchronization for computer vision pipelines, where existing methods are inefficient for cycles longer than three, though it is incremental in improving computational efficiency.
The paper tackles the computational bottleneck of detecting long consistent cycles in group synchronization for Structure from Motion, proposing an algorithm that handles cycles up to length six with time complexity O(n^3) and achieves competitive sample complexity under a uniform corruption model.
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(n^3)$ (or $O(n^{2.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.