Exponential Eigenvalue Decay and Effective Dimension

Why Exponential Decay Produces a Logarithm

The effective dimension in kernel ridge analysis is a regularized count of covariance directions. A direction with eigenvalue much larger than the regularization level contributes nearly one; a direction with eigenvalue much smaller contributes only a small fraction. When eigenvalues decrease exponentially, their size crosses the regularization level after a number of indices proportional to $\log(1/\lambda)$. The effective dimension therefore grows logarithmically as $\lambda$ decreases.

This is an order statement, not a claim that the effective dimension equals an exact logarithm. Its precise form depends on the eigenvalue bounds, their constants, and whether the spectrum has infinitely many positive eigenvalues.

Effective Dimension and Exponential Spectra

Definition: Let $T$ be a positive, compact covariance operator with nonzero eigenvalues $\mu_1\geq\mu_2\geq\cdots>0$, counted with multiplicity. For $\lambda>0$, its effective dimension is $$ \mathcal{N}(\lambda)=\operatorname{Tr}\!\left[T(T+\lambda I)^{-1}\right] =\sum_{j\geq 1}\frac{\mu_j}{\mu_j+\lambda}. $$ Eigenvalues equal to zero contribute zero and can be omitted. The sum is finite when $T$ is trace class, as is the case for the exponentially decaying spectra considered here.

Each summand lies between zero and one. If $\mu_j\geq\lambda$, then $\mu_j/(\mu_j+\lambda)\geq 1/2$; if $\mu_j\ll\lambda$, the summand is approximately $\mu_j/\lambda$. Thus $\mathcal{N}(\lambda)$ is a soft count: it counts the well-resolved directions almost fully and gives smaller weights to the rest.

For geometric exponential decay, the standard assumption is that there are constants $a>0$, $c>0$, and $C>0$ such that $$ c e^{-aj}\leq \mu_j\leq C e^{-aj},\qquad j\geq 1. $$ The constants $c,C,a$ do not depend on $\lambda$. In this tutorial, logarithmic order means that positive constants $A,B$ exist for which $A\log(1/\lambda)\leq\mathcal{N}(\lambda)\leq B\log(1/\lambda)$ for all sufficiently small $\lambda$. Changing a fixed scale inside the logarithm affects only constants and lower-order terms.

Worked Example: Locating the Spectral Cutoff

Suppose $\mu_j=5e^{-0.7j}$, and take $\lambda=0.01$. To find approximately where the spectrum crosses $\lambda$, solve $5e^{-0.7j}=\lambda$: $$ j=\frac{\log(5/0.01)}{0.7} =\frac{\log(500)}{0.7} \approx\frac{6.2146}{0.7} \approx 8.88. $$

The first eight eigenvalues are at least $\lambda$, because $j\leq 8$ implies $5e^{-0.7j}\geq 5e^{-5.6}\approx 0.0185>0.01$. At $j=9$, $\mu_9=5e^{-6.3}\approx0.00918<0.01$. The effective dimension is not exactly eight: the first eight terms each contribute at least $1/2$, and the remaining terms still contribute positive amounts. The cutoff calculation predicts the scale of the answer, not an integer-valued dimension.

The Logarithmic-Order Result

Theorem: Suppose $T$ has infinitely many positive eigenvalues satisfying $c e^{-aj}\leq\mu_j\leq C e^{-aj}$, with fixed $a,c,C>0$. Then, as $\lambda\downarrow0$, $$ \mathcal{N}(\lambda)=\Theta\!\left(\log(1/\lambda)\right). $$ That is, there are constants $A,B>0$ and $\lambda_0>0$ such that $A\log(1/\lambda)\leq\mathcal{N}(\lambda)\leq B\log(1/\lambda)$ whenever $0<\lambda<\lambda_0$.

Proof. For the lower bound, set $J_-=\left\lfloor a^{-1}\log(c/\lambda)\right\rfloor$. For each $j\leq J_-$, the lower eigenvalue bound gives $\mu_j\geq c e^{-aJ_-}\geq\lambda$. Consequently, each of these $J_-$ terms is at least $1/2$, and $$ \mathcal{N}(\lambda)\geq \frac{J_-}{2} \geq \frac{1}{2a}\log(c/\lambda)-\frac{1}{2}. $$ As $\lambda\downarrow0$, $\log(c/\lambda)=\log(1/\lambda)+\log c$; the fixed additive term $\log c$ does not change the order. Hence the lower bound is at least a positive constant times $\log(1/\lambda)$ for sufficiently small $\lambda$.

For the upper bound, take $J_+=\left\lceil a^{-1}\log(C/\lambda)\right\rceil$, for sufficiently small $\lambda$ that $J_+\geq1$. The first $J_+$ summands are each at most one, so their total is at most $J_+$. For the remaining terms, use $\mu_j/(\mu_j+\lambda)\leq\mu_j/\lambda$ and the upper eigenvalue bound: $$ \sum_{j>J_+}\frac{\mu_j}{\mu_j+\lambda} \leq \frac{C}{\lambda}\sum_{j>J_+}e^{-aj} =\frac{C}{\lambda}\frac{e^{-a(J_++1)}}{1-e^{-a}} \leq\frac{1}{1-e^{-a}}. $$ The last inequality follows from $J_+\geq a^{-1}\log(C/\lambda)$, which implies $C e^{-aJ_+}/\lambda\leq1$. Thus $\mathcal{N}(\lambda)\leq J_++(1-e^{-a})^{-1}$, which is at most a constant times $\log(1/\lambda)$ for sufficiently small $\lambda$. Together, the bounds prove the claim. $\square$

Worked Example: A Geometric Spectrum with an Explicit Bound

Let $\mu_j=2^{-j}$ for $j\geq1$, and set $\lambda=2^{-m}$ for a positive integer $m$. For $j\leq m$, the ratio $\mu_j/\lambda=2^{m-j}\geq1$, so each of the first $m$ summands is at least $1/2$. For $j=m+k$, where $k\geq1$, the summand is $$ \frac{2^{-(m+k)}}{2^{-(m+k)}+2^{-m}} =\frac{1}{1+2^k} \leq 2^{-k}. $$

The first $m$ terms therefore contribute at least $m/2$, while the tail is at most $\sum_{k\geq1}2^{-k}=1$. Since the first $m$ terms are also at most $m$, $$ \frac{m}{2}\leq\mathcal{N}(2^{-m})\leq m+1. $$ As $m=\log(1/\lambda)/\log 2$, these bounds display logarithmic growth directly. For example, at $m=4$, the first four terms sum to $8/9+4/5+2/3+1/2=257/90\approx2.856$, and the tail is at most $1$. Thus $2.856\leq\mathcal{N}(1/16)\leq3.856$; the bound is consistent with $2\leq\mathcal{N}(1/16)\leq5$ from the general inequality.

What Changes for Faster-Than-Geometric Decay?

“Exponential decay” is sometimes used broadly for sequences of the form $e^{-a j^r}$, with $r>0$. The geometric case above is $r=1$. If $r\neq1$, the cutoff index has a different dependence on $\lambda$, so the effective-dimension order changes as well. This distinction matters when describing a spectrum: the exponent of the index cannot be dropped.

Derived order: If $\mu_j=e^{-a j^r}$, where $a,r>0$, then $$ \mathcal{N}(\lambda)=\Theta\!\left((\log(1/\lambda))^{1/r}\right) \quad\text{as }\lambda\downarrow0. $$

Derivation. Write $L=\log(1/\lambda)$. If $j\leq (L/a)^{1/r}$, then $a j^r\leq L$, so $\mu_j\geq\lambda$; each such term contributes at least $1/2$. The number of these indices is of order $L^{1/r}$, giving the lower bound.

For the upper bound, let $J=\left\lceil(2L/a)^{1/r}\right\rceil$. The first $J$ terms contribute at most $J$. For $j>J$, $\mu_j/\lambda=e^{L-a j^r}\leq e^{-a j^r/2}$, since $a j^r\geq2L$. The remaining contribution is therefore at most $\sum_{j>J}e^{-a j^r/2}$, which is bounded by the finite constant $\sum_{j\geq1}e^{-a j^r/2}$. This series converges: for sufficiently large $j$, $a j^r/2\geq 2\log j$, so its terms are at most $j^{-2}$. The upper bound is $J$ plus a constant, hence is of order $L^{1/r}$. This proves the stated order. $\square$

Worked Example: Quadratic Exponential Decay

Suppose $\mu_j=e^{-0.5j^2}$. Here $a=0.5$ and $r=2$, so the cutoff is determined by $0.5j^2\approx\log(1/\lambda)$, or $j\approx\sqrt{2\log(1/\lambda)}$. The derived order is therefore $\mathcal{N}(\lambda)=\Theta(\sqrt{\log(1/\lambda)})$, not $\Theta(\log(1/\lambda))$.

For a concrete value, take $\lambda=e^{-8}$. The condition $\mu_j\geq\lambda$ becomes $0.5j^2\leq8$, which holds for $j=1,2,3,4$, but not $j=5$. The first four terms each contribute at least $1/2$, so $\mathcal{N}(e^{-8})\geq2$. The cutoff scale $\sqrt{2\log(1/\lambda)}=\sqrt{16}=4$ matches this count. The remaining terms are positive, but decrease rapidly; the square-root logarithmic order describes their total scale as $\lambda$ decreases.

Assumptions, Interpretation, and a Common Pitfall

The two-sided exponential condition in the theorem serves two different purposes. The upper bound on $\mu_j$ controls the tail and yields an upper bound on effective dimension. The lower bound ensures that sufficiently many eigenvalues remain at or above $\lambda$, yielding a matching lower bound. With only an upper bound, logarithmic growth is an upper bound, but the effective dimension may grow more slowly. For example, a finite-rank operator has $\mathcal{N}(\lambda)$ tending to its rank as $\lambda\downarrow0$, rather than increasing without bound.

A common mistake is to replace the effective dimension by the number of eigenvalues above $\lambda$ and treat the two quantities as exactly equal. The count is useful for identifying the scale, but the definition weights every eigenvalue: those below $\lambda$ still contribute $\mu_j/(\mu_j+\lambda)>0$. The proof of the upper bound explicitly controls this tail; ignoring it would leave a gap. Another mistake is to call every $e^{-a j^r}$ spectrum “geometric.” Only $r=1$ gives a cutoff proportional to $\log(1/\lambda)$; for general $r$, the order is $(\log(1/\lambda))^{1/r}$.

In kernel ridge analysis, effective dimension summarizes how many covariance directions are influential at a given regularization level. Exponential spectra make this number grow slowly: reducing $\lambda$ can bring in additional directions, but the number grows only logarithmically in the geometric case. The calculation characterizes the variance-side complexity of the spectrum; it does not, by itself, select a regularization level or determine the complete prediction risk.

Check Your Understanding

Answer each question using the definition and assumptions stated above.

Why does a summand contribute at least $1/2$ whenever $\mu_j\geq\lambda$?
Which part of the two-sided eigenvalue assumption gives the lower bound on effective dimension, and which part controls its tail?
For $\mu_j$ proportional to $q^j$, where $0<q<1$, what is the order of $\mathcal{N}(\lambda)$ as $\lambda$ decreases?
What order follows for $\mu_j=e^{-a j^3}$, and how does it differ from geometric exponential decay?
Why can a finite-rank covariance operator not have effective dimension growing without bound as $\lambda\downarrow0$?