The Kato-Temple inequality and eigenvalue concentration with applications to graph inference

DOI10.1214/17-EJS1328MaRDI QIDQ2412262zbMATH OpenOpenAlexFDO

Authors Joshua Cape, Minh Tang, Carey E. Priebe

Publication date 23 October 2017

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.06100, https://projecteuclid.org/euclid.ejs/1508292532

zbMATH Keywords

eigenvalue concentrationKato-Temple inequalityperturbation theoryrandom matricesstatistical inference for graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Inequalities involving eigenvalues and eigenvectors (15A42) Random matrices (algebraic aspects) (15B52) Hypothesis testing in multivariate analysis (62H15)

Abstract: We present an adaptation of the Kato--Temple inequality for bounding perturbations of eigenvalues with applications to statistical inference for random graphs, specifically hypothesis testing and change-point detection. We obtain explicit high-probability bounds for the individual distances between certain signal eigenvalues of a graph's adjacency matrix and the corresponding eigenvalues of the model's edge probability matrix, even when the latter eigenvalues have multiplicity. Our results extend more broadly to the perturbation of singular values in the presence of quite general random matrix noise.

Recommendations

• Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices
• Unperturbed: spectral analysis beyond Davis-Kahan
• Concentration and regularization of random graphs
• CONCENTRATION OF RANDOM GRAPHS AND APPLICATION TO COMMUNITY DETECTION
• On some bounds on the perturbation of invariant subspaces of normal matrices with application to a graph connection problem

Cited in

(8)

• Tosio Kato's work on non-relativistic quantum mechanics. I
• Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices
• The Bethe Hessian and information theoretic approaches for online change-point detection in network data
• Statistical inference on random dot product graphs: a survey
• Tosio Kato's work on non-relativistic quantum mechanics. II
• Inference for multiple heterogeneous networks with a common invariant subspace
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes

This page was built for publication: The Kato-Temple inequality and eigenvalue concentration with applications to graph inference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2412262)