Minimax Lower Bounds for Linear Independence Testing
This addresses a fundamental statistical problem for researchers in information theory and statistics, but it is incremental as it focuses on deriving lower bounds without proposing new methods.
The paper tackles the problem of linear independence testing by establishing minimax lower bounds, showing that the sample size n must be at least sqrt(pq)/||Σ_XY||_F^2 for any test to have non-trivial power, and provides evidence that this bound is tight in certain settings.
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 \in \mathbb{R}^p$ and $Y_i \in\mathbb{R}^q$, determine whether $a^T X$ and $b^T Y$ are uncorrelated for every $a \in \mathbb{R}^p, b\in \mathbb{R}^q$ or not. We give minimax lower bound for this problem (when $p+q,n \to \infty$, $(p+q)/n \leq κ< \infty$, without sparsity assumptions). In summary, our results imply that $n$ must be at least as large as $\sqrt {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.