Minimax Lower Bounds for Linear Independence Testing
share
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.
READ FULL TEXT