A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation
Abstract
The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.
Related
- A Frame-Spread Lower Bound for Quantum Entropy Estimation under Fixed Rank-One Measurements
- SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
- Subsampled Pseudo-posteriors for Scalable Bayesian Moment-condition Inference
- On the Orlicz function estimations of the a-Davis--Wielandt radius in C*-algebra
- Latent Score-Based Bayesian Cramér-Rao Bound Estimation for High-Dimensional Imaging Systems
BibTeX
@misc{qing2026subsampled,
title = {{A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation}},
author = {Huan Qing},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09211},
eprint = {2609.09211},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09211},
}
RIS
TY - UNPB
TI - A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation
AU - Huan Qing
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.09211
UR - https://arxiv.org/abs/2609.09211
AB - The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.
ER -