mlsanityData to 7 Oct 2026

A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

arXiv 2609.09211 ↗First posted 6 Sep 2026stat.ML cs.LG stat.MEcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 15 of its 37 references that are in the map. First posted on arXiv 6 Sep 2026.

Builds on

15 of 37 references.

References · 15

  1. 2013Consistency of spectral clustering in stochastic block modelscited by 128
  2. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  3. 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
  4. 2013Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodelcited by 45
  5. 2014Covariate-assisted spectral clusteringcited by 29
  6. 2017Spectral and matrix factorization methods for consistent community detection in multi-layer networkscited by 27
  7. 2013Impact of regularization on Spectral Clusteringcited by 25
  8. 2019A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outlierscited by 9
  9. 2020Randomized Spectral Clustering in Large-Scale Stochastic Block Modelscited by 9
  10. 2020Regularized spectral methods for clustering signed networkscited by 9
  11. 2021Subsampling Spectral Clustering for Large-Scale Social Networkscited by 4
  12. 2024Community detection by spectral methods in multi-layer networkscited by 3
3 more
  1. 2025A Unified Framework for Community Detection and Model Selection in Blockmodelscited by 2
  2. 2022Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCAcited by 1
  3. 2023Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embeddingcited by 1

Built on by

Not cited yet.