Eigenvalue Decay and Variance Profiles

Why Eigenvalue Decay Shapes Variance

A spectral filter acts differently on different eigen-directions. For Tikhonov regularization, directions with eigenvalues much larger than the regularization parameter are passed relatively strongly, while directions with eigenvalues much smaller than it are suppressed. The trace variance adds up the contributions of all these directions. Its size therefore depends not only on the filter, but also on how quickly the eigenvalues decay.

Two questions should be kept separate. The first is how large the total variance is. The second is how many directions have a substantial filter response. Polynomial decay typically leaves a power-law number of active directions; exponential decay leaves only a logarithmic number. But an active-direction count is not itself a trace-variance calculation: the variance contribution of each direction also matters.

Trace Variance for a Tikhonov Filter

Definition: Let $(\mu_j)_{j\geq 1}$ be a nonincreasing sequence of positive eigenvalues, counted with multiplicity, and let $\lambda>0$. The Tikhonov filter is $g_\lambda(\mu)=1/(\mu+\lambda)$. For noise variance $\sigma^2$ and sample size $n$, its trace variance is $$ V(\lambda)=\frac{\sigma^2}{n}\sum_{j\geq 1}\mu_j g_\lambda(\mu_j)^2 =\frac{\sigma^2}{n}\sum_{j\geq 1}\frac{\mu_j}{(\mu_j+\lambda)^2}. $$ The summand $v_j(\lambda)=\mu_j/(\mu_j+\lambda)^2$ is the variance contribution of direction $j$, before multiplication by $\sigma^2/n$.

All sums here include multiplicities. If the spectrum is infinite, boundedness and convergence of $\mu_j$ to zero alone do not guarantee a finite trace variance. For bounded eigenvalues, the Tikhonov sum is finite exactly when $\sum_j\mu_j$ is finite: if $\mu_j\leq M$, then $$ \frac{\mu_j}{(M+\lambda)^2} \leq \frac{\mu_j}{(\mu_j+\lambda)^2} \leq \frac{\mu_j}{\lambda^2}. $$ In particular, the decay regimes treated below have finite sums. This finiteness condition matters: a sequence can be bounded and tend to zero while its eigenvalues are not summable.

It is also useful to track the squared filter response $$ D(\lambda)=\sum_{j\geq 1}\left(\frac{\mu_j}{\mu_j+\lambda}\right)^2. $$ This squared-response effective-dimension quantity, denoted $D(\lambda)$, counts directions according to their squared response, rather than adding the Tikhonov trace-variance contributions. The conventional ridge effective dimension often instead uses the unsquared response, $\sum_{j\geq 1}\mu_j/(\mu_j+\lambda)$. The distinction will be important in the examples and asymptotic results.

Worked Example: Computing Contributions Around the Threshold

Take $\mu_j=j^{-2}$, $\lambda=1/16$, and set $\sigma^2/n=1$ to focus on the spectral sum. The threshold $\mu_j\approx\lambda$ occurs at $j\approx4$, since $\mu_4=1/16$. For $j=1,2,4,8$, the variance contributions are $$ v_j(\lambda)=\frac{\mu_j}{(\mu_j+1/16)^2}. $$ For $j=1$, this is $1/(17/16)^2=256/289\approx0.886$. For $j=2$, it is $(1/4)/(5/16)^2=64/25=2.56$. For $j=4$, it is $(1/16)/(1/8)^2=4$. For $j=8$, it is $(1/64)/(5/64)^2=64/25=2.56$.

The direction at the threshold contributes more than either of the two displayed directions well above and below it. This illustrates why simply counting eigenvalues above $\lambda$ cannot give the trace variance: the summands vary with the eigenvalues as well as with the filter response.

Polynomial Eigenvalue Decay

Assume that for some $\alpha>1$ and constants $c_1,c_2>0$, $$ c_1j^{-\alpha}\leq\mu_j\leq c_2j^{-\alpha},\qquad j\geq1. $$ The condition $\alpha>1$ ensures $\sum_j\mu_j<\infty$, so the trace variance is finite for each fixed $\lambda>0$. The index at which $\mu_j$ is of order $\lambda$ is $$ J_\lambda\asymp\lambda^{-1/\alpha}. $$ Here and below, $a(\lambda)\asymp b(\lambda)$ means that their ratio is bounded above and below by positive constants for all sufficiently small positive $\lambda$.

Theorem: Under the polynomial-decay bounds above, as $\lambda$ decreases to zero, $$ \sum_{j\geq1}\frac{\mu_j}{(\mu_j+\lambda)^2} \asymp\lambda^{-1-1/\alpha}, \qquad D(\lambda)\asymp\lambda^{-1/\alpha}. $$ The first relation describes total spectral trace variance, apart from the factor $\sigma^2/n$; the second describes the effective number of responding directions.

Proof. Write $J=\lfloor\lambda^{-1/\alpha}\rfloor$. For sufficiently small $\lambda$, $J\asymp\lambda^{-1/\alpha}$. Split the trace-variance sum at $J$. For $j\leq J$, use $\mu_j/(\mu_j+\lambda)^2\leq1/\mu_j$. The lower polynomial bound on $\mu_j$ gives $$ \sum_{j\leq J}\frac{\mu_j}{(\mu_j+\lambda)^2} \leq c_1^{-1}\sum_{j\leq J}j^\alpha \leq C J^{\alpha+1}. $$ For $j>J$, use $\mu_j/(\mu_j+\lambda)^2\leq\mu_j/\lambda^2$. Since $\alpha>1$, comparison with the integral of $x^{-\alpha}$ gives $$ \sum_{j>J}\frac{\mu_j}{(\mu_j+\lambda)^2} \leq \frac{c_2}{\lambda^2}\sum_{j>J}j^{-\alpha} \leq C\lambda^{-2}J^{1-\alpha}. $$ Both bounds are $O(\lambda^{-1-1/\alpha})$, because $J\asymp\lambda^{-1/\alpha}$.

For a matching lower bound, consider the indices $J\leq j\leq2J$. Throughout this block the polynomial bounds imply that $\mu_j$ is bounded above and below by positive constant multiples of $\lambda$. Thus each summand $\mu_j/(\mu_j+\lambda)^2$ is at least $c/\lambda$ for a constant $c>0$. There are at least a constant multiple of $J$ such indices, so the block contributes at least $c'J/\lambda\asymp\lambda^{-1-1/\alpha}$. This proves the trace-variance relation.

For $D(\lambda)$, each term is at most $1$, so the first $J$ terms sum to at most $J$. For $j>J$, $$ \left(\frac{\mu_j}{\mu_j+\lambda}\right)^2 \leq \frac{\mu_j^2}{\lambda^2} \leq \frac{c_2^2j^{-2\alpha}}{\lambda^2}. $$ The resulting tail is $O(\lambda^{-2}J^{1-2\alpha})=O(J)$. For the lower bound, on $J\leq j\leq2J$, $\mu_j/\lambda$ is bounded below by a positive constant. Each squared response is consequently bounded below by a positive constant, and the block has order $J$ terms. Hence $D(\lambda)\asymp J\asymp\lambda^{-1/\alpha}$. $\square$

Worked Example: Reading the Polynomial Rate

Suppose $\mu_j=j^{-2}$, so $\alpha=2$. The theorem gives $$ J_\lambda\asymp\lambda^{-1/2},\qquad D(\lambda)\asymp\lambda^{-1/2},\qquad V(\lambda)\asymp\frac{\sigma^2}{n}\lambda^{-3/2}. $$ At $\lambda=10^{-4}$, the threshold index is about $100$, and the effective-dimension scale is about $100$. The trace-variance scale, excluding its unknown constant, is $(\sigma^2/n)(10^{-4})^{-3/2}=10^6\sigma^2/n$.

The exponent $3/2$ is not the effective-dimension exponent: it comes from the additional factor in the trace-variance summand. Reporting $D(\lambda)$ as though it were the trace variance would miss this distinction.

Exponential Eigenvalue Decay

Now suppose that for constants $a,c_1,c_2>0$, $$ c_1e^{-aj}\leq\mu_j\leq c_2e^{-aj},\qquad j\geq1. $$ Solving $e^{-aj}\approx\lambda$ gives a threshold index of logarithmic order: $$ J_\lambda\asymp\log(1/\lambda). $$ Unlike the polynomial case, only logarithmically many eigenvalues are at or above the regularization scale.

Theorem: Under the exponential-decay bounds above, as $\lambda$ decreases to zero, $$ \sum_{j\geq1}\frac{\mu_j}{(\mu_j+\lambda)^2} \asymp\lambda^{-1}, \qquad D(\lambda)\asymp\log(1/\lambda). $$

Proof. Choose an integer $J$ of order $\log(1/\lambda)$ so that $e^{-aJ}$ is of order $\lambda$. For $j\leq J$, the summand is at most $1/\mu_j$. By the lower exponential bound, $$ \sum_{j\leq J}\frac{\mu_j}{(\mu_j+\lambda)^2} \leq \sum_{j\leq J}\frac{1}{\mu_j} \leq c_1^{-1}\sum_{j\leq J}e^{aj} \leq C e^{aJ} =O(\lambda^{-1}). $$ For $j>J$, bound the summand by $\mu_j/\lambda^2$. The upper exponential bound and the geometric-series formula yield $$ \sum_{j>J}\frac{\mu_j}{(\mu_j+\lambda)^2} \leq \frac{c_2}{\lambda^2}\sum_{j>J}e^{-aj} \leq C\lambda^{-2}e^{-aJ} =O(\lambda^{-1}). $$ For a lower bound, choose an index within a fixed integer distance of the threshold where $\mu_j$ is bounded above and below by constant multiples of $\lambda$. Such an index exists from the two-sided exponential bounds and the choice of $J$. Its single variance summand is at least $c/\lambda$. This proves the trace-variance rate.

For $D(\lambda)$, the first $J$ terms are at most $J$; beyond $J$, the squared response is at most $\mu_j^2/\lambda^2$, whose geometric tail is $O(1)$ because $e^{-aJ}$ is of order $\lambda$. Thus $D(\lambda)=O(J)$. For a lower bound, every index in a block of length proportional to $J$ lying sufficiently below the threshold has $\mu_j\geq C\lambda$, so its squared response is bounded below by a positive constant. There are order $J$ such indices. Therefore $D(\lambda)\asymp J\asymp\log(1/\lambda)$. $\square$

Worked Example: A Geometric Spectrum

Let $\mu_j=2^{-j}$, $j\geq1$, and $\lambda=1/16=2^{-4}$. The threshold is at $j=4$. The contributions at $j=2,4,6$ are, respectively, $$ \frac{1/4}{(1/4+1/16)^2}=2.56,\qquad \frac{1/16}{(1/16+1/16)^2}=4,\qquad \frac{1/64}{(1/64+1/16)^2}=2.56. $$ Again, the variance contribution is largest near the threshold. As $\lambda$ becomes smaller, the number of directions above threshold grows in proportion to $\log(1/\lambda)$, while the total spectral variance grows in proportion to $1/\lambda$, up to constants and the factor $\sigma^2/n$.

Finite Spectra and a Common Pitfall

Worked Example: When There Are Only Three Directions

Suppose the spectrum consists of $\mu_1=1$, $\mu_2=1/4$, and $\mu_3=1/16$, with no further positive eigenvalues, and take $\lambda=1/4$. The three trace-variance terms are $$ \frac{1}{(1+1/4)^2}=0.64,\qquad \frac{1/4}{(1/4+1/4)^2}=1,\qquad \frac{1/16}{(1/16+1/4)^2}=0.64. $$ Their sum is $2.28$, so $V(\lambda)=2.28\sigma^2/n$. There are only three directions, so decreasing $\lambda$ cannot produce the infinite-spectrum polynomial or exponential rates indefinitely. In fact, as $\lambda$ tends to zero, this sum tends to $1+4+16=21$.

Common pitfall: It is incorrect to infer that a spectral variance sum is finite just because the eigenvalues are bounded and tend to zero. For the Tikhonov trace variance defined here, fixed-$\lambda$ summands are comparable to $\mu_j$ in the tail. For example, if $\mu_j=j^{-1/2}$, then $\mu_j/(\mu_j+\lambda)^2$ is asymptotic to $j^{-1/2}/\lambda^2$, and the sum diverges. The correction is to check a summability condition appropriate to the actual summand; in this setting, $\sum_j\mu_j<\infty$ suffices and, for bounded eigenvalues, is necessary.

A second error is to equate the number of eigenvalues above $\lambda$ with trace variance. That count is useful for locating the active spectral range: it is of order $\lambda^{-1/\alpha}$ under polynomial decay and $\log(1/\lambda)$ under exponential decay. But the trace variance weights directions by $\mu_j/(\mu_j+\lambda)^2$. Its corresponding rates are $\lambda^{-1-1/\alpha}$ and $\lambda^{-1}$, respectively. These differences are consequential when comparing spectra or assessing how regularization changes variance.

Key takeaway: Polynomial decay produces a power-law effective dimension and a trace-variance rate $\lambda^{-1-1/\alpha}$. Exponential decay produces a logarithmic effective dimension and a trace-variance rate $\lambda^{-1}$. Always identify the exact spectral sum before interpreting its rate, and verify that the eigenvalues make that sum finite.

Check Your Understanding

Use the definitions and assumptions in this tutorial to answer the following.

For $\mu_j\asymp j^{-3}$, what are the orders of $D(\lambda)$ and $V(\lambda)$ as $\lambda$ decreases to zero?
Why does a threshold count alone not determine Tikhonov trace variance?
Under exponential eigenvalue decay, why is the number of directions above the threshold logarithmic in $1/\lambda$?
For a bounded spectrum, what summability condition ensures that the Tikhonov trace-variance sum is finite?
Why do the infinite-spectrum asymptotic rates not continue indefinitely for a finite spectrum?