# Optimal Permutation Recovery in Permuted Monotone Matrix Model

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2019.

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

- [Optimal Estimation of Shared Singular Subspaces across Multiple Noisy Matrices](https://mlsanity.com/paper/2411.17054/) (2024)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport](https://mlsanity.com/paper/2201.03528/) (2022)
- [Multiplicative Dynamic Mode Decomposition](https://mlsanity.com/paper/2405.05334/) (2024)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group](https://mlsanity.com/paper/2111.01767/) (2021)
- [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)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

Motivated by recent research on quantifying bacterial growth dynamics based on genome assemblies, we consider a permuted monotone matrix model Y=ThetaPi+Z, where the rows represent different samples, the columns represent contigs in genome assemblies and the elements represent log-read counts after preprocessing steps and Guanine-Cytosine (GC) adjustment. In this model, Theta is an unknown mean matrix with monotone entries for each row, Pi is a permutation matrix that permutes the columns of Theta, and Z is a noise matrix. This paper studies the problem of estimation/recovery of Pi given the observed noisy matrix Y. We propose an estimator based on the best linear projection, which is shown to be minimax rate-optimal for both exact recovery, as measured by the 0-1 loss, and partial recovery, as quantified by the normalized Kendall's tau distance. Simulation studies demonstrate the superior empirical performance of the proposed estimator over alternative methods. We demonstrate the methods using a synthetic metagenomics dataset of 45 closely related bacterial species and a real metagenomic dataset to compare the bacterial growth dynamics between the responders and the non-responders of the IBD patients after 8 weeks of treatment.