The spectrum of kernel random matrices

By Noureddine El Karoui. 2010

243 citations recorded by the source corpus.

We place ourselves in the setting of high-dimensional statistical inference where the number of variables p in a dataset of interest is of the same order of magnitude as the number of observations n. We consider the spectrum of certain kernel random matrices, in particular n x n matrices whose (i, j)th entry is f (X' i X j /p) or f (∥X i - X j ∥ 2 /p) where p is the dimension of the data, and X i are independent data vectors. Here f is assumed to be a locally smooth function. The study is motivated by questions arising in statistics and computer science where these matrices are used to perform, among other things, nonlinear versions of principal component analysis. Surprisingly, we show that in high-dimensions, and for the models we analyze, the problem becomes essentially linear—which is at odds with heuristics sometimes used to justify the usage of these methods. The analysis also highlights certain peculiarities of models widely studied in random matrix theory and raises some questions about their relevance as tools to model high-dimensional data encountered in practice.

Subfields: Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “Specifically, the mean at each entry is E [( xi xj d )2] = Tr[Σ (2)] d2 (i 6 = j), and the moment calculation in El Karoui [2010] shows the following bound on the error matrix F = ( XX> d XX> d − Tr[Σ(2)] d2 11 > )”
Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing (2015, neutral): “While one may conjecture a result like the above due to the claims of El Karoui [2010] that the Gaussian kernel often behaves like the linear kernel in high dimensions, their results only hold true when n d (apart from other differences in assumptions).”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, methodology): “While the message of [14] is often taken as “kernels do not help in high dimensions,” we show that such a random matrix analysis helps in explaining the good performance of interpolation in Kernel “Ridgeless” Regression.”
Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, background): “The asymptotic behavior of kernel matrices has indeed been the subject of intense scrutiny [45, 62, 46, 11, 63, 48].”
The spectral norm of random inner-product kernel matrices (2015, background): “Let us remark that [35, 25] considered distributions for the rows of X where the entries are not necessarily IID, but that the extension of our result to more general covariances Σ ∈ Rp×p for the application of Section 1.”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “For instance, El Karoui et al. (2010); Cheng and Singer (2013); Fan and Montanari (2019) studied the spectral properties of kernel matrix via Taylor series or Hermite polynomials on the nonlinearity, which in turn explains the generalization of high-dimensional kernel ridgeless interpolators (Liang…”
A Random Matrix Approach to Neural Networks (2017, background): “This scenario has the interesting feature that xTi xj → 0 almost surely for all i 6= j while ‖xi‖2 − 1p tr(12C1 + 12C2) → 0, almost surely, irrespective of the class of xi, thereby allowing for a Taylor expansion of the non-linear kernels as early proposed in (El Karoui, 2010). imsart-aap ver.”
Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond (2009, background): “In [15], it is shown that if M has nonnegative entries, and M and E are symmetric, then |‖E ◦ M|‖2 ≤ max i,j (|Ei,j |)|‖M|‖2.”
Random matrix theory in statistics: A review (2014, background): “El Karoui (2010c) also suggested ways of correcting this bias.”
Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2019, unknown): “In a parallel line of work, a closely related idea has recently emerged in the analysis of kernel methods in high dimension [26, 47].”
THE SPECTRUM OF RANDOM INNER-PRODUCT KERNEL MATRICES (2012, methodology): “The spectrum of inner-product random kernel matrices with kernel functions that are locally smooth at the origin has been studied in [12].”
Limitations of Lazy Training of Two-layers Neural Networks (2019, background): “[EK10] Noureddine El Karoui et al., The spectrum of kernel random matrices, The Annals of Statistics 38 (2010), no.”