Minimax optimal seriation in polynomial time

We consider the statistical seriation problem, where the statistician seeks to recover a hidden ordering from a noisy observation of a permuted Robinson matrix. In this paper, we tightly characterize the minimax rate for this problem of matrix reordering when the Robinson matrix is bi-Lipschitz, and...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-05
Main Authors: Issartel, Yann, Giraud, Christophe, Verzelen, Nicolas
Format: Article
Language:English
Subjects:
Algorithms
Minimax technique
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the statistical seriation problem, where the statistician seeks to recover a hidden ordering from a noisy observation of a permuted Robinson matrix. In this paper, we tightly characterize the minimax rate for this problem of matrix reordering when the Robinson matrix is bi-Lipschitz, and we also provide a polynomial time algorithm achieving this rate; thereby answering two open questions of [Giraud et al., 2021]. Our analysis further extends to broader classes of similarity matrices.
ISSN:2331-8422