# MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2020.

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

- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [Reversible Gromov-Monge Sampler for Simulation-Based Inference](https://mlsanity.com/paper/2109.14090/) (2021)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Gromov-Wasserstein-like Distances in the Gaussian Mixture Models Space](https://mlsanity.com/paper/2310.11256/) (2023)
- [Scalable unsupervised alignment of general metric and non-metric structures](https://mlsanity.com/paper/2406.13507/) (2024)
- [Robust Alignment via Partial Gromov-Wasserstein Distances](https://mlsanity.com/paper/2506.21507/) (2025)
- [Cluster-Aware Matching via Laplacian Optimal Transport](https://mlsanity.com/paper/2607.16178/) (2026)

## Abstract (arXiv)

Comparing and aligning large datasets is a pervasive problem occurring across many different knowledge domains. We introduce and study MREC, a recursive decomposition algorithm for computing matchings between data sets. The basic idea is to partition the data, match the partitions, and then recursively match the points within each pair of identified partitions. The matching itself is done using black box matching procedures that are too expensive to run on the entire data set. Using an absolute measure of the quality of a matching, the framework supports optimization over parameters including partitioning procedures and matching algorithms. By design, MREC can be applied to extremely large data sets. We analyze the procedure to describe when we can expect it to work well and demonstrate its flexibility and power by applying it to a number of alignment problems arising in the analysis of single cell molecular data.