# Estimation of Monge Matrices

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2019.

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

- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Scaling up Ranking under Constraints for Live Recommendations by Replacing Optimization with Prediction](https://mlsanity.com/paper/2202.07088/) (2022)
- [From Cone Geometry to Monge Structure: Local Defects and Global Regret in High-Dimensional Optimal Transport](https://mlsanity.com/paper/2606.04695/) (2026)

## Abstract (arXiv)

Monge matrices and their permuted versions known as pre-Monge matrices naturally appear in many domains across science and engineering. While the rich structural properties of such matrices have long been leveraged for algorithmic purposes, little is known about their impact on statistical estimation. In this work, we propose to view this structure as a shape constraint and study the problem of estimating a Monge matrix subject to additive random noise. More specifically, we establish the minimax rates of estimation of Monge and pre-Monge matrices. In the case of pre-Monge matrices, the minimax-optimal least-squares estimator is not efficiently computable, and we propose two efficient estimators and establish their rates of convergence. Our theoretical findings are supported by numerical experiments.