Taux optimaux de sériation statistique.

Résumé Étant donné une matrice, le problème de la sériation consiste à permuter ses lignes de manière à ce que toutes ses colonnes aient la même forme, par exemple, elles sont monotones croissantes. Nous proposons une approche statistique de ce problème où la matrice d'intérêt est observée avec du bruit et étudions le taux d'estimation minimax correspondant des matrices. Plus précisément, lorsque les colonnes sont soit unimodales soit monotones, nous montrons que l'estimateur des moindres carrés est optimal jusqu'à des facteurs logarithmiques et s'adapte aux matrices ayant une certaine structure naturelle. Enfin, nous proposons un estimateur efficace en termes de calcul dans le cas monotone et étudions ses performances à la fois théoriquement et expérimentalement. Notre travail se situe à l'intersection de l'estimation sous contrainte de forme et des travaux récents qui impliquent l'apprentissage par permutation, comme le débruitage et le classement de graphes.