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.
