Ranking and synchronization from pairwise measurements via SVD

arXiv1906.02746MaRDI QIDQ6320105FDOQ6320105

Authors: Alexandre d'Aspremont, Mihai Cucuringu, Hemant Tyagi 

Publication date: 6 June 2019

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

This page was built for publication: Ranking and synchronization from pairwise measurements via SVD

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320105)