Résumé
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.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 1502-1522 |
| Nombre de pages | 21 |
| journal | Annals of Statistics |
| Volume | 54 |
| Numéro de publication | 3 |
| Les DOIs | |
| état | Publié - 1 juin 2026 |
Empreinte digitale
Examiner les sujets de recherche de « MINIMAX OPTIMAL SERIATION IN POLYNOMIAL TIME ». Ensemble, ils forment une empreinte digitale unique.Contient cette citation
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver