Description
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).
