# Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 55 references that are in the map.
- First posted on arXiv 22 Nov 2023.

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

- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Orthogonal Statistical Learning](https://mlsanity.com/paper/1901.09036/) (2019)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Double/Debiased/Neyman Machine Learning of Treatment Effects](https://mlsanity.com/paper/1701.08687/) (2017)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Towards Optimal Transport with Global Invariances](https://mlsanity.com/paper/1806.09277/) (2018)
- [Orthogonal Machine Learning: Power and Limitations](https://mlsanity.com/paper/1711.00342/) (2017)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2007.00533/) (2020)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Unsupervised Hyperalignment for Multilingual Word Embeddings](https://mlsanity.com/paper/1811.01124/) (2018)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [The Fundamental Limits of Structure-Agnostic Functional Estimation](https://mlsanity.com/paper/2305.04116/) (2023)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Optimal Rates of Statistical Seriation](https://mlsanity.com/paper/1607.02435/) (2016)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Estimation of functionals of sparse covariance matrices](https://mlsanity.com/paper/1408.5087/) (2014)
- [Optimal transport for automatic alignment of untargeted metabolomic data](https://mlsanity.com/paper/2306.03218/) (2023)

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

- [Beyond Distance: Quantifying Point Cloud Dynamics with Persistent Homology and Dynamic Optimal Transport](https://mlsanity.com/paper/2603.15683/) (2026)

## Abstract (arXiv)

Feature alignment methods are used in many scientific disciplines for data pooling, annotation, and comparison. As an instance of a permutation learning problem, feature alignment presents significant statistical and computational challenges. In this work, we propose the covariance alignment model to study and compare various alignment methods and establish a minimax lower bound for covariance alignment that has a non-standard dimension scaling because of the presence of a nuisance parameter. This lower bound is in fact minimax optimal and is achieved by a natural quasi MLE. However, this estimator involves a search over all permutations which is computationally infeasible even when the problem has moderate size. To overcome this limitation, we show that the celebrated Gromov-Wasserstein algorithm from optimal transport which is more amenable to fast implementation even on large-scale problems is also minimax optimal. These results give the first statistical justification for the deployment of the Gromov-Wasserstein algorithm in practice.