Minimax optimal seriation in polynomial time

Abstract

We consider the seriation problem, whose goal is to recover a hidden ordering from a noisy observation of a permuted Robinson matrix. We establish sharp minimax rates under average-Lipschitz conditions that strictly extend the bi-Lipschitz framework of [Giraud et al., 2023]. We further design a polynomial-time algorithm that attains these optimal rates, thereby resolving two open questions raised in [Giraud et al., 2023]. Finally, our analysis extends to a broader class of matrices beyond those generated by exact permutations.