PERFORMANCE-COMPLEXITY TRADE-OFF IN LARGE DIMENSIONAL STATISTICS

This article introduces a random matrix framework for the analysis of the performance-complexity trade-off in a class of machine learning algorithms, under a large dimensional data regime. Specifically, we analyze the spectral properties of a kernel random matrix K upon which a sparsity mask B is applied; this reduces the number of entries to evaluate, thereby reducing complexity, while weakening the power of statistical inference on K, thereby impeding performance. 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.