Minimax optimal seriation in polynomial time
研究了在带噪声的置换矩阵中恢复隐藏排序的问题，给出了一个多项式时间算法，其误差达到理论下界，并解决了两个开放问题，对研究排序恢复和矩阵分析的学者有参考价值。
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, Issartel and Verzelen (Electron. J. Stat. (2023) 17 1587–1662). We further design a polynomial-time algorithm that attains these optimal rates, thereby resolving two open questions raised in Giraud, Issartel and Verzelen. Finally, our analysis extends to a broader class of matrices beyond those generated by exact permutations.