# Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations

arXiv: https://arxiv.org/abs/1806.09544 · HTML: https://mlsanity.com/paper/1806.09544/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2018.

## Built on by (most cited first, 4 of 4)

- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

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.