Ranking and synchronization from pairwise measurements via SVD

Abstract

Given a measurement graph $G=(V,E)$ and an unknown signal $r\in {\mathbb{R}}^n$, we investigate algorithms for recovering $r$ from pairwise measurements of the form $r_i-r_j$; $\{i,j\}\in 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.

arXiv comment49 pages, 10 figures

References in corpus (8)

• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Least Squares Ranking on Graphs
• Low-rank Matrix Completion using Alternating Minimization
• Top-N Recommender System via Matrix Completion
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• Deformed Laplacians and spectral ranking in directed networks
• Ranking Recovery from Limited Comparisons using Low-Rank Matrix Completion

Cited by in corpus (1)

• Network-based ranking in social systems: three challenges