Detection of Correlated Random Vectors

In this paper, we investigate the problem of deciding whether two standard normal random vectors <tex-math notation="LaTeX">X∈ Rⁿ </tex-math> and <tex-math notation="LaTeX">Y∈ Rⁿ </tex-math> 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, <tex-math notation="LaTeX">X </tex-math> and a randomly and uniformly permuted version of <tex-math notation="LaTeX">Y </tex-math> , are correlated with correlation <tex-math notation="LaTeX">ρ </tex-math> . We analyze the thresholds at which optimal testing is information-theoretically impossible and possible, as a function of n and <tex-math notation="LaTeX">ρ </tex-math> . 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.