Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.08747 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |