# A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2019.

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

- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [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)
- [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)
- [Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing](https://mlsanity.com/paper/2211.07621/) (2022)
- [Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators](https://mlsanity.com/paper/2303.11233/) (2023)
- [Optimal Estimator for Linear Regression with Shuffled Labels](https://mlsanity.com/paper/2310.01326/) (2023)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

A tacit assumption in linear regression is that (response, predictor)-pairs correspond to identical observational units. A series of recent works have studied scenarios in which this assumption is violated under terms such as ``Unlabeled Sensing and ``Regression with Unknown Permutation''. In this paper, we study the setup of multiple response variables and a notion of mismatches that generalizes permutations in order to allow for missing matches as well as for one-to-many matches. A two-stage method is proposed under the assumption that most pairs are correctly matched. In the first stage, the regression parameter is estimated by handling mismatches as contaminations, and subsequently the generalized permutation is estimated by a basic variant of matching. The approach is both computationally convenient and equipped with favorable statistical guarantees. Specifically, it is shown that the conditions for permutation recovery become considerably less stringent as the number of responses m per observation increase. Particularly, for m = Omega(log n), the required signal-to-noise ratio no longer depends on the sample size n. Numerical results on synthetic and real data are presented to support the main findings of our analysis.