Optimal rates for ranking a permuted isotonic matrix in polynomial time

Emmanuel Pilliat, Alexandra Carpentier, Nicolas Verzelen

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 mo…