  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.
