Minimax Lower Bounds for Linear Independence Testing

Abstract

Linear independence testing is a fundamental information-theoretic and statistical problem that can be posed as follows: given n points \(X_i,Y_i)\^n_i=1 from a p+q dimensional multivariate distribution where X_i R^p and Y_i R^q, determine whether a^T X and b^T Y are uncorrelated for every a R^p, b R^q or not. We give minimax lower bound for this problem (when p+q,n , (p+q)/n < , without sparsity assumptions). In summary, our results imply that n must be at least as large as pq/\|_XY\|_F^2 for any procedure (test) to have non-trivial power, where _XY 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.

Tasks

Reproductions