2024/01/24 by Dor Elimelech, Wasim Huleihel, Elimelech, Dor +1
Mathematics · #Advanced Combinatorial Mathematics #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2401.13429
openalex publication_date 2024/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we investigate the problem of deciding whether two standard normal random vectors X∈ℝn and Y∈ℝ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, X and a randomly and uniformly permuted version of Y, 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.