# Minimax Lower Bounds for Linear Independence Testing

arXiv: https://arxiv.org/abs/1601.06259 · HTML: https://mlsanity.com/paper/1601.06259/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2016.

## Built on by (most cited first, 3 of 3)

- [Private High-Dimensional Hypothesis Testing](https://mlsanity.com/paper/2203.01537/) (2022)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)

## Abstract (arXiv)

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.