Appears in collection : 2022 - T3 - WS1 - Non-Linear and High Dimensional Inference

Motivated by crowd-sourcing applications, we consider a model where we have partial observations from a bivariate isotonic $n\times d$ matrix with an unknown permutation $\pi^_$ acting on its rows. We consider the twin problems of recovering the permutation $\pi^_$ and estimating the unknown matrix. We introduce a polynomial-time procedure achieving the minimax risk for these two problems, this for all possible values of $n$, $d$, and all possible sampling efforts. Along the way, we establish that, in some regimes, recovering the unknown permutation $\pi^*$ is considerably simpler than estimating the matrix.

This is based on a joint work with Alexandra Carpentier (U. Potsdam) and Emmanuel Pilliat (U. Montpellier).