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, 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.
Fields of Study & Subjects
Blind Source Separation Techniques
Random Matrices and Applications
graph theory and CDMA systems
Publication details
- Journal / source
- The Annals of Statistics
- Publisher
- Institute of Mathematical Statistics
- Volume
- 54
- Issue
- 3
- Pages
- 1502-1522
- Publication date
- 1 June 2026
- Language
- EN