The spectral norm of random inner-product kernel matrices

We study an “inner-product kernel” random matrix model, whose empirical spectral distribution was shown by Xiuyuan Cheng and Amit Singer to converge to a deterministic measure in the large n and p limit. We provide an interpretation of this limit measure as the additive free convolution of a semicircle law and a Marchenko–Pastur law. By comparing the tracial moments of this matrix to an additive deformation of a Wigner matrix, we establish that for odd kernel functions, the spectral norm of this matrix converges almost surely to the edge of the limiting spectrum. Our study is motivated by the analysis of a covariance thresholding procedure for the statistical detection and estimation of sparse principal components, and our results characterize the limit of the largest eigenvalue of the thresholded sample covariance matrix in the null setting.

• Publication year

  2015

• Venue

  Probability Theory and Related Fields

• Publication date

  2015-07-19

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1007/s00440-018-0830-4arXiv 1507.05343
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Domain-Adversarial Training of Neural Networks

  2015cited by this paper
• On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence

  2015cited by this paper
• Spectral Norm of Random Kernel Matrices with Applications to Privacy

  2015cited by this paper
• Optimal estimation and rank detection for sparse spiked covariance matrices

  2014cited by this paper
• Fluctuations at the edges of the spectrum of the full rank deformed GUE

  2014cited by this paper
• Edge universality for deformed Wigner matrices

  2014cited by this paper
• Sparsistency and agnostic inference in sparse PCA

  2014cited by this paper
• Bulk universality for deformed Wigner matrices

  2014cited by this paper
• Sparse PCA via Covariance Thresholding

  2013influential reference
• Asymptotic power of sphericity tests for high-dimensional data

  2013cited by this paper
• Optimal estimation and rank detection for sparse spiked covariance matrices

  2013cited by this paper
• DO SEMIDEFINITE RELAXATIONS SOLVE SPARSE PCA UP TO THE INFORMATION LIMIT

  2013influential reference
• Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

  2013influential reference
• Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA

  2013cited by this paper
• Minimax Rates of Estimation for Sparse PCA in High Dimensions

  2012cited by this paper
• The spectrum of random kernel matrices: universality results for rough and varying kernels

  2012cited by this paper
• Sparse PCA: Optimal rates and adaptive estimation

  2012cited by this paper
• OPTIMAL RATES OF CONVERGENCE FOR SPARSE COVARIANCE MATRIX ESTIMATION

  2012cited by this paper
• THE SPECTRUM OF RANDOM INNER-PRODUCT KERNEL MATRICES

  2012influential reference
• Topics in Random Matrix Theory

  2012cited by this paper
• Optimal detection of sparse principal components in high dimension

  2012cited by this paper
• MINIMAX BOUNDS FOR SPARSE PCA WITH NOISY HIGH-DIMENSIONAL DATA.

  2012cited by this paper
• MINIMAX ESTIMATION OF LARGE COVARIANCE MATRICES UNDER ℓ1-NORM

  2012cited by this paper
• Sparse Principal Component Analysis and Iterative Thresholding

  2011cited by this paper
• Sparse linear discriminant analysis by thresholding for high dimensional data

  2011cited by this paper
• Covariance estimation for distributions with 2+ε moments

  2011cited by this paper
• Universality of covariance matrices

  2011cited by this paper
• On Universality of Local Edge Regime for the Deformed Gaussian Unitary Ensemble

  2011cited by this paper
• Introduction to the non-asymptotic analysis of random matrices

  2010cited by this paper
• The spectrum of kernel random matrices

  2010cited by this paper
• The norm of polynomials in large random and deterministic matrices

  2010cited by this paper
• Free Convolution with a Semicircular Distribution and Eigenvalues of Spiked Deformations of Wigner Matrices

  2010influential reference
• Spectral Analysis of Large Dimensional Random Matrices

  2009influential reference
• Finite sample approximation results for principal component analysis: a matrix perturbation approach

  2009cited by this paper
• Covariance regularization by thresholding

  2009cited by this paper
• Sparse Principal Components Analysis

  2009cited by this paper
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions

  2009cited by this paper
• The local relaxation flow approach to universality of the local statistics for random matrices

  2009cited by this paper
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis.

  2009cited by this paper
• Random covariance matrices: Universality of local statistics of eigenvalues

  2009cited by this paper
• Generalized Thresholding of Large Covariance Matrices

  2009cited by this paper
• High-dimensional analysis of semidefinite relaxations for sparse principal components

  2008influential reference
• Operator norm consistent estimation of large-dimensional sparse covariance matrices

  2008cited by this paper
• Sparse principal component analysis via regularized low rank matrix approximation

  2008cited by this paper
• ASYMPTOTICS OF SAMPLE EIGENSTRUCTURE FOR A LARGE DIMENSIONAL SPIKED COVARIANCE MODEL

  2007cited by this paper
• Sparse Principal Component Analysis

  2006cited by this paper
• Some estimates of norms of random matrices

  2005influential reference
• Rate of convergence in probability to the Marchenko-Pastur law

  2004cited by this paper
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices

  2004cited by this paper
• SOME ESTIMATES OF NORMS OF RANDOM MATRICES

  2004influential reference
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

  2004cited by this paper
• Eigenvalues of large sample covariance matrices of spiked population models

  2004cited by this paper
• A Modified Principal Component Technique Based on the LASSO

  2003cited by this paper
• On the distribution of the largest eigenvalue in principal components analysis

  2001cited by this paper
• ADAPTIVE ESTIMATION OF A QUADRATIC FUNCTIONAL BY MODEL SELECTION

  2001cited by this paper
• Random matrix approximation of spectra of integral operators

  2000influential reference
• On the free convolution with a semi-circular distribution

  1997cited by this paper
• Kernel Principal Component Analysis

  1997influential reference
• On the empirical distribution of eigenvalues of a class of large dimensional random matrices

  1995cited by this paper
• Mathematical Physics © Springer-Verlag 1996 On Orthogonal and Symplectic Matrix Ensembles

  1995cited by this paper
• Multiplicative functions on the lattice of non-crossing partitions and free convolution

  1994cited by this paper
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix

  1993cited by this paper
• A training algorithm for optimal margin classifiers

  1992cited by this paper
• Addition of freely independent random variables

  1992influential reference
• On Certain Free Product Factors via an Extended Matrix Model

  1992cited by this paper
• Limit laws for Random matrices and free products

  1991cited by this paper
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix

  1988cited by this paper
• Addition of certain non-commuting random variables

  1986influential reference
• The eigenvalues of random symmetric matrices

  1981cited by this paper
• A Limit Theorem for the Norm of Random Matrices

  1980cited by this paper
• On orthogonal polynomials

  1975influential reference
• Probability inequalities for sums of independent random variables with values in a Banach space

  1971cited by this paper
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES

  1967cited by this paper
• On Berstein’s approximation problem

  1951cited by this paper
• Journal of the American Statistical Association Adaptive Thresholding for Sparse Covariance Matrix Estimation Adaptive Thresholding for Sparse Covariance Matrix Estimation

  year unknowncited by this paper

• Asymptotic analysis of the Gaussian kernel matrix for partially noisy data in high dimensions

  2026cites this paper
• Global law of conjugate kernel random matrices with heavy-tailed weights

  2026cites this paper
• On the edge eigenvalues of sparse random geometric graphs

  2025cites this paper
• Eigenvalue distribution of the Neural Tangent Kernel in the quadratic scaling

  2025cites this paper
• A geometrical analysis of kernel ridge regression and its applications

  2025cites this paper
• Kernel ridge regression under power-law data: spectrum and generalization

  2025cites this paper
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime

  2025cites this paper
• Global law of conjugate kernel random matrices with heavy-tailed weights

  2025cites this paper
• Efficient Estimation of Kernel Matrix Spectral Norm using Random Features

  2025cites this paper
• A general technique for approximating high-dimensional empirical kernel matrices

  2025cites this paper
• Extremal Eigenvalues of Random Kernel Matrices with Polynomial Scaling

  2024influential citation
• Exact Risk Curves of signSGD in High-Dimensions: Quantifying Preconditioning and Noise-Compression Effects

  2024cites this paper
• Conditioning of random Fourier feature matrices: double descent and generalization error

  2024cites this paper
• "Lossless" Compression of Deep Neural Networks: A High-dimensional Neural Tangent Kernel Approach

  2024cites this paper
• Spectral Properties of Elementwise-Transformed Spiked Matrices

  2023cites this paper
• Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime

  2023cites this paper
• Fundamental limits of overparametrized shallow neural networks for supervised learning

  2023cites this paper
• Spectral clustering in the Gaussian mixture block model

  2023cites this paper
• Demystifying Disagreement-on-the-Line in High Dimensions

  2023cites this paper
• Concentration of Random Feature Matrices in High-Dimensions

  2022cites this paper
• Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach

  2022cites this paper
• Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks

  2022cites this paper
• Local and Global Expansion in Random Geometric Graphs

  2022cites this paper
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation

  2022cites this paper
• An equivalence principle for the spectrum of random inner-product kernel matrices with polynomial scalings

  2022influential citation
• The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks

  2021cites this paper
• Double-descent curves in neural networks: a new perspective using Gaussian processes

  2021cites this paper
• Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model

  2021cites this paper
• Hessian Eigenspectra of More Realistic Nonlinear Models

  2021cites this paper
• Learning curves of generic features maps for realistic datasets with a teacher-student model

  2021cites this paper
• Asymptotic Spectral Behavior of Kernel Matrices in Complex Valued Observations

  2021cites this paper
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error

  2021cites this paper
• How do kernel-based sensor fusion algorithms behave under high dimensional noise?

  2021cites this paper
• Impact of Signal-to-Noise Ratio and Bandwidth on Graph Laplacian Spectrum From High-Dimensional Noisy Point Cloud

  2020cites this paper
• The Gaussian equivalence of generative models for learning with shallow neural networks

  2020cites this paper
• Phase transition of graph Laplacian of high dimensional noisy random point cloud

  2020cites this paper
• Sparse Quantized Spectral Clustering

  2020cites this paper
• Universality Laws for High-Dimensional Learning With Random Features

  2020cites this paper
• The Gaussian equivalence of generative models for learning with two-layer neural networks

  2020cites this paper
• Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint

  2020cites this paper
• Generalisation error in learning with random features and the hidden manifold model

  2020cites this paper
• Submitted to the Annals of Statistics CONCENTRATION OF KERNEL MATRICES WITH APPLICATION TO KERNEL SPECTRAL CLUSTERING By Arash

  2020cites this paper
• Multiple Kernel Learning from $U$-Statistics of Empirical Measures in the Feature Space

  2019cites this paper
• On Inner-Product Kernels of High Dimensional Data

  2019cites this paper
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve

  2019cites this paper
• Eigenvalue distribution of nonlinear models of random matrices

  2019cites this paper
• Modeling the Influence of Data Structure on Learning in Neural Networks: The Hidden Manifold Model

  2019cites this paper
• Surprises in High-Dimensional Ridgeless Least Squares Interpolation

  2019influential citation
• The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime

  2019cites this paper
• On the Spectral Property of Kernel-Based Sensor Fusion Algorithms of High Dimensional Data

  2019cites this paper
• Eigenvalue distribution of some nonlinear models of random matrices

  2019cites this paper
• Inner-product Kernels are Asymptotically Equivalent to Binary Discrete Kernels

  2019cites this paper
• Porcupine Neural Networks: Approximating Neural Network Landscapes

  2018cites this paper
• Submitted to the Annals of Applied Statistics SUBSPACE KERNEL SPECTRAL CLUSTERING OF LARGE DIMENSIONAL DATA By

  2017cites this paper
• Porcupine Neural Networks: (Almost) All Local Optima are Global

  2017cites this paper
• Sparse PCA via Covariance Thresholding

  2013cites this paper