Performance-Complexity Trade-Off in Large Dimensional Statistics

This article introduces a random matrix framework for the analysis of the trade-off between performance and complexity in a class of machine learning algorithms, under a large dimensional data X = [x
₁
, ..., x
_n
] ∈ R
^p×n
regime. Specifically, we analyze the spectral properties of K ⊙ B ∈ R
^n×n
, for the kernel random matrix K=-[1/p]X
^T
X upon which a sparsity mask B ∈ {0,1}
^n×n
is applied: this reduces the number of K
_ij
to evaluate, thereby reducing complexity, while weakening the power of statistical inference on K, thereby impeding performance. Assuming the data structured as X = Z + √(nμv)
^T
for informative vectors μ ∈ R
^p
, v ∈ R
ⁿ
, and white noise Z, we exhibit a phase transition phenomenon below which spectral methods must fail and which is a function of the sparsity structure of B. This finds immediate applications to the fundamental limits of complexity-reduced spectral clustering as well as principal component analysis.