{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:52:37Z","timestamp":1791323557483,"version":"4.3.1"},"reference-count":37,"publisher":"Institute of Mathematical Statistics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2026,6,1]]},"abstract":"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\u20131662). 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.<\/jats:p>","DOI":"10.1214\/25-aos2615","type":"journal-article","created":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T13:51:02Z","timestamp":1782395462000},"page":"1502-1522","source":"Crossref","is-referenced-by-count":0,"title":["Minimax optimal seriation in polynomial time"],"prefix":"10.1214","volume":"54","author":[{"given":"Yann","family":"Issartel","sequence":"first","affiliation":[{"name":"LTCI, T\u00e9l\u00e9com Paris, Institut Polytechnique de Paris"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christophe","family":"Giraud","sequence":"additional","affiliation":[{"name":"Laboratoire de Math\u00e9matiques d\u2019Orsay, Universit\u00e9 Paris-Saclay"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Verzelen","sequence":"additional","affiliation":[{"name":"MISTEA, INRAE, Institut Agro, Universit\u00e9 Montpellier"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"8","doi-asserted-by":"publisher","unstructured":"CHEN, P.<\/small>, GAO, C.<\/small> and ZHANG, A. Y.<\/small> (2022). Optimal full ranking from pairwise comparisons. Ann. Statist.<\/i> 50<\/b> 1775\u20131805.","DOI":"10.1214\/22-aos2175"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Vershynin, R.<\/small> (2018). High-Dimensional Probability<\/i>: An Introduction with Applications in Data Science<\/i>. Cambridge Series in Statistical and Probabilistic Mathematics<\/i> 47<\/b>. Cambridge Univ. Press, Cambridge. With a foreword by Sara van de Geer.","DOI":"10.1017\/9781108231596"},{"key":"7","doi-asserted-by":"publisher","unstructured":"CHATTERJEE, S.<\/small> and MUKHERJEE, S.<\/small> (2019). Estimation in tournaments and graphs under monotonicity constraints. IEEE Trans. Inf. Theory<\/i> 65<\/b> 3525\u20133539.","DOI":"10.1109\/TIT.2019.2893911"},{"key":"15","doi-asserted-by":"publisher","unstructured":"FLAMMARION, N.<\/small>, MAO, C.<\/small> and RIGOLLET, P.<\/small> (2019). Optimal rates of statistical seriation. Bernoulli<\/i> 25<\/b> 623\u2013653.","DOI":"10.3150\/17-bej1000"},{"key":"27","doi-asserted-by":"publisher","unstructured":"MAO, C.<\/small>, PANANJADY, A.<\/small> and WAINWRIGHT, M. J.<\/small> (2020). Towards optimal estimation of bivariate isotonic matrices with unknown permutations. Ann. Statist.<\/i> 48<\/b> 3183\u20133205.","DOI":"10.1214\/19-AOS1925"},{"key":"12","unstructured":"COLLIER, O.<\/small> and DALALYAN, A. S.<\/small> (2016). Minimax rates in permutation estimation for feature matching. J. Mach. Learn. Res.<\/i> 17<\/b> Paper No. 6, 31."},{"key":"32","doi-asserted-by":"publisher","unstructured":"RECANATI, A.<\/small>, BR\u00dcLS, T.<\/small> and D\u2019ASPREMONT, A.<\/small> (2017). A spectral algorithm for fast de novo layout of uncorrected long nanopore reads. Bioinformatics<\/i> 33<\/b> 3188\u20133194.","DOI":"10.1093\/bioinformatics\/btx370"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Chen, Y.<\/small>, Fan, J.<\/small>, Ma, C.<\/small> and Wang, K.<\/small> (2019). Spectral method and regularized MLE are both optimal for top-K<\/i> ranking. Ann. Statist.<\/i> 47<\/b> 2204\u20132235.","DOI":"10.1214\/18-AOS1745"},{"key":"36","doi-asserted-by":"publisher","unstructured":"ROCHA, I.<\/small>, JANSSEN, J.<\/small> and KALYANIWALLA, N.<\/small> (2018). Recovering the structure of random linear graphs. Linear Algebra Appl.<\/i> 557<\/b> 234\u2013264.","DOI":"10.1016\/j.laa.2018.07.029"},{"key":"4","unstructured":"BRAVERMAN, M.<\/small> and MOSSEL, E.<\/small> (2009). Sorting from noisy information. ArXiv preprint. Available at arXiv:0910.1191<\/a>."},{"key":"1","doi-asserted-by":"publisher","unstructured":"ATKINS, J. E.<\/small>, BOMAN, E. G.<\/small> and HENDRICKSON, B.<\/small> (1998). A spectral algorithm for seriation and the consecutive ones problem. SIAM J. Comput.<\/i> 28<\/b> 297\u2013310.","DOI":"10.1137\/S0097539795285771"},{"key":"2","doi-asserted-by":"publisher","unstructured":"BARNARD, S. T.<\/small>, POTHEN, A.<\/small> and SIMON, H.<\/small> (1995). A spectral algorithm for envelope reduction of sparse matrices. Numer. Linear Algebra Appl.<\/i> 2<\/b> 317\u2013334.","DOI":"10.1002\/nla.1680020402"},{"key":"3","unstructured":"BERENFELD, C.<\/small>, CARPENTIER, A.<\/small> and VERZELEN, N.<\/small> (2024). Seriation of Toeplitz and latent position matrices: Optimal rates and computational trade-offs. arXiv preprint. Available at arXiv:2408.10004<\/a>."},{"key":"5","doi-asserted-by":"publisher","unstructured":"CAI, T. T.<\/small> and MA, R.<\/small> (2024). Matrix reordering for noisy disordered matrices: Optimality and computationally efficient algorithms. IEEE Trans. Inf. Theory<\/i> 70<\/b> 509\u2013531.","DOI":"10.1109\/tit.2023.3305538"},{"key":"6","doi-asserted-by":"publisher","unstructured":"CARMONA, M.<\/small>, CHEPOI, V.<\/small>, NAVES, G.<\/small> and PR\u00c9A, P.<\/small> (2024). Modules in Robinson spaces. SIAM J. Discrete Math.<\/i> 38<\/b> 190\u2013224.","DOI":"10.1137\/22M1494348"},{"key":"10","unstructured":"CHEPOI, V.<\/small> and SESTON, M.<\/small> (2009). An approximation algorithm for l<\/mi><\/mrow>\u221e<\/mi><\/mrow><\/msub><\/math>-fitting Robinson structures to distances. In STACS<\/i> 2009: 26th International Symposium on Theoretical Aspects of Computer Science<\/i>. LIPIcs. Leibniz Int. Proc. Inform.<\/i> 3<\/b> 265\u2013276. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern."},{"key":"11","doi-asserted-by":"crossref","unstructured":"CHESHIRE, J.<\/small> and ISSARTEL, Y.<\/small> (2025). Active seriation: Efficient ordering recovery with statistical guarantees. In The Thirty-Ninth Annual Conference on Neural Information Processing Systems<\/i>.","DOI":"10.52202\/085713-4842"},{"key":"13","doi-asserted-by":"crossref","unstructured":"DIACONIS, P.<\/small> and GRAHAM, R. L.<\/small> (2018). Spearman\u2019s footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B, Methodol.<\/i> 39<\/b> 262\u2013268.","DOI":"10.1111\/j.2517-6161.1977.tb01624.x"},{"key":"14","doi-asserted-by":"publisher","unstructured":"ELSON, J.<\/small>, KARP, R. M.<\/small>, PAPADIMITRIOU, C. H.<\/small> and SHENKER, S.<\/small> (2004). Global synchronization in sensornets. In LATIN<\/i> 2004: Theoretical Informatics<\/i> (M. Farach-Colton, ed.). Lecture Notes in Computer Science<\/i> 2976<\/b> 609\u2013624. Springer, Berlin.","DOI":"10.1007\/978-3-540-24698-5_63"},{"key":"16","unstructured":"FOGEL, F.<\/small>, D\u2019ASPREMONT, A.<\/small> and VOJNOVIC, M.<\/small> (2014). SerialRank: Spectral ranking using seriation. In Advances in Neural Information Processing Systems<\/i> (Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence and K. Q. Weinberger, eds.) 27. Curran Associates, Red Hook."},{"key":"17","doi-asserted-by":"publisher","unstructured":"FOGEL, F.<\/small>, JENATTON, R.<\/small>, BACH, F.<\/small> and D\u2019ASPREMONT, A.<\/small> (2015). Convex relaxations for permutation problems. SIAM J. Matrix Anal. Appl.<\/i> 36<\/b> 1465\u20131488.","DOI":"10.1137\/130947362"},{"key":"18","doi-asserted-by":"crossref","unstructured":"FULKERSON, D. R.<\/small> and GROSS, O. A.<\/small> (1965). Incidence matrices and interval graphs. Pacific J. Math.<\/i> 15<\/b> 835\u2013855.","DOI":"10.2140\/pjm.1965.15.835"},{"key":"19","doi-asserted-by":"publisher","unstructured":"GALSTYAN, T.<\/small>, MINASYAN, A.<\/small> and DALALYAN, A. S.<\/small> (2022). Optimal detection of the feature matching map in presence of noise and outliers. Electron. J. Stat.<\/i> 16<\/b> 5720\u20135750.","DOI":"10.1214\/22-ejs2076"},{"key":"20","doi-asserted-by":"crossref","unstructured":"GARRIGA, G. C.<\/small>, JUNTTILA, E.<\/small> and MANNILA, H.<\/small> (2011). Banded structure in binary matrices. Knowl. Inf. Syst.<\/i> 28<\/b> 197\u2013226.","DOI":"10.1007\/s10115-010-0319-7"},{"key":"21","doi-asserted-by":"publisher","unstructured":"GIRAUD, C.<\/small>, ISSARTEL, Y.<\/small> and VERZELEN, N.<\/small> (2023). Localization in 1D non-parametric latent space models from pairwise affinities. Electron. J. Stat.<\/i> 17<\/b> 1587\u20131662.","DOI":"10.1214\/23-ejs2134"},{"key":"22","doi-asserted-by":"crossref","unstructured":"GIRIDHAR, A.<\/small> and KUMAR, P. R.<\/small> (2006). Distributed clock synchronization over wireless networks: Algorithms and analysis. In Proceedings of the<\/i> 45th IEEE Conference on Decision and Control<\/i> 4915\u20134920.","DOI":"10.1109\/CDC.2006.377325"},{"key":"23","doi-asserted-by":"publisher","unstructured":"H\u00dcTTER, J.-C.<\/small>, MAO, C.<\/small>, RIGOLLET, P.<\/small> and ROBEVA, E.<\/small> (2020). Estimation of Monge matrices. Bernoulli<\/i> 26<\/b> 3051\u20133080.","DOI":"10.3150\/20-BEJ1215"},{"key":"24","unstructured":"ISSARTEL, Y.<\/small> (2021). On the estimation of network complexity: Dimension of graphons. J. Mach. Learn. Res.<\/i> 22<\/b> Paper No. 191, 62."},{"key":"25","doi-asserted-by":"crossref","unstructured":"ISSARTEL, Y.<\/small>, GIRAUD, C.<\/small> and VERZELEN, N.<\/small> (2026). Supplement to \u201cMinimax optimal seriation in polynomial time.\u201d https:\/\/doi.org\/10.1214\/25-AOS2615SUPP<\/a>","DOI":"10.1214\/25-AOS2615SUPP"},{"key":"26","doi-asserted-by":"publisher","unstructured":"JANSSEN, J.<\/small> and SMITH, A.<\/small> (2022). Reconstruction of line-embeddings of graphons. Electron. J. Stat.<\/i> 16<\/b> 331\u2013407.","DOI":"10.1214\/21-ejs1940"},{"key":"28","unstructured":"MAO, C.<\/small>, WEED, J.<\/small> and RIGOLLET, P.<\/small> (2018). Minimax rates and efficient algorithms for noisy sorting. In Algorithmic Learning Theory<\/i> 2018. Proc. Mach. Learn. Res<\/i>. (PMLR<\/i>) 83<\/b> 27. PMLR."},{"key":"29","unstructured":"MASSART, P.<\/small> (2007). Concentration Inequalities and Model Selection<\/i>. Lecture Notes in Math.<\/i> 1896<\/b>. Springer, Berlin. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6\u201323, 2003. With a foreword by Jean Picard."},{"key":"30","doi-asserted-by":"publisher","unstructured":"NATIK, A.<\/small> and SMITH, A.<\/small> (2026). Consistency of spectral seriation. ESAIM Probab. Stat.<\/i> 30<\/b> 120\u2013161.","DOI":"10.1051\/ps\/2025018"},{"key":"31","doi-asserted-by":"publisher","unstructured":"PR\u00c9A, P.<\/small> and FORTIN, D.<\/small> (2014). An optimal algorithm to recognize Robinsonian dissimilarities. J. Classification<\/i> 31<\/b> 351\u2013385.","DOI":"10.1007\/s00357-014-9150-2"},{"key":"33","unstructured":"RECANATI, A.<\/small>, KERDREUX, T.<\/small> and D\u2019ASPREMONT, A.<\/small> (2018). Reconstructing latent orderings by spectral clustering. arXiv preprint. Available at arXiv:1807.07122<\/a>."},{"key":"34","unstructured":"RIGOLLET, P.<\/small> and H\u00dcTTER, J.-C.<\/small> (2023). High-dimensional statistics. arXiv preprint. Available at arXiv:2310.19244<\/a>."},{"key":"35","doi-asserted-by":"crossref","unstructured":"ROBINSON, W. S.<\/small> (1951). A method for chronologically ordering archaeological deposits. Amer. Antiq.<\/i> 16<\/b> 293\u2013301.","DOI":"10.2307\/276978"}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:19:34Z","timestamp":1791321574000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-54\/issue-3\/Minimax-optimal-seriation-in-polynomial-time\/10.1214\/25-AOS2615.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,1]]},"references-count":37,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2026,6,1]]}},"URL":"https:\/\/doi.org\/10.1214\/25-aos2615","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,1]]}}}