zbMATH — the first resource for mathematics

The Kato-Temple inequality and eigenvalue concentration with applications to graph inference. (English) Zbl 1403.15011
Summary: 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.

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