Optimal rates for ranking a permuted isotonic matrix in polynomial time

Abstract

We consider a ranking problem where we have noisy observations from a matrix with isotonic columns whose rows have been permuted by some permutation $\pi$ *. This encompasses many models, including crowd-labeling and ranking in tournaments by pair-wise comparisons. In this work, we provide an optimal and polynomial-time procedure for recovering $\pi$ * , settling an open problem in [7]. As a byproduct, our procedure is used to improve the state-of-the art for ranking problems in the stochastically transitive model (SST). Our approach is based on iterative pairwise comparisons by suitable data-driven weighted means of the columns. These weights are built using a combination of spectral methods with new dimension-reduction techniques. In order to deal with the important case of missing data, we establish a new concentration inequality for sparse and centered rectangular Wishart-type matrices.

References in corpus (6)

• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Noisy Sorting Without Resampling
• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Concentration of quadratic forms under a Bernstein moment assumption
• Active Ranking of Experts Based on their Performances in Many Tasks
• Optimal Permutation Estimation in Crowd-Sourcing problems