# Shuffled linear regression through graduated convex relaxation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 61 references that are in the map.
- First posted on arXiv 30 Sep 2022.

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

- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [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)
- [Optimal De-Anonymization in Random Graphs with Community Structure](https://mlsanity.com/paper/1602.01409/) (2016)
- [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)
- [Linear Regression without Correspondences via Concave Minimization](https://mlsanity.com/paper/2003.07706/) (2020)
- [Signal Recovery from Unlabeled Samples](https://mlsanity.com/paper/1701.08701/) (2017)
- [Spherical Regression under Mismatch Corruption with Application to Automated Knowledge Translation](https://mlsanity.com/paper/1810.05679/) (2018)
- [A Hypergradient Approach to Robust Regression without Correspondence](https://mlsanity.com/paper/2012.00123/) (2020)
- [Learning relationships between data obtained independently](https://mlsanity.com/paper/1601.00504/) (2016)
- [The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors](https://mlsanity.com/paper/1909.02496/) (2019)
- [Sorting Network Relaxations for Vector Permutation Problems](https://mlsanity.com/paper/1407.6609/) (2014)
- [Projected Power Iteration for Network Alignment](https://mlsanity.com/paper/1707.04929/) (2017)
- [Robust Seriation and Applications to Cancer Genomics](https://mlsanity.com/paper/1806.00664/) (2018)

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

- [Shuffled Multi-Channel Sparse Signal Recovery](https://mlsanity.com/paper/2212.07368/) (2022)
- [Cross-Channel Unlabeled Sensing over a Union of Signal Subspaces](https://mlsanity.com/paper/2506.09773/) (2025)

## Abstract (arXiv)

The shuffled linear regression problem aims to recover linear relationships in datasets where the correspondence between input and output is unknown. This problem arises in a wide range of applications including survey data, in which one needs to decide whether the anonymity of the responses can be preserved while uncovering significant statistical connections. In this work, we propose a novel optimization algorithm for shuffled linear regression based on a posterior-maximizing objective function assuming Gaussian noise prior. We compare and contrast our approach with existing methods on synthetic and real data. We show that our approach performs competitively while achieving empirical running-time improvements. Furthermore, we demonstrate that our algorithm is able to utilize the side information in the form of seeds, which recently came to prominence in related problems.