Optimal Permutation Estimation in CrowdSourcing problems
针对众包应用中部分观测的双变量等调矩阵，提出多项式时间算法，在排列恢复和矩阵估计上达到极小极大风险，并发现某些情况下排列恢复比矩阵估计更简单。
Motivated by crowdsourcing applications, we consider a model where we have partial observations from a bivariate isotonic n×d matrix with an unknown permutation π∗ acting on its rows. Focusing on the twin problems of recovering the permutation π∗ 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 π∗ is considerably simpler than estimating the matrix.