Empirical Spectral Perturbations

Why Empirical Spectra Need Their Own Stability Analysis

A spectral regularization method is often defined using eigenvalues and eigendirections of an operator. In practice, those quantities may be estimated from data. The resulting question is not only whether the empirical eigenvalues are close to the population eigenvalues. A filter also acts along eigenvectors, and those directions can change substantially even when eigenvalues barely move.

This tutorial studies that distinction for finite-dimensional positive semidefinite operators, represented by symmetric matrices. This setting includes empirical covariance and kernel matrices. The same principles apply to compact self-adjoint operators when the relevant eigenvalues are isolated. Throughout, perturbation size means operator norm, not entrywise error.

Definition: Let $T$ and $\widehat T$ be symmetric positive semidefinite matrices, with ordered eigenvalues $\mu_1\geq\cdots\geq\mu_d\geq0$ and $\widehat\mu_1\geq\cdots\geq\widehat\mu_d\geq0$. Their operator-norm discrepancy is $\delta=\|\widehat T-T\|_{\mathrm{op}}$. For a scalar filter response $h$, the corresponding spectral operator is $h(T)=\sum_{j=1}^d h(\mu_j)u_ju_j^\top$, where $u_j$ are orthonormal eigenvectors of $T$. The empirical version $h(\widehat T)$ is defined in the same way from $\widehat T$.

A filter response specifies how much a spectral component at eigenvalue $t$ is retained. For example, the Tikhonov response at regularization level $\lambda>0$ is $h_\lambda(t)=t/(t+\lambda)$. A spectral cutoff at threshold $\tau>0$ has response $h_\tau(t)=\mathbf{1}\{t\geq\tau\}$. Once the response is chosen, the actual filtered operator depends on both the eigenvalues and their eigenspaces.

Eigenvalue Error: A Bound Without a Gap Assumption

For symmetric matrices, Weyl’s eigenvalue perturbation inequality says that matching eigenvalues in decreasing order differ by at most the operator-norm discrepancy. No assumption that eigenvalues are distinct or well separated is needed.

Theorem (Weyl’s eigenvalue perturbation bound): If $T$ and $\widehat T$ are symmetric $d\times d$ matrices and $\delta=\|\widehat T-T\|_{\mathrm{op}}$, then for every $j=1,\ldots,d$, $$ |\widehat\mu_j-\mu_j|\leq\delta. $$

Proof. For a symmetric matrix $T$, the variational characterization of its $j$th largest eigenvalue is

\mu_j=\min_{\dim S=d-j+1}\ \max_{\substack{x\in S\\ \|x\|=1}}x^\top T x.

For every unit vector $x$, the definition of operator norm gives $|x^\top(\widehat T-T)x|\leq\delta$. Thus $x^\top T x-\delta\leq x^\top\widehat T x\leq x^\top T x+\delta$. Taking the maximum over unit vectors in any fixed subspace, then the minimum over subspaces of dimension $d-j+1$, gives $\mu_j-\delta\leq\widehat\mu_j\leq\mu_j+\delta$, using the variational characterization for each matrix. This proves the inequality. $\square$

Worked Example: Eigenvalue Error for a Diagonal Empirical Operator

Let $T=\operatorname{diag}(4,1)$ and $\widehat T=\operatorname{diag}(4.2,0.9)$. Their ordered eigenvalues are $(4,1)$ and $(4.2,0.9)$. The difference matrix is $\operatorname{diag}(0.2,-0.1)$, so $\delta=0.2$. The eigenvalue errors are $0.2$ and $0.1$, each at most $\delta$, as Weyl’s bound requires.

For Tikhonov regularization with $\lambda=1$, the responses at the first eigenvalue are $h_1(4)=4/5=0.8$ and $h_1(4.2)=4.2/5.2=21/26\approx0.8077$, an absolute change of about $0.0077$. At the second eigenvalue they are $h_1(1)=1/2=0.5$ and $h_1(0.9)=0.9/1.9=9/19\approx0.4737$, a change of about $0.0263$. The larger response change occurs at the smaller eigenvalue, where the Tikhonov response is steeper.

Filter-Operator Error Includes More Than Eigenvalue Error

If $T$ and $\widehat T$ share eigenvectors, a scalar response $h$ that is Lipschitz on their spectra has a simple bound: each response changes by at most its Lipschitz constant times $\delta$. But shared eigenvectors cannot generally be assumed. Even identical spectra can correspond to different eigendirections, so eigenvalue error alone does not control the difference between filtered operators.

Theorem (Tikhonov filter perturbation): For symmetric positive semidefinite $T,\widehat T$, $\lambda>0$, and $\delta=\|\widehat T-T\|_{\mathrm{op}}$, $$ \|h_\lambda(\widehat T)-h_\lambda(T)\|_{\mathrm{op}}\leq\frac{\delta}{\lambda}, \qquad h_\lambda(t)=\frac{t}{t+\lambda}. $$

Proof. The spectral theorem gives $h_\lambda(T)=I-\lambda(T+\lambda I)^{-1}$, and the same identity holds for $\widehat T$. Therefore

h_\lambda(\widehat T)-h_\lambda(T) =\lambda\big[(T+\lambda I)^{-1}-(\widehat T+\lambda I)^{-1}\big] =\lambda(T+\lambda I)^{-1}(\widehat T-T)(\widehat T+\lambda I)^{-1}.

The last equality follows by multiplying out the right-hand side. Since both matrices are positive semidefinite, every eigenvalue of $T+\lambda I$ and $\widehat T+\lambda I$ is at least $\lambda$. Hence each inverse has operator norm at most $1/\lambda$. Taking norms in the displayed identity and using $\|ABC\|_{\mathrm{op}}\leq\|A\|_{\mathrm{op}}\|B\|_{\mathrm{op}}\|C\|_{\mathrm{op}}$ yields $\|h_\lambda(\widehat T)-h_\lambda(T)\|_{\mathrm{op}}\leq\lambda(1/\lambda)\delta(1/\lambda)=\delta/\lambda$. $\square$

This bound handles eigenvalue and eigenvector changes together. It also makes the regularization level consequential: a smaller $\lambda$ permits a larger worst-case filter change for the same $\delta$. It is a bound on this particular smooth filter; one should not infer that every scalar Lipschitz response has the same operator-norm guarantee.

Worked Example: Same Spectrum, Different Tikhonov Filter

Take $T=\operatorname{diag}(2,1)$ and let $\widehat T=R_\theta T R_\theta^\top$, where $R_\theta$ is a two-dimensional rotation through $\theta=10^\circ$. The matrices have exactly the same eigenvalues, so the eigenvalue errors are zero. Their top eigenvectors, however, differ by $10^\circ$.

At $\lambda=1$, the two filter responses are $h_1(2)=2/3$ and $h_1(1)=1/2$. Thus $h_1(T)=(1/2)I+(1/6)P$, where $P$ projects onto the top eigendirection; the rotated matrix has the same expression with the rotated projector $\widehat P$. In two dimensions, $\|P-\widehat P\|_{\mathrm{op}}=\sin\theta$: in the basis of the two directions, the difference of their projection matrices has eigenvalues $\sin\theta$ and $-\sin\theta$. Consequently,

\|h_1(\widehat T)-h_1(T)\|_{\mathrm{op}} =\frac{1}{6}\sin(10^\circ)\approx0.0289.

The filter operators differ despite zero eigenvalue error. The difference arises entirely from the changed eigendirections.

Eigenvector Stability Depends on the Spectral Gap

An eigendirection is reliably identified only when its eigenvalue is separated from the rest of the spectrum. For a simple eigenvalue $\mu_j$, define its gap by $\gamma=\min_{k\ne j}|\mu_j-\mu_k|$. If this gap is small, a small perturbation can rotate the corresponding eigenvector substantially. The following elementary bound makes the dependence explicit.

Proposition (isolated eigenvector bound): Suppose $\mu_j$ is a simple eigenvalue of symmetric $T$, with gap $\gamma>0$, and $\widehat T=T+E$ is symmetric with $\delta=\|E\|_{\mathrm{op}}<\gamma/2$. Let $\widehat u_j$ be a unit eigenvector for the $j$th ordered eigenvalue of $\widehat T$, and let $u_j$ be a unit eigenvector of $T$. Then $$ \sin\angle(\widehat u_j,u_j)\leq\frac{\delta}{\gamma-\delta}, $$ where $\sin\angle(\widehat u_j,u_j)=\|(I-u_ju_j^\top)\widehat u_j\|$.

Proof. Weyl’s bound gives $|\widehat\mu_j-\mu_j|\leq\delta$. Let $P=u_ju_j^\top$ and $P^\perp=I-P$. On the range of $P^\perp$, every eigenvalue of $T$ is at distance at least $\gamma$ from $\mu_j$, so every eigenvalue there is at distance at least $\gamma-\delta$ from $\widehat\mu_j$. By the spectral theorem, $\|(T-\widehat\mu_j I)P^\perp v\|\geq(\gamma-\delta)\|P^\perp v\|$ for every vector $v$. Since $T$ commutes with $P^\perp$, and $(T+E)\widehat u_j=\widehat\mu_j\widehat u_j$, we obtain

(\gamma-\delta)\|P^\perp\widehat u_j\| \leq\|(T-\widehat\mu_j I)P^\perp\widehat u_j\| =\|P^\perp E\widehat u_j\| \leq\delta.

The leftmost norm $\|P^\perp\widehat u_j\|$ is the sine of the angle between the unit eigenvectors, which proves the result. $\square$

Worked Example: A Small Gap Allows a Large Rotation

Let $T=\operatorname{diag}(1.01,1)$, whose top-eigenvalue gap is $\gamma=0.01$. Rotate its eigenvectors by $20^\circ$ to form $\widehat T=R_{20^\circ}TR_{20^\circ}^\top$. The eigenvalues are unchanged, but the top eigenvector rotates by $20^\circ$. The difference is $0.01$ times the difference between the two rank-one projectors, so $\delta=\|\widehat T-T\|_{\mathrm{op}}=0.01\sin(20^\circ)\approx0.00342$. This is less than $\gamma/2=0.005$, as required by the proposition.

The bound is $\sin\angle(\widehat u_1,u_1)\leq0.00342/(0.01-0.00342)\approx0.52$; the actual value is $\sin(20^\circ)\approx0.342$. The bound is conservative, but correctly signals that the direction may move appreciably when the gap is small. For the Tikhonov response at $\lambda=1$, $h_1(1.01)-h_1(1)=101/201-1/2=1/402$. Thus the filtered-operator difference is only $(1/402)\sin(20^\circ)\approx0.00085$. A noticeably rotated eigenvector need not cause a large change in a smooth filter when the responses on the nearby eigenvalues are themselves close.

Why Cutoffs Require Special Care

Smooth filters can suppress the effect of nearby eigenvalues by assigning them similar responses. A hard cutoff does not: its response jumps from zero to one at the threshold. For example, take $T=\operatorname{diag}(1.001,0.5)$ and $\widehat T=\operatorname{diag}(0.999,0.5)$, with threshold $\tau=1$. Then $\|\widehat T-T\|_{\mathrm{op}}=0.002$, but the cutoff response on the first component changes from one to zero. The filter-operator difference has norm one.

This is not a failure of Weyl’s bound. Weyl correctly says the eigenvalue moved by only $0.002$. The large change comes from placing that eigenvalue on opposite sides of a discontinuity. When a cutoff is used, eigenvalues close to its threshold deserve particular scrutiny.

Common Mistake

Wrong reasoning: “The estimated eigenvalues are close, so the estimated spectral filter must be close.” This ignores that eigendirections can rotate, and that a discontinuous response can change sharply even for a tiny eigenvalue error.
Correction: Use Weyl’s bound for eigenvalue error, a gap-dependent argument for eigenvector stability, and a filter-specific operator bound when assessing the full filtered operator. For a smooth Tikhonov response, the resolvent argument gives such a bound directly. For a hard cutoff, also check how close estimated eigenvalues are to the threshold.

Key takeaway: Eigenvalue accuracy and eigendirection accuracy are distinct. Eigenvalues are controlled by operator-norm error without a gap assumption; individual eigenvectors require spectral separation. The effect on a filtered operator depends on both, as well as on how smoothly the filter response varies over the spectrum.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

If $\|\widehat T-T\|_{\mathrm{op}}=0.03$, what can Weyl’s bound guarantee about each pair of ordered eigenvalues?
Why can two matrices with identical eigenvalues have different Tikhonov filter operators?
In the isolated eigenvector bound, what happens to the upper bound as the spectral gap becomes small relative to the perturbation size?
For the Tikhonov filter, how does the bound on filter-operator error depend on $\lambda$?
Why can a hard cutoff change substantially even when the eigenvalue perturbation is small?