Seriation of Tœplitz and latent position matrices: Optimal rates and computational trade-offs
Abstract
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 modeling 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 rows and columns. We consider in this paper two submodels of Robinson matrices: the Tœplitz 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 achieves 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.
Related
- Eigenvector distributions and optimal shrinkage estimators for large covariance and precision matrices
- From Matrices to Morphisms II: Examples of Computational Categories in MATLAB and Octave
- An optimal pinching theorem on compact minimal submanifolds in the Euclidean spheres via eigenvalues of fundamental matrices
- An optimal pinching theorem on compact minimal submanifolds in the Euclidean spheres via eigenvalues of fundamental matrices II
- A computational framework for multidimensional loop-cocyclic Hadamard matrices
BibTeX
@article{berenfeld2026seriation,
title = {{Seriation of Tœplitz and latent position matrices: Optimal rates and computational trade-offs}},
author = {Clément Berenfeld and Alexandra Carpentier and Nicolas Verzelen},
journal = {Bernoulli},
year = {2026},
month = oct,
doi = {10.3150/25-bej1915},
url = {https://hal.inrae.fr/hal-05715863v1},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Seriation of Tœplitz and latent position matrices: Optimal rates and computational trade-offs
AU - Clément Berenfeld
AU - Alexandra Carpentier
AU - Nicolas Verzelen
PY - 2026
DA - 2026/10/30
JO - Bernoulli
DO - 10.3150/25-bej1915
UR - https://hal.inrae.fr/hal-05715863v1
AB - 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 modeling 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 rows and columns. We consider in this paper two submodels of Robinson matrices: the Tœplitz 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 achieves 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.
SN - 1350-7265
ER -