# Detection of Correlated Random Vectors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 24 Jan 2024.

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

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Testing correlation of unlabeled random graphs](https://mlsanity.com/paper/2008.10097/) (2020)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [Database Alignment with Gaussian Features](https://mlsanity.com/paper/1903.01422/) (2019)
- [The Planted Matching Problem: Phase Transitions and Exact Results](https://mlsanity.com/paper/1912.08880/) (2019)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [A Concentration of Measure Approach to Database De-anonymization](https://mlsanity.com/paper/1901.07655/) (2019)
- [Sequential Classification with Empirically Observed Statistics](https://mlsanity.com/paper/1912.01170/) (2019)
- [On Correlation Detection and Alignment Recovery of Gaussian Databases](https://mlsanity.com/paper/2211.01069/) (2022)
- [Phase Transitions in the Detection of Correlated Databases](https://mlsanity.com/paper/2302.03380/) (2023)
- [Testing Dependency of Unlabeled Databases](https://mlsanity.com/paper/2311.05874/) (2023)

## Abstract (arXiv)

In this paper, we investigate the problem of deciding whether two standard normal random vectors mathsfX∈ℝn and mathsfY∈ℝn are correlated or not. This is formulated as a hypothesis testing problem, where under the null hypothesis, these vectors are statistically independent, while under the alternative, mathsfX and a randomly and uniformly permuted version of mathsfY, are correlated with correlation ρ. We analyze the thresholds at which optimal testing is information-theoretically impossible and possible, as a function of n and ρ. To derive our information-theoretic lower bounds, we develop a novel technique for evaluating the second moment of the likelihood ratio using an orthogonal polynomials expansion, which among other things, reveals a surprising connection to integer partition functions. We also study a multi-dimensional generalization of the above setting, where rather than two vectors we observe two databases/matrices, and furthermore allow for partial correlations between these two.