Passer à la navigation principale Passer à la recherche Passer au contenu principal

MINIMAX OPTIMAL SERIATION IN POLYNOMIAL TIME

  • Laboratoire de Mathématiques d'Orsay
  • University of Montpellier (UMR MiVEGEC)

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

1 Citation (Scopus)

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 originaleAnglais
Pages (de - à)1502-1522
Nombre de pages21
journalAnnals of Statistics
Volume54
Numéro de publication3
Les DOIs
étatPublié - 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