Improved dependence on coherence in eigenvector and eigenvalue estimation error bounds

Hao Yan, Keith Levin
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1549-1557, 2025.

Abstract

Spectral estimators are fundamental in low-rank matrix models and arise throughout machine learning and statistics, with applications including network analysis, matrix completion and PCA. These estimators aim to recover the leading eigenvalues and eigenvectors of an unknown signal matrix observed subject to noise. While extensive research has addressed the statistical accuracy of spectral estimators under a variety of conditions, most previous work has assumed that the signal eigenvectors are incoherent with respect to the standard basis. This assumption typically arises because of suboptimal dependence on coherence in one or more concentration inequalities. Using a new matrix concentration result that may be of independent interest, we establish estimation error bounds for eigenvector and eigenvalue recovery whose dependence on coherence significantly improves upon prior work. Our results imply that coherence-free bounds can be achieved when the standard deviation of the noise is comparable to its Orlicz 1-norm (i.e., its subexponential norm). This matches known minimax lower bounds under Gaussian noise up to logarithmic factors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-yan25a, title = {Improved dependence on coherence in eigenvector and eigenvalue estimation error bounds}, author = {Yan, Hao and Levin, Keith}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {1549--1557}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/yan25a/yan25a.pdf}, url = {https://proceedings.mlr.press/v258/yan25a.html}, abstract = {Spectral estimators are fundamental in low-rank matrix models and arise throughout machine learning and statistics, with applications including network analysis, matrix completion and PCA. These estimators aim to recover the leading eigenvalues and eigenvectors of an unknown signal matrix observed subject to noise. While extensive research has addressed the statistical accuracy of spectral estimators under a variety of conditions, most previous work has assumed that the signal eigenvectors are incoherent with respect to the standard basis. This assumption typically arises because of suboptimal dependence on coherence in one or more concentration inequalities. Using a new matrix concentration result that may be of independent interest, we establish estimation error bounds for eigenvector and eigenvalue recovery whose dependence on coherence significantly improves upon prior work. Our results imply that coherence-free bounds can be achieved when the standard deviation of the noise is comparable to its Orlicz 1-norm (i.e., its subexponential norm). This matches known minimax lower bounds under Gaussian noise up to logarithmic factors.} }
Endnote
%0 Conference Paper %T Improved dependence on coherence in eigenvector and eigenvalue estimation error bounds %A Hao Yan %A Keith Levin %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-yan25a %I PMLR %P 1549--1557 %U https://proceedings.mlr.press/v258/yan25a.html %V 258 %X Spectral estimators are fundamental in low-rank matrix models and arise throughout machine learning and statistics, with applications including network analysis, matrix completion and PCA. These estimators aim to recover the leading eigenvalues and eigenvectors of an unknown signal matrix observed subject to noise. While extensive research has addressed the statistical accuracy of spectral estimators under a variety of conditions, most previous work has assumed that the signal eigenvectors are incoherent with respect to the standard basis. This assumption typically arises because of suboptimal dependence on coherence in one or more concentration inequalities. Using a new matrix concentration result that may be of independent interest, we establish estimation error bounds for eigenvector and eigenvalue recovery whose dependence on coherence significantly improves upon prior work. Our results imply that coherence-free bounds can be achieved when the standard deviation of the noise is comparable to its Orlicz 1-norm (i.e., its subexponential norm). This matches known minimax lower bounds under Gaussian noise up to logarithmic factors.
APA
Yan, H. & Levin, K.. (2025). Improved dependence on coherence in eigenvector and eigenvalue estimation error bounds. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1549-1557 Available from https://proceedings.mlr.press/v258/yan25a.html.

Related Material