# Ranking and synchronization from pairwise measurements via SVD

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2019.

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

- [Lead-lag detection and network clustering for multivariate time series with an application to the US equity market](https://mlsanity.com/paper/2201.08283/) (2022)
- [Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method](https://mlsanity.com/paper/2109.13743/) (2021)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Learning the Structure of Connection Graphs](https://mlsanity.com/paper/2510.11245/) (2025)
- [Ranking with Confidence for Large Scale Comparison Data](https://mlsanity.com/paper/2202.01670/) (2022)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models](https://mlsanity.com/paper/2305.06704/) (2023)
- [Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem](https://mlsanity.com/paper/2310.02016/) (2023)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)

## Abstract (arXiv)

Given a measurement graph G= (V,E) and an unknown signal r ∈ ℝn, we investigate algorithms for recovering r from pairwise measurements of the form ri - rj; i,j ∈ E. This problem arises in a variety of applications, such as ranking teams in sports data and time synchronization of distributed networks. Framed in the context of ranking, the task is to recover the ranking of n teams (induced by r) given a small subset of noisy pairwise rank offsets. We propose a simple SVD-based algorithmic pipeline for both the problem of time synchronization and ranking. We provide a detailed theoretical analysis in terms of robustness against both sampling sparsity and noise perturbations with outliers, using results from matrix perturbation and random matrix theory. Our theoretical findings are complemented by a detailed set of numerical experiments on both synthetic and real data, showcasing the competitiveness of our proposed algorithms with other state-of-the-art methods.