A Davis–Kahan Bound for Subspace Perturbations

Why a Subspace Perturbation Bound Matters

In principal component analysis, a covariance matrix determines the directions of its principal components. In practice, however, the matrix used in an analysis may be an estimate, or it may differ from a target covariance matrix because of rounding, measurement, or modeling choices. The central stability question is not merely whether the matrices are close, but whether their leading principal subspaces are close.

A leading subspace can remain stable even when individual eigenvectors are not uniquely defined, for example when eigenvalues within the leading group are repeated. The relevant comparison is therefore between subspaces, not between particular signed eigenvectors. A Davis–Kahan-style bound makes the comparison quantitative: a small matrix perturbation helps, while a small gap separating the leading eigenvalues from the rest can make the subspace sensitive.

Subspaces, Principal Angles, and the Relevant Gap

Let $A$ be a real symmetric $p\times p$ matrix with ordered eigenvalues $\lambda_1(A)\geq\cdots\geq\lambda_p(A)$. For an integer $k$ with $1\leq k<p$, the leading $k$-dimensional eigenspace is the span of eigenvectors associated with the largest $k$ eigenvalues. It is separated from the remaining eigenspaces when $\lambda_k(A)>\lambda_{k+1}(A)$. Eigenvalues within the leading group may still be repeated.

Definition: The leading eigengap at dimension $k$ is $\delta=\lambda_k(A)-\lambda_{k+1}(A)$. If $U$ and $V$ are $p\times k$ matrices with orthonormal columns spanning two $k$-dimensional subspaces, their principal angles are $\theta_1\leq\cdots\leq\theta_k$, with $\cos(\theta_j)$ equal to the singular values of $U^\mathsf{T}V$. The largest principal angle, $\theta_k$, measures the greatest directional separation between the subspaces.

Write $U_\perp$ for a matrix whose columns form an orthonormal basis for the orthogonal complement of the columns of $U$. The sines of the principal angles are the singular values of $U_\perp^\mathsf{T}V$. In particular, $\sin(\theta_k)=\|U_\perp^\mathsf{T}V\|_2$, where $\|\cdot\|_2$ is the spectral norm (largest singular value). This quantity does not depend on the choice of orthonormal bases. It also equals the spectral norm of the difference of the orthogonal projection matrices onto the two subspaces.

For a covariance matrix, the leading eigenspace describes the span of the first $k$ principal directions. If the $k$-th and $(k+1)$-st eigenvalues are close, that span may change substantially under a modest covariance perturbation. A gap within the leading group is not required: the separating gap at the boundary of the group is what matters.

A Davis–Kahan-Style Bound

Let $\widehat A=A+E$, where both $A$ and $\widehat A$ are real symmetric, so $E$ is symmetric as well. Let $U$ span the leading $k$-dimensional eigenspace of $A$, and let $V$ span a leading $k$-dimensional eigenspace of $\widehat A$. Set $\varepsilon=\|E\|_2$. The next result bounds the largest principal angle between these subspaces.

Theorem: Suppose $\delta=\lambda_k(A)-\lambda_{k+1}(A)>0$ and $\varepsilon=\|\widehat A-A\|_2<\delta$. Then $$ \sin(\theta_k)\leq \frac{\varepsilon}{\delta-\varepsilon}. $$ Here $\theta_k$ is the largest principal angle between the leading $k$-dimensional eigenspaces of $A$ and $\widehat A$. The condition $\varepsilon<\delta$ ensures that the denominator is positive; if $\varepsilon<\delta/2$, the bound is less than one and gives a nontrivial upper bound on the angle.

This is one useful Davis–Kahan-style form. It uses the original matrix’s boundary gap and allows that the perturbation can move the perturbed eigenvalues. When an eigenvalue at the boundary of the perturbed leading group is repeated, the selected leading subspace need not be unique. Under the stated condition, the bound applies to any such selection.

Deriving the Bound

Two ingredients give the result: eigenvalues move by at most the spectral norm of the perturbation, and a separated Sylvester equation has a norm-controlled solution. The eigenvalue inequality follows from the variational characterization of ordered eigenvalues. For every unit vector $x$, $|x^\mathsf{T}Ex|\leq\|E\|_2=\varepsilon$; applying this to the variational characterization gives

|\lambda_j(\widehat A)-\lambda_j(A)|\leq\varepsilon,\qquad j=1,\ldots,p.

In particular, the smallest eigenvalue among the selected leading $k$ eigenvalues of $\widehat A$ satisfies $\widehat\lambda_k\geq\lambda_k(A)-\varepsilon$. Consequently, it is separated from every eigenvalue of $A$ below the leading subspace by at least $\delta-\varepsilon>0$.

For the matrix equation used in the proof, suppose $D$ and $H$ are symmetric, every eigenvalue of $D$ is at most $a$, and every eigenvalue of $H$ is at least $b>a$. If $XH-DX=C$, then

X=\int_0^\infty e^{tD}C e^{-tH}\,dt, \qquad \|X\|_2\leq\frac{\|C\|_2}{b-a}.

To verify the representation, differentiate $e^{tD}Ce^{-tH}$. Its derivative is $D e^{tD}Ce^{-tH}-e^{tD}Ce^{-tH}H$. The integrand tends to zero in norm as $t$ tends to infinity, since $\|e^{tD}\|_2\leq e^{ta}$ and $\|e^{-tH}\|_2\leq e^{-tb}$. Integrating the derivative from zero to infinity gives $DX-XH=-C$, or $XH-DX=C$. The integral converges in norm, and

\|X\|_2 \leq\int_0^\infty e^{ta}\|C\|_2e^{-tb}\,dt =\frac{\|C\|_2}{b-a}.

Now choose orthonormal eigenvector matrices so $U$ spans the leading space of $A$, $U_\perp$ spans its orthogonal complement, and $V$ spans the leading space of $\widehat A$. Write $D=U_\perp^\mathsf{T}AU_\perp$ and $H=V^\mathsf{T}\widehat A V$. The eigenvalues of $D$ are at most $\lambda_{k+1}(A)$, and those of $H$ are at least $\widehat\lambda_k\geq\lambda_k(A)-\varepsilon$. Define $X=U_\perp^\mathsf{T}V$. Since $\widehat A V=VH$, multiplying on the left by $U_\perp^\mathsf{T}$ yields

DX+U_\perp^\mathsf{T}EV=XH, \qquad XH-DX=U_\perp^\mathsf{T}EV.

The separation between the spectra of $D$ and $H$ is at least $(\lambda_k(A)-\varepsilon)-\lambda_{k+1}(A)=\delta-\varepsilon$. Applying the integral bound, with $C=U_\perp^\mathsf{T}EV$, gives

\|U_\perp^\mathsf{T}V\|_2 \leq\frac{\|U_\perp^\mathsf{T}EV\|_2}{\delta-\varepsilon} \leq\frac{\|E\|_2}{\delta-\varepsilon}.

The last inequality uses the fact that multiplication by matrices with orthonormal columns or rows cannot increase the spectral norm. Since $\|U_\perp^\mathsf{T}V\|_2=\sin(\theta_k)$, this proves the theorem. $\square$

Worked Applications

Worked Example: A Two-Dimensional Leading Direction

Consider $A=\begin{pmatrix}5&0\\0&2\end{pmatrix}$ and $\widehat A=\begin{pmatrix}5&0.2\\0.2&2\end{pmatrix}$. The leading eigenspace is one-dimensional, so the principal angle is the absolute angle between the leading eigenvectors.

The gap is $\delta=5-2=3$. The perturbation $E=\widehat A-A=\begin{pmatrix}0&0.2\\0.2&0\end{pmatrix}$ has eigenvalues $0.2$ and $-0.2$, so $\varepsilon=\|E\|_2=0.2$. The theorem gives $\sin(\theta_1)\leq 0.2/(3-0.2)=0.0714286$.

For comparison, the leading eigenvector of a symmetric matrix $\begin{pmatrix}a&c\\c&d\end{pmatrix}$, with $a>d$, is rotated from the first coordinate axis by $\theta=\tfrac12\arctan(2c/(a-d))$. Here $\theta=\tfrac12\arctan(0.4/3)\approx0.0662758$ radians, and $\sin(\theta)\approx0.0662273$. Thus the actual sine is below the bound. The two values need not be equal: the theorem is an upper bound that uses only the perturbation norm and the gap.

Worked Example: A Two-Dimensional Leading Subspace

Let $A=\operatorname{diag}(9,6,2)$, take $k=2$, and set $\widehat A=\begin{pmatrix}9&0&0\\0&6&0.3\\0&0.3&2\end{pmatrix}$. The original leading subspace is spanned by $e_1,e_2$, and its boundary gap is $\delta=6-2=4$.

The perturbation has nonzero entries $0.3$ in the second and third coordinates. Its nonzero eigenvalues are $0.3$ and $-0.3$, so $\varepsilon=0.3$. The bound is $\sin(\theta_2)\leq0.3/(4-0.3)=0.0810811$.

The first coordinate remains an eigenvector with eigenvalue 9. In the second-and-third-coordinate block, the leading eigenvector is rotated by $\theta=\tfrac12\arctan(0.6/4)\approx0.0744450$ radians from $e_2$. Therefore the largest principal angle between the two planes is this rotation, with $\sin(\theta)\approx0.0743762$, which satisfies the stated bound.

Worked Example: Repeated Eigenvalues Within the Leading Group

Let $A=\operatorname{diag}(8,8,3)$ and $k=2$. The leading eigenspace is the plane spanned by $e_1,e_2$, even though the two leading eigenvalues are repeated. Its boundary gap is $\delta=8-3=5$. Set $\widehat A=A+E$, where $E=\begin{pmatrix}0&0&0.3\\0&0&0.4\\0.3&0.4&0\end{pmatrix}$.

The vector $q=(0.6,0.8,0)^\mathsf{T}$ is a unit vector in the original leading plane, and the perturbation couples $q$ to $e_3$ with strength $0.5$, since $(0.3,0.4)=0.5(0.6,0.8)$. The orthogonal leading-plane vector $r=(-0.8,0.6,0)^\mathsf{T}$ remains an eigenvector with eigenvalue 8. On the span of $q,e_3$, the perturbed matrix is $\begin{pmatrix}8&0.5\\0.5&3\end{pmatrix}$.

The eigenvalues of $E$ are $0.5,-0.5,0$, so $\varepsilon=0.5$, and the theorem gives $\sin(\theta_2)\leq0.5/(5-0.5)=1/9\approx0.111111$. The rotation in the $q,e_3$ plane satisfies $\theta_2=\tfrac12\arctan(1/5)\approx0.0986978$ radians, hence $\sin(\theta_2)\approx0.0985378$, below the bound. The repeated eigenvalue within the leading group causes no difficulty: the theorem concerns the plane and requires a gap only between the second and third eigenvalues.

Interpreting the Bound and Avoiding a Common Mistake

The inequality separates two sources of stability. The numerator $\varepsilon$ measures the size of the covariance perturbation in the spectral norm, so it reflects the perturbation’s largest effect on any unit direction. The denominator is controlled by the gap at the boundary of the target subspace. Holding the perturbation fixed, a larger gap gives a tighter bound; a smaller gap weakens the guarantee.

A common mistake is to conclude that a small perturbation must imply a stable leading subspace. That reasoning omits the eigengap. For instance, a perturbation that is small in absolute size may still be comparable to $\delta$, allowing the leading subspace to rotate substantially. The correction is to compare perturbation size with the boundary gap, not to interpret $\varepsilon$ in isolation. If $\varepsilon\geq\delta$, this version supplies no positive denominator and gives no stability guarantee. Even when $\varepsilon<\delta$, the displayed upper bound is informative as a number below one only when $\varepsilon<\delta/2$.

Another related mistake is to compare signed eigenvectors one by one, especially when eigenvalues within the leading group are repeated or nearly repeated. Individual eigenvectors can change through sign choices or rotations within the same subspace. The principal-angle comparison avoids that ambiguity and measures the change in the span itself. This makes the bound useful when assessing the stability of PCA summaries based on a group of leading components.

Key takeaway: For a symmetric covariance matrix with boundary eigengap $\delta>0$, a symmetric perturbation of spectral norm $\varepsilon<\delta$ changes the leading $k$-dimensional subspace by at most $\varepsilon/(\delta-\varepsilon)$ in the sine of its largest principal angle. Stability depends jointly on perturbation size and eigengap.

Check Your Understanding

Use the definitions and theorem above to answer the following.

Which eigengap is relevant to the leading $k$-dimensional subspace, and why is a gap among the first $k$ eigenvalues not required?
If $\delta=2$ and $\|\widehat A-A\|_2=0.2$, what upper bound does the theorem give for the sine of the largest principal angle?
What condition on $\varepsilon$ and $\delta$ makes the displayed bound less than one?
Why is a principal-angle comparison preferable to comparing individual signed eigenvectors when the leading eigenvalues are repeated?
For the three-dimensional example with $A=\operatorname{diag}(8,8,3)$, identify the boundary gap and perturbation norm, and state the resulting bound.