Conditioning, Ill-Posed Problems and Tikhonov Regularization

By Better Wise

Last lesson gave you a hard switch: keep the large singular values, drop the small ones, and the pseudoinverse becomes stable. Real problems rarely offer such a clean cut. Here we quantify sensitivity with the condition number, recognize when no cut point exists, and replace truncation with a smooth filter whose strength you can defend.

By the end you should be able to:

• compute and interpret $\kappa_2(A)$ as digits of accuracy lost;
• tell a rank-deficient matrix apart from a discrete ill-posed operator;
• derive the Tikhonov filter factors and read $\lambda$ as a cap on noise amplification;
• choose $\lambda$ with the L-curve, the discrepancy principle, or a validation sweep.

Recall from the previous lesson: $A = U\Sigma V^\top$, $A^{+} = V\Sigma^{+}U^\top$, and TSVD zeroes every $\sigma_i$ below a threshold. Keep that spectral picture, we are about to soften it.

Sensitivity has a number

For square invertible $A$, the 2-norm condition number is $\kappa_2(A) = |A|2|A^{-1}|2 = \sigma{\max}/\sigma{\min}$, and it is exactly the worst-case amplification of relative error:

$$ \frac{|\delta x|}{|x|} \le \kappa(A),\frac{|\delta b|}{|b|} $$

Worked example. Take $A = \begin{bmatrix}1 & 1\ 1 & 1+\varepsilon\end{bmatrix}$ with $\varepsilon = 10^{-8}$. Then $\sigma_{\max}\approx 2$, $\sigma_{\min}\approx \varepsilon/2$, so $\kappa \approx 4\times10^{8}$: a float64 solve keeps about 8 of its 16 digits. Perturbing $b_2$ by one ulp ($10^{-16}$) moves both entries of the solution by $10^{-8}$, since $A^{-1}$ has entries of size $1/\varepsilon$. Nothing is wrong with your solver; the problem is the problem.

Two consequences that bite constantly:

• $\kappa$ is not scale invariant. Row and column equilibration before factorizing is free accuracy.
• $\kappa(A^\top A)=\kappa(A)^2$. This is the whole argument for QR over normal equations, and it also means you should never form $A^\top A$ just to add $\lambda^2 I$ when you can work in the SVD basis instead.

When the residual lies. Hilbert matrices $H_n$ have $\kappa(H_n)\sim e^{3.5n}$; $H_{12}$ has $\kappa\approx 1.7\times10^{16}$, past $1/\epsilon_{\text{mach}}$. The computed solution can have a residual near machine precision while being wrong in every digit. A small residual bounds the residual, not the error, and the gap between them is $\kappa$.

Ill-posed, not singular

Hadamard called a problem well-posed when a solution exists, is unique, and depends continuously on the data. Discrete ill-posed problems fail the third clause: $\sigma_i$ decays smoothly toward the noise floor with no spectral gap, so no truncation index is obvious. They show up in deconvolution, super-resolution, inverse scattering, and any Jacobian of a smoothing forward model.

The diagnostic is the Picard plot: coefficients $|u_i^\top b|$ against $\sigma_i$. For clean data satisfying the Picard condition, $|u_i^\top b|$ decays faster than $\sigma_i$ and the ratios stay bounded. Noise breaks the decay at a floor.

Rows 1 to 5 satisfy the Picard condition: the data coefficients decay faster than the singular values, so the ratios $|u_i^\top b|/\sigma_i$ stay bounded. From row 6 the coefficients stop decaying at $10^{-8}$, the noise floor, while $\sigma_i$ keeps falling. Every mode past that point contributes $10^{-8}/\sigma_i$ of pure amplified noise to the naive solution. The filter factors in the last column show what Tikhonov does about it: modes well above $\lambda$ pass through almost untouched, modes well below $\lambda$ are killed, and the mode at $\sigma_i = \lambda$ is halved.

Tikhonov as a spectral filter with a dial

Tikhonov regularization replaces the solve by the penalized problem

$$ \min_x ; |Ax - b|_2^2 + \lambda^2 |Lx|_2^2 $$

With $L = I$ and the SVD in hand, the solution is a filtered pseudoinverse:

$$ x_\lambda = \sum_i f_i \frac{u_i^\top b}{\sigma_i} v_i, \qquad f_i = \frac{\sigma_i^2}{\sigma_i^2 + \lambda^2} $$

Three readings of the same formula, all worth keeping:

• Filter: $f_i$ is a smooth version of the hard truncation you built last lesson. TSVD sets $f_i \in {0,1}$; Tikhonov sets $f_i \in (0,1)$. Nothing else changes.
• Algebra: $\lambda^2$ is added to every eigenvalue of $A^\top A$, so $\kappa(A^\top A + \lambda^2 I) \le (\sigma_1^2 + \lambda^2)/\lambda^2$. Conditioning becomes finite by construction.
• Statistics: the penalty is a Gaussian prior $x \sim \mathcal{N}(0, \tfrac{1}{2\lambda^2}I)$, and $x_\lambda$ is the MAP estimate. The regularization strength is a prior strength.

Note the units: $\lambda$ carries the units of singular values, so always report $\lambda/\sigma_{\max}$. A $\lambda$ of $10^{-4}$ means nothing until you say it is $10^{-4}$ relative to the largest scale of the operator.

Bias and variance split cleanly. The estimator has expectation $\sum_i f_i (u_i^\top A x_{\text{true}}) v_i / \sigma_i$, so the bias comes from $f_i - 1$, and the propagated noise variance is $\sigma_{\text{noise}}^2 \sum_i f_i^2/\sigma_i^2$. Larger $\lambda$ buys variance at the price of bias. The optimum sits near $\lambda \approx \sigma_{\text{noise}}$ for problems whose coefficients satisfy the Picard condition.

flowchart TD
    A["SVD: plot σ_i and |u_i^T b|"] --> B{"Spectral gap present?"}
    B -->|yes| C["Truncate at the gap (TSVD)"]
    B -->|no| D["Sweep λ over a log grid"]
    D --> E["L-curve: log||x_λ|| vs log||Ax_λ - b||"]
    E --> F["Take the corner, or validate on held-out b"]
    F --> G["Sanity check: filter factors cut modes below the noise floor"]

Choosing the strength: L-curve and validation

L-curve. Sweep $\lambda$ geometrically, say forty values from $10^{-8}\sigma_{\max}$ to $10^{0}\sigma_{\max}$. For each, record $|x_\lambda|2$ and $|Ax\lambda - b|_2$ and plot them log-log. Small $\lambda$ gives a large solution norm and a small residual (the vertical leg, dominated by noise amplification). Large $\lambda$ gives a small solution norm and a large residual (the horizontal leg, dominated by bias). The corner is the balance point. Compute it as the point of maximum discrete curvature, do not eyeball it if you can avoid it.

Worked number. Take $H_{12}$ with $\kappa \approx 1.7\times10^{16}$ and relative noise $\delta = 10^{-6}$. The unregularized error scales like $\kappa \delta \approx 10^{10}$, so every digit is wrong. The error of the filtered solution is roughly $\sqrt{\delta}$, about $10^{-3}$: regularization buys back thirteen orders of magnitude at the cost of about three digits of bias. That trade is almost always worth taking, and it is why the unregularized answer is not a baseline worth defending.

Validation sweep. When you have repeated observations or held-out entries of $b$, do the honest thing: fit $x_\lambda$ on a training split, score $|A_{\text{val}} x_\lambda - b_{\text{val}}|$ on the rest, and pick the $\lambda$ that minimizes it. This costs one SVD plus cheap filtered solves, since $f_i$ is the only thing that changes with $\lambda$. GCV is the closed-form shortcut, minimizing $|Ax_\lambda - b|^2/(m - \mathrm{tr},H_\lambda)^2$ with $\mathrm{tr},H_\lambda = \sum_i f_i$; use it when no split is available, and distrust it when the noise is correlated.

Tikhonov filter factors are _____, which tend to _____ for modes above λ and to zero below it. The L-curve plots _____, and its corner marks the balance between noise amplification and bias. A useful default starting point for λ is the _____ of the data, measured in the same units as the singular values. GCV divides the residual by _____, the effective number of fitted parameters.

Field notes on regularizing real systems

• Never report a solve without $\kappa$. Compute it from the SVD you already have. If you did not compute the SVD, say so, because QR-based solves hide the conditioning completely.
• Residual is not error. A tiny residual with a huge $\kappa$ is the signature of a confident wrong answer. Check the residual against $\kappa \cdot \epsilon_{\text{mach}} \cdot |A||x|$.
• Scale before you penalize. With $L = I$, the penalty is not scale-invariant across columns. Standardize columns first, or use a smoothing operator $L$ (first or second difference) that encodes what "rough" means for your problem.
• A missing L-curve corner is information. If the curve has no bend, either the noise is correlated or the problem is so ill-posed that the corner sits at the grid boundary. Refit with a wider grid before trusting anything.
• Tikhonov is one linear solve. Stack it: $\min |[A; \lambda L]x - [b; 0]|$ is an ordinary least-squares problem, so the QR solver from the first lesson applies directly.
• Truncation and Tikhonov agree in the limit. As the filter factors sharpen, the two families converge. Do not agonize over the choice; agonize over the strength.

What to carry forward

Conditioning tells you how much a solve can lie. The Picard plot tells you which singular directions the data actually support. Tikhonov turns that diagnosis into a one-parameter estimator whose filter factors you can read off, and the L-curve or a validation sweep picks the parameter with a defensible argument rather than a guess. The next lesson, the module checkpoint, puts QR, SVD, truncation and Tikhonov together on full systems and asks you to choose among them under time pressure.

Front: Condition number of a linear solve, in terms of the SVD Back: κ(A) = σ_max / σ_min, the relative error amplification factor.

Front: Error bound for a perturbed solve Back: ||Δx||/||x|| ≤ κ(A) · ||Δb||/||b|| for consistent systems.

Front: Why does a tiny residual not imply a small error? Back: Residual bounds the backward error; the gap to forward error is κ.

Front: What does a Hadamard well-posed problem require? Back: Existence, uniqueness, and continuous dependence on the data.

Front: Which clause do discrete ill-posed problems violate? Back: Continuous dependence: σ_i decays smoothly to the noise floor with no spectral gap.

Front: Picard condition Back: |u_i^T b| must decay faster than σ_i so the ratios stay bounded.

Front: Tikhonov filter factor Back: f_i = σ_i² / (σ_i² + λ²), a smooth soft truncation of each mode.

Front: Effect of Tikhonov on the spectrum of A^T A Back: Adds λ² to every eigenvalue, capping the condition number at (σ_max² + λ²)/λ².

Front: Bayesian reading of the Tikhonov penalty with L = I Back: A Gaussian prior x ~ N(0, 1/(2λ²) I); the solution is the MAP estimate.

Front: What do the two axes of the L-curve show? Back: Solution norm ||x_λ|| against residual norm ||Ax_λ - b||, both on log scales.

Front: Where on the L-curve does the chosen λ sit? Back: At the corner of maximum curvature, balancing noise amplification against bias.

Front: Generalized cross-validation objective Back: ||Ax_λ - b||² / (m - trace(H_λ))², minimized over λ.

Front: Typical scaling rule for a good λ Back: λ on the order of the data noise level, always reported relative to σ_max.

Front: How to solve a Tikhonov problem with the tools from lesson 2.1 Back: Stack [A; λL] and [b; 0] into one least-squares problem and apply QR.

Front: Why is the unregularized Hilbert-matrix solution not a baseline? Back: Its error scales like κ·δ, which for κ ≈ 1.7e16 and δ = 1e-6 destroys every digit.