Unperturbed: spectral analysis beyond Davis-Kahan

Justin Eldridge, Mikhail Belkin, Yusu Wang
Proceedings of Algorithmic Learning Theory, PMLR 83:321-358, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-eldridge18a, title = {Unperturbed: spectral analysis beyond Davis-Kahan}, author = {Eldridge, Justin and Belkin, Mikhail and Wang, Yusu}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {321--358}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/eldridge18a/eldridge18a.pdf}, url = {https://proceedings.mlr.press/v83/eldridge18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Unperturbed: spectral analysis beyond Davis-Kahan %A Justin Eldridge %A Mikhail Belkin %A Yusu Wang %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-eldridge18a %I PMLR %P 321--358 %U https://proceedings.mlr.press/v83/eldridge18a.html %V 83 %X 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.
APA
Eldridge, J., Belkin, M. & Wang, Y.. (2018). Unperturbed: spectral analysis beyond Davis-Kahan. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:321-358 Available from https://proceedings.mlr.press/v83/eldridge18a.html.

Related Material