# Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 72 references that are in the map.
- First posted on arXiv 10 Jan 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections](https://mlsanity.com/paper/2107.01718/) (2021)
- [On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising](https://mlsanity.com/paper/1712.02009/) (2017)
- [Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport](https://mlsanity.com/paper/1905.10812/) (2019)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Uncoupled isotonic regression via minimum Wasserstein deconvolution](https://mlsanity.com/paper/1806.10648/) (2018)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Linear Regression with Shuffled Labels](https://mlsanity.com/paper/1705.01342/) (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)
- [A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data](https://mlsanity.com/paper/1910.01623/) (2019)
- [Spherical Regression under Mismatch Corruption with Application to Automated Knowledge Translation](https://mlsanity.com/paper/1810.05679/) (2018)
- [Learning relationships between data obtained independently](https://mlsanity.com/paper/1601.00504/) (2016)
- [An algebraic-geometric approach for linear regression without correspondences](https://mlsanity.com/paper/1810.05440/) (2018)
- [Unlinked monotone regression](https://mlsanity.com/paper/2007.00830/) (2020)

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

- [A New Perspective On Denoising Based On Optimal Transport](https://mlsanity.com/paper/2312.08135/) (2023)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Optimal Estimator for Linear Regression with Shuffled Labels](https://mlsanity.com/paper/2310.01326/) (2023)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

Suppose that we have a regression problem with response variable Y in ℝd and predictor X in ℝd, for d ≥ 1. In permuted or unlinked regression we have access to separate unordered data on X and Y, as opposed to data on (X,Y)-pairs in usual regression. So far in the literature the case d=1 has received attention, see e.g., the recent papers by Rigollet and Weed [Information & Inference, 8, 619--717] and Balabdaoui et al. [J. Mach. Learn. Res., 22(172), 1--60]. In this paper, we consider the general multivariate setting with d ≥ 1. We show that the notion of cyclical monotonicity of the regression function is sufficient for identification and estimation in the permuted/unlinked regression model. We study permutation recovery in the permuted regression setting and develop a computationally efficient and easy-to-use algorithm for denoising based on the Kiefer-Wolfowitz [Ann. Math. Statist., 27, 887--906] nonparametric maximum likelihood estimator and techniques from the theory of optimal transport. We provide explicit upper bounds on the associated mean squared denoising error for Gaussian noise. As in previous work on the case d = 1, the permuted/unlinked setting involves slow (logarithmic) rates of convergence rooting in the underlying deconvolution problem. Numerical studies corroborate our theoretical analysis and show that the proposed approach performs at least on par with the methods in the aforementioned prior work in the case d = 1 while achieving substantial reductions in terms of computational complexity.