# Shuffled Linear Regression via Spectral Matching

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 46 references that are in the map.
- First posted on arXiv 30 Sep 2024.

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

- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [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)
- [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)
- [Blind Graph Matching Using Graph Signals](https://mlsanity.com/paper/2306.15747/) (2023)

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

- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

Shuffled linear regression (SLR) seeks to estimate latent features through a linear transformation, complicated by unknown permutations in the measurement dimensions. This problem extends traditional least-squares (LS) and Least Absolute Shrinkage and Selection Operator (LASSO) approaches by jointly estimating the permutation, resulting in shuffled LS and shuffled LASSO formulations. Existing methods, constrained by the combinatorial complexity of permutation recovery, often address small-scale cases with limited measurements. In contrast, we focus on large-scale SLR, particularly suited for environments with abundant measurement samples. We propose a spectral matching method that efficiently resolves permutations by aligning spectral components of the measurement and feature covariances. Rigorous theoretical analyses demonstrate that our method achieves accurate estimates in both shuffled LS and shuffled LASSO settings, given a sufficient number of samples. Furthermore, we extend our approach to address simultaneous pose and correspondence estimation in image registration tasks. Experiments on synthetic datasets and real-world image registration scenarios show that our method outperforms existing algorithms in both estimation accuracy and registration performance.