Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - Université de Rouen Normandie

We consider the problem of embedding a set of items in a one-dimensional torus, using noisy observations of pairwise affinities. Importantly, the affinity function between items is unknown and it is only assumed that items with high affinity should be close in the latent space and that the affinity is a smooth function of latent positions. We introduce a new embedding procedure that provably uniformly localizes the latent positions of all items up to a precision of order $\sqrt{\log(n)/n}$. Conversely, this rate is proved to be minimax optimal. We also analyze a computationally efficient alternative procedure that achieves the optimal localization rate under additional assumptions on the affinity function. Finally, our general results are applied to the problem of statistical seriation.

Cet exposé rentre dans le cadre de l'ANR SMILES ANR-18-CE40-0014.