# One-Way Matching of Datasets with Low Rank Signals

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 42 references that are in the map.
- First posted on arXiv 29 Apr 2022.

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

- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [From tree matching to sparse graph alignment](https://mlsanity.com/paper/2002.01258/) (2020)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Database Alignment with Gaussian Features](https://mlsanity.com/paper/1903.01422/) (2019)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Strong recovery of geometric planted matchings](https://mlsanity.com/paper/2107.05567/) (2021)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)

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

- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions](https://mlsanity.com/paper/2407.03522/) (2024)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)

## Abstract (arXiv)

We study one-way matching of a pair of datasets with low rank signals. Under a stylized model, we first derive information-theoretic limits of matching under a mismatch proportion loss. We then show that linear assignment with projected data achieves fast rates of convergence and sometimes even minimax rate optimality for this task. The theoretical error bounds are corroborated by simulated examples. Furthermore, we illustrate practical use of the matching procedure on two single-cell data examples.