Fetching the paper…

Reading the bibliography…

Unperturbed: spectral analysis beyond Davis-Kahan · Around

2017

Unperturbed: spectral analysis beyond Davis-Kahan

Eldridge, Justin, Belkin, Mikhail, Wang, Yusu

Original
PDF
Post on X

Understand

Classical matrix perturbation results, such as Weyl's theorem for eigenvalues and the Davis-Kahan theorem for eigenvectors, are general purpose.

These classical bounds are tight in the worst case, but in many settings sub-optimal in the typical case.
In this paper, we present perturbation bounds which consider the nature of the perturbation and its interaction with the unperturbed structure in order to obtain significant improvements over the classical theory in many scenarios, such as when the perturbation is random.
We demonstrate the utility of these new results by analyzing perturbations in the stochastic blockmodel where we derive much tighter bounds than provided by the classical theory.

Built on

Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)
H. Weyl · 1912
Earlier work this paper cites.
Spectral statistics of Erdős-Rényi graphs i: Local semicircle law
L. Erdős, A. Knowles, H.-T. Yau, and J. Yin · 1919
Earlier work this paper cites.
Some new bounds on perturbation of subspaces
C. Davis and W. M. Kahan · 1969
Earlier work this paper cites.
Singular vectors under random perturbation
V. Vu · 2000
Earlier work this paper cites.
Spectral norm of random matrices
V. Vu · 2007
Earlier work this paper cites.

Similar

Entrywise bounds for eigenvectors of random graphs
P. Mitra · 2009
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
R. Vershynin · 2010
Cited alongside, same era.
Matrix Analysis
R. A. Horn and C. R. Johnson · 2012
Cited alongside, same era.
Random perturbation of low rank matrices: Improving classical bounds
S. O’Rourke, V. Vu, and K. Wang · 2013
Cited alongside, same era.
Angles between subspaces and their tangents
P. Zhu and A. V. Knyazev · 2013
Cited alongside, same era.

Then

A simple SVD algorithm for finding hidden partitions
V. Vu · 2014
Later among the works it cites.
A useful variant of the Davis–Kahan theorem for statisticians
Y. Yu, T. Wang, and R. J. Samworth · 2015
Later among the works it cites.
An ℓ ∞ \ell_{\infty} eigenvector perturbation bound and its application to robust covariance estimation
J. Fan, W. Wang, and Y. Zhong · 2016
Later among the works it cites.
Community detection and stochastic block models: recent developments
E. Abbe · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…