Minimax Lower Bounds for Linear Independence Testing

Linear independence testing is a fundamental information-theoretic and statistical problem that can be posed as follows: given n points (Xi,Yi)ni=1 from a p+q dimensional multivariate distribution where Xi ∈ ℝp and Yi ∈ℝq, determine whether aT X and bT Y are uncorrelated for every a ∈ ℝp, b∈ ℝq or not. We give minimax lower bound for this problem (when p+q,n → ∞, (p+q)/n ≤ kappa < ∞, without sparsity assumptions). In summary, our results imply that n must be at least as large as √ pq/|SigmaXY|F2 for any procedure (test) to have non-trivial power, where SigmaXY is the cross-covariance matrix of X,Y. We also provide some evidence that the lower bound is tight, by connections to two-sample testing and regression in specific settings.