PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Huan Qing

arXiv:2609.09211v1stat.MLcs.LGstat.ME

TL;DR

Large symmetric matrices make leading-eigenvector computation expensive, while column subsampling creates a rectangular problem outside the direct scope of classical Davis–Kahan theory. The paper introduces Bernoulli column sampling and a subsampled Davis–Kahan bound for estimating the target eigenspace from leading left singular vectors. The bound quantifies an explicit trade-off: subsampling reduces expected computational cost by α while inflating Frobenius-norm subspace error by 1/√α.

  • Problem

    Computing leading eigenvectors of large symmetric matrices is expensive, and column subsampling creates a rectangular matrix to which symmetric-matrix Davis–Kahan results do not directly apply.

  • Method

    The paper independently retains columns with Bernoulli probability α and uses the leading left singular vectors of the resulting matrix to estimate the low-rank target eigenspace.

  • Results

    Subsampling inflates Frobenius-norm subspace estimation error by 1/√α while reducing expected computational cost by α.

  • Takeaways & Limitations

    The theorem provides a quantitative accuracy–cost trade-off for large-scale spectral analysis of symmetric low-rank signals.

  • Takeaways & Limitations

    Prior randomized spectral guarantees motivating this work are model-specific and cannot be extended directly to other matrix types or general column subsampling.

Abstract

from arXiv · show

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.

1. Introduction

Classical Davis–Kahan analyses support spectral methods but do not directly address the computational cost of eigendecomposition or the rectangular matrices created by column subsampling. This paper develops a subsampled framework that estimates a low-rank symmetric matrix’s leading eigenspace from sampled columns and quantifies the resulting accuracy–cost trade-off.

  • Motivation: O(dp^2) operations are required for full eigendecomposition even when the target rank d is much smaller than p.This makes leading-eigenvector computation quickly infeasible for large matrices.
  • Limitations of prior work: Existing randomized spectral methods have model-specific error analyses that do not extend to other matrix classes or general column subsampling.Their guarantees rely on quantities particular to SBM or related variants.
  • Problem: Column subsampling breaks symmetry by producing a rectangular matrix, so symmetric-matrix Davis–Kahan results do not directly govern its singular vectors.The resulting cross-type comparison requires a new perturbation framework.
  • Approach: The paper estimates the leading eigenspace of a low-rank symmetric matrix using leading left singular vectors of a column-subsampled rectangular matrix.Columns are retained independently with probability α, and the sampled matrix is denoted H.
  • Main result: The subsampled Davis–Kahan bound controls Frobenius-norm subspace error using the sampling probability, noise level, and spectral gap without imposing a generative model.It applies to any symmetric matrix in the stated setting.
  • Trade-off: Statistical error grows as the inverse square root of the sampling probability while computational cost decreases proportionally to that probability.The result makes the accuracy–computation trade-off explicit for large-scale spectral analysis.

2. Problem Formulation

The paper studies estimating a low-rank symmetric matrix’s leading eigenspace when full eigendecomposition is computationally prohibitive. It subsamples columns independently and estimates the target subspace from the retained matrix’s leading left singular vectors.

  • The target is the d-dimensional eigenspace of a noiseless low-rank symmetric matrix Σ, estimated from a noisy symmetric observation.
  • Computing leading eigenvectors of a p×p symmetric matrix costs O(dp^2), which is prohibitive when p is large.
  • Independent Bernoulli sampling retains each column with probability α, forming a column-selection matrix S and subsampled matrix H.
  • The estimator uses H’s leading d left singular vectors to approximate the leading eigenvectors of Σ.
  • The expected total complexity is O(αdp^2), compared with O(dp^2) for the full-matrix approach.
  • The paper establishes a non-asymptotic Frobenius-norm bound for the subspace distance, explicitly showing how approximation error depends on α.

3. Main Results

The main theorem combines sampling, subspace-preservation, and perturbation lemmas to give an explicit probabilistic error bound for the subsampled eigenspace estimator. It quantifies the computational-statistical trade-off and identifies conditions for reliable recovery.

  • The analysis requires enough sampled columns for the estimator to be well-defined and for sampled columns to preserve the target d-dimensional structure.
  • Theorem 3.4 gives an explicit high-probability bound for the Frobenius distance between the target eigenspace and the subsampled estimator.
  • When α=1, the theorem recovers the classical Davis–Kahan bound without additional noise assumptions.
  • For 0<α<1, subsampling inflates the eigenspace error by 1/√α.
  • The sampling condition becomes restrictive mainly when d is nearly as large as p, while fixed-d and many sublinear-rank regimes satisfy it.
  • Using a weaker sampling constant lowers the required sampling rate but weakens the probability guarantee.

Chernoff bound gives P(σd(V⊤S ) ≥√

The sampling condition balances preservation of the target subspace against control of perturbation by noise. A smaller constant can reduce sampling requirements, but only with a weaker probability guarantee.

  • The theorem remains valid under a weaker condition, but the probability guarantee changes to 1−p^-d−dp^-1.
  • Replacing constant 16 with 8 lowers the sampling rate at the cost of a weaker probability guarantee.
  • Unlike classical Davis–Kahan comparisons, the theorem directly compares eigenvectors of a symmetric matrix with left singular vectors of a rectangular subsampled matrix.
  • The sampling condition ensures the sampled signal preserves the target subspace and keeps noise from overwhelming the reduced sample.
  • Under the sampling condition, the subsampled signal’s column space coincides with span(V), enabling perturbation analysis for the estimator.

4. Practical Implications

The subsampled theorem can replace full eigenspace computation in downstream spectral procedures while preserving subspace-error control. In stochastic block models, this yields a column-subsampled spectral clustering procedure with reduced computational cost.

  • The result applies to spectral procedures including PCA, matrix denoising, tensor completion, spectral clustering, and community detection.
  • Theorem 3.4 reduces eigenspace-computation complexity from O(dp^2) to O(αdp^2) while leaving downstream tasks unchanged.
  • The acceleration factor is 1/α, so smaller sampling probabilities provide faster computation at the cost of greater subspace error.
  • In the SBM application, the method samples adjacency-matrix columns, computes leading left singular vectors, and applies k-means to their rows.
  • The SBM guarantee assumes O(1) communities, balanced communities, and a smallest absolute population eigenvalue bounded below by a constant.
  • For dense networks, the subsampled method achieves vanishing misclustering at O(log^-ε p) with expected cost O(p log^(1+ε) p), versus O(p^2) for the full method.

5. Numerical Experiments

The experiments evaluate CSSC against standard spectral clustering across network sizes and sparsity levels, measuring misclustering error and subspace-estimation time. Subsampling preserves near-zero error while substantially reducing computation, especially for large or dense networks.

  • Experimental setup: The experiments average misclustering rates and running times over 100 repetitions using identical power-iteration settings, excluding k-means post-processing from timing.SC uses the full matrix, whereas CSSC constructs a column-subsampled matrix before extracting top-d left singular vectors.
  • Experiment 1: Increasing network size: CSSC's misclustering error vanishes as p increases and remains very small, whereas SC achieves exactly zero error for all tested network sizes.These results indicate that column subsampling maintains high accuracy in the dense regime.
  • Experiment 1: Increasing network size: At p = 50000, CSSC keeps subspace-estimation time below 2 seconds while SC becomes increasingly slower as network size grows.The speed-up factor grows with network size, while CSSC's error remains very small and vanishes as p increases.
  • Experiment 2: Increasing sparsity: For ρ ≥ 0.2, CSSC's error becomes negligible and reaches zero around ρ = 0.5, while SC has zero error throughout.At ρ = 0.1, slightly below the theoretical threshold, CSSC shows noticeable error.
  • Experiment 2: Increasing sparsity: At p = 50000, CSSC remains below 5 seconds across sparsity levels, while SC approaches 250 seconds at ρ = 1.The runtime gap widens in denser networks because SC scales with edge count, whereas CSSC operates on a much smaller matrix.

6. Conclusion

The conclusion presents a subsampled Davis–Kahan theorem that directly relates the target eigenspace of a symmetric matrix to left singular vectors from a column-subsampled matrix. It identifies an explicit computational–statistical trade-off and reports accurate, faster spectral clustering under the stochastic block model.

  • 6. Conclusion: The theorem directly bounds the distance between the original symmetric matrix's eigenvectors and the left singular vectors of its rectangular subsampled matrix.This differs from prior results comparing eigenvectors of two symmetric matrices.
  • 6. Conclusion: Subsampling with probability α inflates Frobenius-norm subspace error by 1/√α while reducing expected computational cost by α.This trade-off holds uniformly for symmetric low-rank signals under an explicit sampling-probability condition.
  • 6. Conclusion: The framework applies broadly to spectral methods that extract a leading eigenspace from a symmetric data matrix.The conclusion characterizes the method as a scalable extension of Davis–Kahan analysis for large-scale spectral computation.
  • 6. Conclusion: Under the stochastic block model, subsampled spectral clustering achieves a vanishing misclustering rate at substantially reduced computational cost compared with full spectral clustering.Numerical experiments support these theoretical findings.

Appendix A.1. Proof of Lemma 3.1

The proof uses a scalar Chernoff lower-tail bound to show that the number of sampled columns is at least the eigenspace dimension with high probability. It derives the result by selecting a deviation parameter satisfying the required range.

  • Appendix A.1. Proof of Lemma 3.1: The proof applies a Chernoff lower-tail bound to n ∼ Binomial(p, α) after establishing pα ≥ 16d log p.The sampling condition ensures the expected number of sampled columns is sufficiently larger than d.
  • Appendix A.1. Proof of Lemma 3.1: Setting (1 − τ)pα = d gives τ = 1 − d/(pα), and the sampling condition implies τ ∈ (1/2, 1).This places τ in the interval required by the Chernoff inequality.
  • Appendix A.1. Proof of Lemma 3.1: The resulting lower-tail probability bound controls the event n < d and completes the lemma's proof.The proof identifies {n < d} as a subset of the corresponding Chernoff deviation event.

Appendix A.2. Proof of Lemma 3.2

The proof establishes full rank and a lower bound for the sampled representation of the target eigenspace using a matrix Chernoff inequality. It expresses the relevant Gram matrix as a sum of independent positive semidefinite rank-one terms.

  • Appendix A.2. Proof of Lemma 3.2: For α = 1, S = I_p deterministically and σ_d(VᵀS) = 1; for 0 < α < 1, the proof analyzes Bernoulli-selected basis contributions.The selected terms are independent rank-one positive semidefinite matrices.
  • Appendix A.2. Proof of Lemma 3.2: The expected summand matrix has minimum eigenvalue α, and substituting t = 1/2 into matrix Chernoff yields the required lower-tail control.The proof verifies the summand eigenvalue bound before invoking the inequality.
  • Appendix A.2. Proof of Lemma 3.2: Writing Y = (VᵀS)(VᵀS)ᵀ, the proof shows that λ_min(Y) = σ_d(VᵀS)^2 and uses matrix Chernoff to control this quantity.Positive definiteness of Y implies rank(VᵀS) = d, so the sampled representation retains full eigenspace rank.
  • Appendix A.2. Proof of Lemma 3.2: Because VᵀS has d rows and full rank, the argument also establishes n ≥ d whenever the controlled positive-definiteness event occurs.The rank identity connects the sampled column count to the smallest singular value.

Appendix A.3. Proof of Lemma 3.3

The proof establishes the subsampled eigenspace bound by combining singular-value perturbation control, subspace alignment, and separate treatment of full and partial sampling.

  • Perturbation bound: Wedin’s generalized sin θ theorem converts residual bounds for the sampled matrix into a Frobenius-norm bound between its leading left singular subspace and the target subspace.The argument verifies the required spectral-gap condition before applying Wedin’s theorem and then uses the CS decomposition to align the bases.
  • Full-sampling case: For full sampling, S=I_p and the proof reduces directly to the classical Davis–Kahan theorem with constant 2.No probabilistic argument or upper bound on the perturbation norm is required beyond the assumption δ>0 in this case.
  • Signal conditioning: The sampled signal matrix B retains rank d because V^⊤S has full row rank, while its smallest nonzero singular value is lower-bounded through a Gram-matrix argument.The proof uses Weyl monotonicity and the lower bound δ on the nonzero eigenvalues of the signal matrix.
  • Subspace alignment: The column space of B equals the column space of V, so the leading left singular vectors of B differ from V only by an orthogonal change of basis.Full row rank of Λ(V^⊤S) gives both inclusions needed for span(B)=span(V).
  • SBM application: In the stochastic block model application, α ≥ C log p/(ρp) is sufficient for the theorem, and the resulting eigenspace error controls the misclustering rate.The argument uses d=O(1), δ ≍ ρp, and a noise spectral-norm bound before invoking the misclustering result.
Loading 2609.09211v1…