Towards optimal estimation of bivariate isotonic matrices with unknown permutations
研究了在噪声观测下估计双变量等渗矩阵的问题，设计了多项式时间算法，在两种指标上改进了现有方法，并证明了在某些设置下可实现极小化最优的估计。
Many applications, including rank aggregation, crowd-labeling and graphon estimation, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and/or columns. We consider the problem of estimating an unknown matrix in this class, based on noisy observations of (possibly, a subset of) its entries. We design and analyze polynomial-time algorithms that improve upon the state of the art in two distinct metrics, showing, in particular, that minimax optimal, computationally efficient estimation is achievable in certain settings. Along the way, we prove matching upper and lower bounds on the minimax radii of certain cone testing problems, which may be of independent interest. (A corollary of Theorem 3.5 of this paper was presented at the Conference on Learning Theory (COLT) 2018, and a statement of this result appears in the abstract (In Proceedings of the 31st Conference On Learning Theory (2018) 2037–2042 PMLR).)