Minimax optimal seriation in polynomial time
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911308725616640 |
|---|---|
| author | Issartel, Yann Giraud, Christophe Verzelen, Nicolas |
| author_facet | Issartel, Yann Giraud, Christophe Verzelen, Nicolas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_08747 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimax optimal seriation in polynomial time Issartel, Yann Giraud, Christophe Verzelen, Nicolas Statistics Theory 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. |
| title | Minimax optimal seriation in polynomial time |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2405.08747 |