Testing for correlation in Gaussian databases via local decision making

We propose a computationally efficient statistical test for detecting correlation between two Gaussian databases. The problem is formulated as a hypothesis test: under the null hypothesis, the databases are independent; under the alternative hypothesis, they are correlated but subject to an unknown row permutation. We derive bounds on both type Ⅰ and type Ⅱ error probabilities and demonstrate that the proposed test outperforms a recently introduced method across a broad range of parameter settings. The test statistic is based on a sum of dependent indicator random variables. To effectively bound the type Ⅰ error probability, we introduce a novel graph-theoretic technique for bounding the $k$-th moments of such statistics.