Performance-Complexity Trade-Off in Large Dimensional Statistics

International audienceThis 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 = [x1,. .. , xn] ∈ 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 Kij 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 n , 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