Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.10004 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913947294105600 |
|---|---|
| author | Berenfeld, Clément Carpentier, Alexandra Verzelen, Nicolas |
| author_facet | Berenfeld, Clément Carpentier, Alexandra Verzelen, Nicolas |
| contents | In this paper, we consider the problem of seriation of a permuted structured matrix based on noisy observations. The entries of the matrix relate to an expected quantification of interaction between two objects: the higher the value, the closer the objects. A popular structured class for modelling such matrices is the permuted Robinson class, namely the set of matrices whose coefficients are decreasing away from its diagonal, up to a permutation of its lines and columns. We consider in this paper two submodels of Robinson matrices: the Toeplitz model, and the latent position model. We provide a computational lower bound based on the low-degree paradigm, which hints that there is a statistical-computational gap for seriation when measuring the error based on the Frobenius norm. We also provide a simple and polynomial-time algorithm that achives this lower bound. Along the way, we also characterize the information-theory optimal risk thereby giving evidence for the extent of the computation/information gap for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10004 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Seriation of Toeplitz and latent position matrices: optimal rates and computational trade-offs Berenfeld, Clément Carpentier, Alexandra Verzelen, Nicolas Statistics Theory In this paper, we consider the problem of seriation of a permuted structured matrix based on noisy observations. The entries of the matrix relate to an expected quantification of interaction between two objects: the higher the value, the closer the objects. A popular structured class for modelling such matrices is the permuted Robinson class, namely the set of matrices whose coefficients are decreasing away from its diagonal, up to a permutation of its lines and columns. We consider in this paper two submodels of Robinson matrices: the Toeplitz model, and the latent position model. We provide a computational lower bound based on the low-degree paradigm, which hints that there is a statistical-computational gap for seriation when measuring the error based on the Frobenius norm. We also provide a simple and polynomial-time algorithm that achives this lower bound. Along the way, we also characterize the information-theory optimal risk thereby giving evidence for the extent of the computation/information gap for this problem. |
| title | Seriation of Toeplitz and latent position matrices: optimal rates and computational trade-offs |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2408.10004 |