Conjugate-Gradient Regularization and Ritz Spectra

Why Conjugate Gradient Acts Like a Regularizer

For an inverse problem $Hx=g$, where $H$ is a positive-definite symmetric matrix, the exact solution multiplies each eigen-coordinate of $g$ by $1/\lambda$. When an eigenvalue $\lambda$ is small, that division can amplify noise substantially. Conjugate gradient (CG), started from zero and stopped after a finite number of iterations, does not apply the full inverse. Instead, it constructs a polynomial approximation to the inverse using the observed right-hand side $g$.

This makes early-stopped CG a spectral regularization method, but not generally a fixed filter chosen in advance. Its polynomial is data-dependent: the Lanczos process started from $g$ produces Ritz values that determine the residual polynomial. Those values help explain which parts of the spectrum are attenuated at a given iteration—and why the attenuation need not be smooth or monotone.

Definition: Let $H$ be a real symmetric positive-definite matrix and $g\ne 0$. CG started at $x_0=0$ generates $x_k$ in the Krylov subspace $\mathcal K_k(H,g)=\operatorname{span}\{g,Hg,\ldots,H^{k-1}g\}$. A spectral-filter representation is $x_k=q_{k-1}(H)g$, where $q_{k-1}$ is a polynomial of degree at most $k-1$. The associated signal filter is $f_k(\lambda)=\lambda q_{k-1}(\lambda)$; the residual polynomial is $p_k(\lambda)=1-f_k(\lambda)$, so $p_k(0)=1$.

If $H u_i=\lambda_i u_i$, then the exact solution has coordinate $u_i^\mathsf{T}g/\lambda_i$, while the $k$-step iterate has coordinate $f_k(\lambda_i)u_i^\mathsf{T}g/\lambda_i$. Thus $f_k(\lambda_i)$ is the fraction of the exact solution coordinate retained at that eigenvalue. Equivalently, the residual coordinate is multiplied by $p_k(\lambda_i)$. The filter polynomial is shaped by the spectrum visible from the starting vector $g$, not just by the eigenvalues of $H$ in isolation.

Worked Examples of Finite-Step Filters

Worked Example: One CG Step Can Overshoot

Take $H=\operatorname{diag}(1,4)$ and $g=(1,1)^\mathsf{T}$. The first CG iterate has the form $x_1=\alpha g$. CG minimizes $\|H^{-1}g-x\|_H$, where $\|z\|_H^2=z^\mathsf{T}Hz$. Minimizing over $\alpha$, or using the first CG step, gives

\alpha=\frac{g^\mathsf{T}g}{g^\mathsf{T}Hg} =\frac{2}{1+4}=\frac{2}{5}.

Consequently $q_0(\lambda)=2/5$, $f_1(\lambda)=2\lambda/5$, and $p_1(\lambda)=1-2\lambda/5$. At the two eigenvalues the signal filters are $f_1(1)=2/5$ and $f_1(4)=8/5$. The second exceeds one: a CG filter is not necessarily a monotone profile bounded by one. After two steps, the Krylov space spans both coordinates and CG solves exactly.

Worked Example: Computing a Two-Step Ritz Filter

Let $H=\operatorname{diag}(1,4,9)$ and $g=(1,1,1)^\mathsf{T}$. Lanczos begins with $v_1=g/\sqrt{3}$, and its first diagonal coefficient is $\alpha_1=v_1^\mathsf{T}Hv_1=14/3$. The unnormalized remainder for the starting vector is

Hg-\frac{14}{3}g=\frac{1}{3}(-11,-2,13)^\mathsf{T}, \qquad \left\|Hg-\frac{14}{3}g\right\|_2 =\frac{\sqrt{294}}{3} \approx 5.715.

Lanczos uses the normalized starting vector, so the off-diagonal coefficient is $\beta_1=\sqrt{294}/(3\sqrt{3})=7\sqrt{2}/3$, not the norm of the unnormalized remainder. The next Lanczos vector is $v_2=(-11,-2,13)^\mathsf{T}/\sqrt{294}$. Its diagonal coefficient is

\alpha_2=v_2^\mathsf{T}Hv_2 =\frac{121+16+1521}{294} =\frac{829}{147}.

The two-dimensional Lanczos matrix is $T_2=\begin{pmatrix}14/3&7\sqrt{2}/3\\7\sqrt{2}/3&829/147\end{pmatrix}$. Its trace is $505/49$, and its determinant is $108/7$: indeed, $(14/3)(829/147)-(7\sqrt{2}/3)^2=11606/441-4802/441=108/7$. Its two positive eigenvalues, the Ritz values, therefore have reciprocal sum $505/756$ and reciprocal product $7/108$. Hence

p_2(\lambda)=\left(1-\frac{\lambda}{\theta_1}\right) \left(1-\frac{\lambda}{\theta_2}\right) =1-\frac{505}{756}\lambda+\frac{7}{108}\lambda^2, \qquad f_2(\lambda)=1-p_2(\lambda).

At $\lambda=1$, $p_2(1)=1-505/756+7/108=25/63$, so $f_2(1)=38/63$. At $\lambda=4$, $p_2(4)=1-4(505/756)+16(7/108)=-40/63$, so $f_2(4)=103/63$. At $\lambda=9$, $p_2(9)=1-9(505/756)+81(7/108)=5/21$, so $f_2(9)=16/21$. The value at $4$ again exceeds one. As a check, $x_2$ has coordinates $38/63,\;103/252,\;16/189$. Its residual $g-Hx_2=(25/63,-40/63,5/21)^\mathsf{T}$ is orthogonal to both $g$ and $Hg$, as CG requires.

Worked Example: Interpreting Noise Multipliers

Use the two-step filter just calculated, and consider a fixed-filter calculation with additive noise $\varepsilon$ having mean zero and covariance $\sigma^2 I$. If this polynomial is held fixed, the noise in the estimate is $q_1(H)\varepsilon$, where $q_1(\lambda)=f_2(\lambda)/\lambda$. Its multipliers at eigenvalues $1,4,9$ are, respectively, $38/63,\;103/252,\;16/189$. Thus its variance trace is

\sigma^2\left[\left(\frac{38}{63}\right)^2+ \left(\frac{103}{252}\right)^2+ \left(\frac{16}{189}\right)^2\right] =\sigma^2\frac{307513}{571536}.

For comparison, applying the unregularized inverse would give variance trace $\sigma^2(1+1/16+1/81)$, which is larger. This calculation describes a fixed polynomial. In actual CG applied to noisy $g$, the Ritz values and polynomial can themselves depend on that noise, so this fixed-filter trace is not automatically the unconditional variance of the data-dependent CG estimator.

The Ritz-Value Representation

The key connection is that CG's residual polynomial has roots at the eigenvalues of the Lanczos matrix. To state it precisely, run $k$ Lanczos steps from $v_1=g/\|g\|_2$, with no breakdown before step $k$. Write $T_k$ for the resulting symmetric tridiagonal matrix, with diagonal entries $\alpha_j$ and off-diagonal entries $\beta_j$. Its eigenvalues $\theta_1,\ldots,\theta_k$ are the Ritz values. Since $H$ is positive definite, $T_k$ is positive definite and all $\theta_j>0$.

Theorem: Under these conditions, the CG residual after $k$ steps is $r_k=p_k(H)g$, where $$ p_k(\lambda)=\frac{\det(\lambda I-T_k)}{\det(-T_k)} =\prod_{j=1}^k\left(1-\frac{\lambda}{\theta_j}\right). $$ Therefore $f_k(\lambda)=1-p_k(\lambda)$, and $q_{k-1}(\lambda)=f_k(\lambda)/\lambda$ is a polynomial of degree at most $k-1$.

Proof. CG constructs $x_k\in\mathcal K_k(H,g)$ such that its residual $r_k=g-Hx_k$ is orthogonal to $\mathcal K_k(H,g)$. Since $x_k$ is a polynomial in $H$ applied to $g$, $r_k=p(H)g$ for a degree-at-most-$k$ polynomial with $p(0)=1$. The orthogonality conditions say that $p$ is orthogonal to every polynomial of degree at most $k-1$ under the discrete inner product

\langle a,b\rangle_g =\sum_i (u_i^\mathsf{T}g)^2a(\lambda_i)b(\lambda_i),

where $u_i$ is an orthonormal eigenbasis of $H$. Lanczos tridiagonalization from $v_1$ represents this same spectral measure: the three-term recurrence for the orthogonal polynomials has coefficients $\alpha_j,\beta_j$. Its degree-$k$ polynomial is proportional to $\det(\lambda I-T_k)$. One can see the determinant recurrence directly by expanding the tridiagonal determinant: $D_0=1$, $D_1=\lambda-\alpha_1$, and $D_j=(\lambda-\alpha_j)D_{j-1}-\beta_{j-1}^2D_{j-2}$. This is the Lanczos orthogonal-polynomial recurrence. Thus the CG residual polynomial is $D_k(\lambda)/D_k(0)$; since $D_k(0)=(-1)^k\det(T_k)$, this is the displayed product. Finally $p_k(0)=1$, so $1-p_k(\lambda)$ has a factor $\lambda$, proving that $q_{k-1}$ is a polynomial of degree at most $k-1$. $\square$

What Ritz Values Say About Noise Suppression

The product representation gives a direct description near zero. Expanding it shows that, for fixed positive Ritz values,

p_k(\lambda)=1-\lambda\sum_{j=1}^k\frac{1}{\theta_j}+O(\lambda^2), \qquad f_k(\lambda)=\lambda\sum_{j=1}^k\frac{1}{\theta_j}+O(\lambda^2).

Therefore the solution-coordinate multiplier $f_k(\lambda)$ tends to zero linearly as $\lambda$ tends to zero. The noise multiplier after applying the inverse, $q_{k-1}(\lambda)=f_k(\lambda)/\lambda$, instead has a finite limit $\sum_j1/\theta_j$. This helps explain why a finite-step iterate avoids the unbounded $1/\lambda$ amplification of the exact inverse near zero. It is not, by itself, a uniform bound: the limit can be large if the Ritz values are small.

For a fixed polynomial and isotropic noise with covariance $\sigma^2 I$, the trace of the noise covariance is $\sigma^2\sum_i q_{k-1}(\lambda_i)^2$. That identity follows by diagonalizing $H$: the noise coordinates are uncorrelated with variance $\sigma^2$, and the $i$th coordinate is multiplied by $q_{k-1}(\lambda_i)$. But ordinary CG chooses its polynomial from the observed right-hand side. When that right-hand side includes noise, this dependence matters; a fixed-filter variance calculation cannot simply be transferred to the random CG estimator.

Key takeaway: Ritz values identify the roots of the finite-step residual polynomial and describe low-eigenvalue attenuation. They do not guarantee a monotone filter, and their data dependence is important whenever noise properties are assessed.

Common Pitfall

A tempting but incorrect argument is: “CG is a regularization method, so every eigen-coordinate must be shrunk by a factor between zero and one, increasingly as the eigenvalue grows.” The first worked example disproves this: at $\lambda=4$, the one-step filter equals $8/5$. CG minimizes an energy error over a Krylov subspace; it does not impose coordinatewise bounds on its polynomial. The correct interpretation is to calculate $p_k$ from the Ritz values and inspect $f_k=1-p_k$ on the spectrum of interest. In addition, do not confuse a Ritz value with an eigenvalue of $H$: Ritz values are eigenvalues of the finite-dimensional projected matrix $T_k$, and their locations depend on the starting vector and iteration count.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

Why is $q_{k-1}(\lambda)=f_k(\lambda)/\lambda$ a polynomial even though the formula appears to divide by $\lambda$?
What information about the residual polynomial is supplied by the Ritz values?
For a fixed finite set of positive Ritz values, what is the first-order behavior of $f_k(\lambda)$ as $\lambda$ approaches zero?
Why does a fixed-filter variance calculation not generally equal the unconditional variance of CG with a noisy right-hand side?
Give one reason a finite-step CG filter may exceed one at an eigenvalue.