# Linear Regression with Sparsely Permuted Data

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

## Key facts

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

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

- [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)
- [Linear regression with partially mismatched data: local search with theoretical guarantees](https://mlsanity.com/paper/2106.02175/) (2021)
- [Compensation Learning](https://mlsanity.com/paper/2107.11921/) (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)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Shuffled Multi-Channel Sparse Signal Recovery](https://mlsanity.com/paper/2212.07368/) (2022)
- [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)
- [Analysis and Approximate Inference of Large Random Kronecker Graphs](https://mlsanity.com/paper/2306.08489/) (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)
- [AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization](https://mlsanity.com/paper/2504.14741/) (2025)
- [Cross-Channel Unlabeled Sensing over a Union of Signal Subspaces](https://mlsanity.com/paper/2506.09773/) (2025)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

In regression analysis of multivariate data, it is tacitly assumed that response and predictor variables in each observed response-predictor pair correspond to the same entity or unit. In this paper, we consider the situation of "permuted data" in which this basic correspondence has been lost. Several recent papers have considered this situation without further assumptions on the underlying permutation. In applications, the latter is often to known to have additional structure that can be leveraged. Specifically, we herein consider the common scenario of "sparsely permuted data" in which only a small fraction of the data is affected by a mismatch between response and predictors. However, an adverse effect already observed for sparsely permuted data is that the least squares estimator as well as other estimators not accounting for such partial mismatch are inconsistent. One approach studied in detail herein is to treat permuted data as outliers which motivates the use of robust regression formulations to estimate the regression parameter. The resulting estimate can subsequently be used to recover the permutation. A notable benefit of the proposed approach is its computational simplicity given the general lack of procedures for the above problem that are both statistically sound and computationally appealing.