# Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 82 references that are in the map.
- First posted on arXiv 17 Jan 2022.

## Builds on (most cited first, 19 of 19)

- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [Learning from Comparisons and Choices](https://mlsanity.com/paper/1704.07228/) (2017)
- [Optimal Rates of Statistical Seriation](https://mlsanity.com/paper/1607.02435/) (2016)
- [Optimal Permutation Recovery in Permuted Monotone Matrix Model](https://mlsanity.com/paper/1911.10604/) (2019)
- [Hidden Hamiltonian Cycle Recovery via Linear Programming](https://mlsanity.com/paper/1804.05436/) (2018)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Consistent recovery threshold of hidden nearest neighbor graphs](https://mlsanity.com/paper/1911.08004/) (2019)
- [Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates](https://mlsanity.com/paper/2002.07624/) (2020)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations](https://mlsanity.com/paper/1806.09544/) (2018)
- [Reconstructing Latent Orderings by Spectral Clustering](https://mlsanity.com/paper/1807.07122/) (2018)
- [Estimation of Monge Matrices](https://mlsanity.com/paper/1904.03136/) (2019)
- [An Optimal Algorithm for Strict Circular Seriation](https://mlsanity.com/paper/2106.05944/) (2021)

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

- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)

## Abstract (arXiv)

Motivated by applications in single-cell biology and metagenomics, we investigate the problem of matrix reordering based on a noisy disordered monotone Toeplitz matrix model. We establish the fundamental statistical limit for this problem in a decision-theoretic framework and demonstrate that a constrained least squares estimator achieves the optimal rate. However, due to its computational complexity, we analyze a popular polynomial-time algorithm, spectral seriation, and show that it is suboptimal. To address this, we propose a novel polynomial-time adaptive sorting algorithm with guaranteed performance improvement. Simulations and analyses of two real single-cell RNA sequencing datasets demonstrate the superiority of our algorithm over existing methods.