Polynomial Eigenvalue Decay and Effective Dimension

Why the Eigenvalue Tail Matters

The effective dimension of a kernel covariance operator measures how many spectral directions are substantially retained at a chosen regularization level. Its value is not generally the number of eigenvalues larger than that level: eigenvalues below the level still contribute, but with reduced weight. When eigenvalues decay polynomially, both the size of this tail and the number of larger eigenvalues depend on the decay exponent. This tutorial makes that dependence explicit.

Let $T$ be a positive, compact, trace-class covariance operator with positive eigenvalues $\mu_1\geq\mu_2\geq\cdots>0$, listed with multiplicity. The operator may also have a null space; its zero eigenvalues contribute nothing to the quantity below. For regularization parameter $\lambda>0$, the effective dimension is the trace of $T(T+\lambda I)^{-1}$.

Definition: The effective dimension at regularization level $\lambda>0$ is $$ \mathcal{N}(\lambda) = \operatorname{Tr}\!\left[T(T+\lambda I)^{-1}\right] = \sum_{j=1}^{\infty}\frac{\mu_j}{\mu_j+\lambda}. $$ We say the eigenvalues have polynomial decay with exponent $p>1$ if, for some $c>0$, $\mu_j\sim c j^{-p}$ as $j\to\infty$. More generally, $\mu_j\asymp j^{-p}$ means there are constants $c_-,c_+>0$ and an index $j_0$ such that $c_-j^{-p}\leq\mu_j\leq c_+j^{-p}$ for every $j\geq j_0$.

The convention here is that $p$ is the power in the eigenvalue sequence itself. Thus larger $p$ means faster decay. The condition $p>1$ is natural for an infinite positive spectrum of a trace-class operator: a sequence comparable to $j^{-p}$ is summable precisely when $p>1$. For each fixed $\lambda>0$, the effective dimension is finite because $\mu_j/(\mu_j+\lambda)\leq\mu_j/\lambda$, and $\sum_j\mu_j<\infty$.

The Polynomial Effective-Dimension Order

The summand is close to one when $\mu_j$ is much larger than $\lambda$, and is approximately $\mu_j/\lambda$ when $\mu_j$ is much smaller. For a power law, the transition occurs around the index $j$ satisfying $c j^{-p}\approx\lambda$, or $j\approx(c/\lambda)^{1/p}$. The following result shows that this transition index gives the correct order of the whole sum, including its tail.

Theorem: Suppose $\mu_j\asymp j^{-p}$ for some $p>1$. Then, as $\lambda\downarrow0$, $$ \mathcal{N}(\lambda)\asymp \lambda^{-1/p}. $$ That is, there are constants $A,B>0$ and $\lambda_0>0$ such that $A\lambda^{-1/p}\leq\mathcal{N}(\lambda)\leq B\lambda^{-1/p}$ whenever $0<\lambda<\lambda_0$. The constants can depend on the eigenvalue bounds and on $p$.

Proof. Choose $j_0,c_-,c_+$ such that $c_-j^{-p}\leq\mu_j\leq c_+j^{-p}$ for $j\geq j_0$. For the lower bound, take $J=\lfloor(c_-/\lambda)^{1/p}\rfloor$. For sufficiently small $\lambda$, $J\geq j_0$. Every $j_0\leq j\leq J$ satisfies $\mu_j\geq c_-j^{-p}\geq\lambda$, so $\mu_j/(\mu_j+\lambda)\geq1/2$. Consequently, $$ \mathcal{N}(\lambda)\geq\frac{J-j_0+1}{2}. $$ As $\lambda\downarrow0$, $J$ is of order $\lambda^{-1/p}$, giving the required lower bound.

For the upper bound, let $J=\lceil(c_+/\lambda)^{1/p}\rceil$, taking $\lambda$ small enough that $J\geq j_0$. The first $J$ summands are at most one each. For $j>J$, use $\mu_j/(\mu_j+\lambda)\leq\mu_j/\lambda$ and the upper eigenvalue bound. Since $x^{-p}$ is decreasing and $p>1$, $$ \mathcal{N}(\lambda) \leq J+\frac{c_+}{\lambda}\sum_{j>J}j^{-p} \leq J+\frac{c_+}{\lambda}\int_J^\infty x^{-p}\,dx =J+\frac{c_+}{(p-1)\lambda}J^{1-p}. $$ Here $J$ is of order $\lambda^{-1/p}$, and $\lambda^{-1}J^{1-p}$ is also of that order. The finitely many indices before $j_0$ do not affect the bounds. This proves the theorem. $\square$

Worked Example: A Quadratic Spectrum

Suppose $\mu_j=4j^{-2}$. Here $c=4$ and $p=2$, so the theorem gives $\mathcal{N}(\lambda)\asymp\lambda^{-1/2}$. The exact leading constant can also be calculated below; it is $\pi$. Thus $$ \mathcal{N}(\lambda)\sim\pi\lambda^{-1/2}. $$ At $\lambda=10^{-4}$, the leading-order approximation is $\pi(10^{-4})^{-1/2}=100\pi\approx314.16$. This is an asymptotic approximation to the sum, not an assertion that its exact value at this particular $\lambda$ is $314.16$.

The transition index is approximately $(4/10^{-4})^{1/2}=200$: near that index, the eigenvalue is about the regularization level. The sum is not just 200, however, because eigenvalues above and below the transition both contribute.

The Sharp Constant for an Exact Power Law

An exact asymptotic for the eigenvalues gives more than the rate: it determines the leading constant in the effective dimension. The constant comes from approximating the sum by an integral after rescaling the index by the transition scale.

Theorem: If $\mu_j\sim c j^{-p}$, where $c>0$ and $p>1$, then $$ \mathcal{N}(\lambda) \sim c^{1/p}\lambda^{-1/p} I_p, \qquad I_p=\int_0^\infty\frac{dx}{1+x^p} =\frac{\pi}{p}\csc\!\left(\frac{\pi}{p}\right). $$

Proof. First consider an exact power sequence $a j^{-p}$, where $a>0$. Set $t=(a/\lambda)^{1/p}$. Its effective-dimension sum is $$ \sum_{j=1}^{\infty}\frac{a j^{-p}}{a j^{-p}+\lambda} = \sum_{j=1}^{\infty}\frac{1}{1+(j/t)^p}. $$ The function $g(x)=(1+x^p)^{-1}$ is continuous, decreasing, and integrable on $[0,\infty)$, since $p>1$. Therefore its Riemann sums on bounded intervals converge to the corresponding integrals. The tails are controlled uniformly: for $j>Rt$, with $R>0$, $$ \frac{1}{t}\sum_{j>Rt}g(j/t) \leq \frac{1}{t}\sum_{j>Rt}(j/t)^{-p} \leq \frac{R^{1-p}}{p-1}+o(1) $$ as $t\to\infty$, by the integral bound for a decreasing power function. Letting first $t\to\infty$ and then $R\to\infty$ gives $$ \frac{1}{t}\sum_{j=1}^{\infty}g(j/t)\longrightarrow \int_0^\infty g(x)\,dx=I_p. $$ The displayed evaluation of the integral follows from the beta integral, $\int_0^\infty(1+x^p)^{-1}dx=\frac1p\Gamma(1/p)\Gamma(1-1/p)$, and Euler's reflection identity.

For the general sequence, fix $0<\varepsilon<1$. There is an index $j_0$ such that, for every $j\geq j_0$, $(1-\varepsilon)cj^{-p}\leq\mu_j\leq(1+\varepsilon)cj^{-p}$. Since $u\mapsto u/(u+\lambda)$ is increasing for $u\geq0$, the part of $\mathcal{N}(\lambda)$ from $j\geq j_0$ is bounded below and above by the corresponding power-sequence sums with $a=(1-\varepsilon)c$ and $a=(1+\varepsilon)c$. The finitely many omitted summands are bounded by $j_0$; divided by $(c/\lambda)^{1/p}$, they tend to zero. Applying the exact-power limit and dividing by $(c/\lambda)^{1/p}$, the lower and upper limits are bounded respectively by $(1-\varepsilon)^{1/p}I_p$ and $(1+\varepsilon)^{1/p}I_p$. Letting $\varepsilon\downarrow0$ proves the stated asymptotic. $\square$

Worked Example: A Three-Halves Power Law

Take $\mu_j=3j^{-3/2}$, so $c=3$ and $p=3/2$. The rate exponent is the reciprocal of the eigenvalue-decay exponent, $1/p=2/3$. The integral constant is $$ I_{3/2} = \frac{\pi}{3/2}\csc(2\pi/3) = \frac{2\pi}{3}\cdot\frac{2}{\sqrt{3}} = \frac{4\pi}{3\sqrt{3}}. $$ Multiplying by $c^{1/p}=3^{2/3}$ gives $$ \mathcal{N}(\lambda) \sim \frac{4\pi}{3^{5/6}}\lambda^{-2/3} \approx5.03\lambda^{-2/3}. $$ At $\lambda=10^{-3}$, the leading-order approximation is about $5.03\times100=503$, since $(10^{-3})^{-2/3}=100$. The exponent differs from the quadratic-spectrum example because the eigenvalues decay more slowly.

Worked Example: Using Two-Sided Bounds

Suppose that, for every $j\geq1$, $2j^{-2}\leq\mu_j\leq6j^{-2}$. These inequalities establish polynomial order with $p=2$, even though no exact asymptotic constant for $\mu_j$ has been specified. The theorem therefore gives $\mathcal{N}(\lambda)\asymp\lambda^{-1/2}$.

For a concrete bound at $\lambda=0.01$, take $J_-=\lfloor(2/0.01)^{1/2}\rfloor=14$. For each $1\leq j\leq14$, $\mu_j\geq2j^{-2}\geq2/14^2\approx0.0102>0.01$. Each of these 14 summands is at least $1/2$, so $\mathcal{N}(0.01)\geq7$.

For an upper bound, take $J_+=\lceil(6/0.01)^{1/2}\rceil=25$. The first 25 summands are at most one each. For the rest, use $\mu_j/(\mu_j+0.01)\leq\mu_j/0.01$, followed by the eigenvalue bound and an integral comparison: $$ \mathcal{N}(0.01) \leq25+600\sum_{j>25}j^{-2} \leq25+600\int_{25}^{\infty}x^{-2}\,dx =25+24=49. $$ Thus $7\leq\mathcal{N}(0.01)\leq49$. The interval is deliberately conservative; its purpose is to verify the order from two-sided bounds without assuming a sharp eigenvalue asymptotic.

Interpreting the Exponent and Avoiding a Pitfall

The reciprocal in $\lambda^{-1/p}$ is important. If eigenvalues decrease faster, meaning $p$ is larger, effective dimension grows more slowly as $\lambda$ decreases. For example, the rates for $p=2$ and $p=4$ are respectively $\lambda^{-1/2}$ and $\lambda^{-1/4}$. Some sources instead write the decay as $\mu_j\asymp j^{-1/\alpha}$; under that convention the same calculation gives $\mathcal{N}(\lambda)\asymp\lambda^{-\alpha}$. Always check which exponent is used in the eigenvalue sequence itself.

Common mistake: Count only the eigenvalues above $\lambda$, declare that their number is approximately $\lambda^{-1/p}$, and treat this count as the whole effective dimension. The transition index does give the right order, but the argument is incomplete: infinitely many smaller eigenvalues remain in the sum. Their total contribution is controlled by the tail bound $\lambda^{-1}\sum_{j>J}\mu_j$, which is also of order $\lambda^{-1/p}$ when $J$ is of order $\lambda^{-1/p}$. Ignoring this tail can lead to unjustified constants or an incorrect conclusion when the decay assumptions are insufficient.

In kernel ridge analysis, this spectral calculation converts an eigenvalue assumption into a regularization-dependent measure of the number of directions that matter. The effective dimension enters variance bounds, so its rate determines how the spectral complexity varies with regularization. The calculation here concerns that dependence alone; it does not select a regularization level or combine the dimension with a bias term.

Key takeaway: Under $\mu_j\asymp j^{-p}$ with $p>1$, effective dimension has order $\lambda^{-1/p}$. Under the sharper assumption $\mu_j\sim c j^{-p}$, its leading constant is $c^{1/p}\frac{\pi}{p}\csc(\pi/p)$.

Check Your Understanding

Use the exponent convention and results developed above to answer these questions.

If $\mu_j\asymp j^{-5/2}$, what is the order of $\mathcal{N}(\lambda)$ as $\lambda\downarrow0$?
For $\mu_j\sim 8j^{-4}$, identify the transition index up to constant factors and state the effective-dimension rate.
Why is the condition $p>1$ needed for the integral-tail argument in the sharp asymptotic result?
In the two-sided-bound example, which inequality ensures that each of the first 14 summands is at least $1/2$?
Explain why counting eigenvalues above $\lambda$ alone does not establish the effective-dimension order.

Polynomial Eigenvalue Decay and Effective Dimension

What You'll Learn