Davis-Kahan Bounds for Sample Eigenspaces

Why a Finite-Sample Eigenspace Bound Matters

A sample covariance matrix is a random perturbation of the population covariance matrix. Even when individual sample eigenvectors are unstable near repeated eigenvalues, a separated group of population eigenvalues can define a stable subspace. The Davis–Kahan bound makes this stability quantitative: it relates the angle between the population and sample subspaces to the size of the covariance perturbation and the spectral separation around the subspace.

Here the goal is a finite-sample statement. Once a covariance estimate and a bound on its error are available, the result gives a deterministic bound on the subspace angle. It does not require an asymptotic approximation or a probability model for the error. To use it, one must identify exactly which spectral separation is positive; a population eigengap condition and a realized sample-to-population separation condition are related, but they are not interchangeable.

Subspace Angles and the Covariance Perturbation

Let \(\Sigma\) be a real symmetric \(p\times p\) population covariance matrix, and let \(S\) be a real symmetric estimate of it. Write their eigenvalues in decreasing order: \(\lambda_1(\Sigma)\ge\cdots\ge\lambda_p(\Sigma)\) and \(\widehat\lambda_1\ge\cdots\ge\widehat\lambda_p\). For a chosen dimension \(k<p\), let \(U_1\) contain orthonormal eigenvectors for the leading \(k\)-dimensional population subspace, and let \(U_2\) contain an orthonormal basis for its orthogonal complement. Define \(V_1\) similarly for a selected leading \(k\)-dimensional invariant subspace of \(S\). If the eigenvalue at the boundary is tied, a leading subspace need not be unique; the bounds below apply to any such choice.

The operator norm is \(\|A\|_2=\sup_{\|x\|_2=1}\|Ax\|_2\). Set \(E=S-\Sigma\) and \(\varepsilon=\|E\|_2\). The relevant population boundary gap is \(\delta=\lambda_k(\Sigma)-\lambda_{k+1}(\Sigma)\). A positive \(\delta\) makes the population leading \(k\)-dimensional subspace uniquely defined, even if eigenvalues within that group are repeated.

A Davis–Kahan Bound Using Realized Separation

A useful form of the perturbation bound uses the distance between the selected sample eigenvalues and the population eigenvalues on the other side of the boundary. It can apply even when the simpler population-gap condition below cannot be verified.

Proof. Let \(\Lambda_2\) be the diagonal matrix of the eigenvalues of \(\Sigma\) on the complement spanned by \(U_2\), and let \(\widehat\Lambda_1\) be the diagonal matrix of the selected eigenvalues of \(S\). Put \(X=U_2^{\mathsf T}V_1\) and \(R=U_2^{\mathsf T}EV_1\). The eigenvector equations give \[ SV_1=V_1\widehat\Lambda_1,\qquad U_2^{\mathsf T}\Sigma=\Lambda_2U_2^{\mathsf T}. \] Multiplying the first equation on the left by \(U_2^{\mathsf T}\), and using \(S=\Sigma+E\), yields \[ X\widehat\Lambda_1-\Lambda_2X=R. \] Every eigenvalue of \(\widehat\Lambda_1\) is at least \(\widehat\lambda_k\), and every eigenvalue of \(\Lambda_2\) is at most \(\lambda_{k+1}(\Sigma)\). Thus their spectra are separated by at least \(\gamma>0\).

For \(t\ge0\), the matrix exponential norm bounds give \[ \|e^{t\Lambda_2}Re^{-t\widehat\Lambda_1}\|_2 \le e^{t\lambda_{k+1}(\Sigma)}\|R\|_2e^{-t\widehat\lambda_k} =e^{-t\gamma}\|R\|_2. \] Consequently the integral \[ X_*=\int_0^\infty e^{t\Lambda_2}Re^{-t\widehat\Lambda_1}\,dt \] converges in operator norm and satisfies \(\|X_*\|_2\le\|R\|_2/\gamma\). Differentiating the integrand and integrating from zero to infinity shows that \(\Lambda_2X_*-X_*\widehat\Lambda_1=-R\), or equivalently \(X_*\widehat\Lambda_1-\Lambda_2X_*=R\). The Sylvester equation has a unique solution when the two spectra are disjoint, so \(X=X_*\). Finally, orthonormality implies \(\|R\|_2\le\|E\|_2\), and the definition of the largest principal angle gives \[ \|\sin\Theta(U_1,V_1)\|_2=\|X\|_2\le\frac{\|E\|_2}{\gamma}. \] This proves the stated bound. \(\square\)

A Bound From the Population Eigengap

The theorem’s separation condition can be guaranteed using only a population eigengap and the perturbation size. Weyl’s eigenvalue inequality for symmetric matrices states that \(|\widehat\lambda_j-\lambda_j(\Sigma)|\le\|S-\Sigma\|_2\) for every \(j\). In particular, \(\widehat\lambda_k\ge\lambda_k(\Sigma)-\varepsilon\). Therefore \(\widehat\lambda_k-\lambda_{k+1}(\Sigma)\ge\delta-\varepsilon\).

This follows by substituting the lower bound \(\delta-\varepsilon>0\) for the denominator in the separated-spectrum theorem. The corollary is convenient when the population gap and a perturbation bound are known, but it can be conservative: the realized denominator \(\widehat\lambda_k-\lambda_{k+1}(\Sigma)\) may be positive even when \(\delta-\varepsilon\) is not.

Worked Applications

Interpretation and a Common Pitfall

The bound separates two ingredients. The numerator measures how much the covariance matrix changed in operator norm; the denominator measures the spectral separation needed to keep the chosen subspace distinct from its complement. A smaller perturbation or a larger separating gap gives a stronger guarantee. If the denominator is small, the bound may be weak even if the observed eigenspace happens to be close to the population one.

Common pitfall: It is incorrect to conclude that the realized-separation theorem fails merely because \(\varepsilon\ge\delta\). That inequality only prevents use of the population-gap corollary, whose denominator \(\delta-\varepsilon\) must be positive. The correct check for the more general theorem is whether \(\widehat\lambda_k>\lambda_{k+1}(\Sigma)\). Conversely, a positive population gap alone does not justify the corollary unless the perturbation is smaller than that gap.

These are deterministic bounds. In statistical applications, sampling theory can provide a probabilistic bound on \(\|S-\Sigma\|_2\); substituting such a bound then yields a probabilistic statement about the subspace angle. The finite-sample inequality itself does not supply that probability calculation.