# The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2016.

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

- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Fast, Accurate and Memory-Efficient Partial Permutation Synchronization](https://mlsanity.com/paper/2203.16505/) (2022)
- [Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching](https://mlsanity.com/paper/2201.04797/) (2022)
- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method](https://mlsanity.com/paper/2112.06556/) (2021)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimaging](https://mlsanity.com/paper/2406.18215/) (2024)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Learning Tensor Representations for Meta-Learning](https://mlsanity.com/paper/2201.07348/) (2022)
- [A Novel and Optimal Spectral Method for Permutation Synchronization](https://mlsanity.com/paper/2303.12051/) (2023)
- [Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering](https://mlsanity.com/paper/2310.13311/) (2023)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)
- [Dynamic Topic Modeling with a Higher-Order Hypergraphical Representation](https://mlsanity.com/paper/2605.28269/) (2026)

## Abstract (arXiv)

Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete---and hence nonconvex---structure of the problem, computing the optimal assignment (e.g.~maximum likelihood assignment) becomes intractable at first sight. This paper makes progress towards efficient computation by focusing on a concrete joint alignment problem---that is, the problem of recovering n discrete variables xi ∈ 1,cdots, m, 1≤ i≤ n given noisy observations of their modulo differences xi - xj~mathsfmod~m. We propose a low-complexity and model-free procedure, which operates in a lifted space by representing distinct label values in orthogonal directions, and which attempts to optimize quadratic functions over hypercubes. Starting with a first guess computed via a spectral method, the algorithm successively refines the iterates via projected power iterations. We prove that for a broad class of statistical models, the proposed projected power method makes no error---and hence converges to the maximum likelihood estimate---in a suitable regime. Numerical experiments have been carried out on both synthetic and real data to demonstrate the practicality of our algorithm. We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.