Motivated by crowd-sourcing applications, we consider a model where we have partial observations from a bivariate isotonic n x d matrix with an unknown permutation $\pi$ * acting on its rows. Focusing on 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.
翻译:在众包应用的推动下,我们考虑了一个模型,我们从一个二变异异位数 n x d 矩阵中进行部分观测,该矩阵在行内运行的变异值为未知的 $\ pi $ * 。我们集中关注恢复变异值 $\ pi $ * 和估算未知矩阵的双重问题,我们引入了一个多时程序,实现这两个问题的最低风险,这是所有可能的n, d 值和所有可能的取样努力。 顺便提一下,我们确定在某些制度中,恢复未知变异值 $\ pi $ * 要比估算矩阵简单得多。