# Denoising Linear Models with Permuted Data

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2017.

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

- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport](https://mlsanity.com/paper/2201.03528/) (2022)
- [Linear regression with partially mismatched data: local search with theoretical guarantees](https://mlsanity.com/paper/2106.02175/) (2021)
- [Shuffled linear regression through graduated convex relaxation](https://mlsanity.com/paper/2209.15608/) (2022)
- [Multiview Sensing With Unknown Permutations: An Optimal Transport Approach](https://mlsanity.com/paper/2103.07458/) (2021)
- [Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group](https://mlsanity.com/paper/2111.01767/) (2021)
- [Shuffled Linear Regression via Spectral Matching](https://mlsanity.com/paper/2410.00078/) (2024)
- [Modeling and Correcting Bias in Sequential Evaluation](https://mlsanity.com/paper/2205.01607/) (2022)
- [Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing](https://mlsanity.com/paper/2211.07621/) (2022)
- [Optimal Estimator for Linear Regression with Shuffled Labels](https://mlsanity.com/paper/2310.01326/) (2023)

## Abstract (arXiv)

The multivariate linear regression model with shuffled data and additive Gaussian noise arises in various correspondence estimation and matching problems. Focusing on the denoising aspect of this problem, we provide a characterization the minimax error rate that is sharp up to logarithmic factors. We also analyze the performance of two versions of a computationally efficient estimator, and establish their consistency for a large range of input parameters. Finally, we provide an exact algorithm for the noiseless problem and demonstrate its performance on an image point-cloud matching task. Our analysis also extends to datasets with outliers.