Example number
94
Example slug
example_94_conditioning_small_perturbations_big_solution_changes
Background

The condition number $\kappa(A) = \|A\| \|A^{-1}\|$ was formally introduced by John von Neumann and H. H. Goldstine (1947) to quantify how sensitively solutions of $Ax = b$ depend on perturbations in $A$ or $b$. They proved: relative solution error is bounded by $\kappa(A)$ times relative input error. Alan Turing (1948) and later James Wilkinson (1961) developed backward error analysis, proving that the error from finite-precision arithmetic is equivalent to solving a nearby problem $(A + \Delta A)x = b + \Delta b$ where $\|\Delta A\|/\|A\|, \|\Delta b\|/\|b\| \approx \epsilon$ (machine precision). By the 1960s, practitioners recognized that ill-conditioned systems are unsolvable in practice—no algorithm can reliably solve them. The singular value decomposition (SVD) and QR factorization emerged as solutions: both reveal and exploit the numerical rank without amplifying conditioning. By the 1980s, LAPACK encoded these principles: always check conditioning before solving; use SVD if $\kappa(A)$ is large; regularize instead of inverting. In modern ML (2010s+), ill-conditioning is ubiquitous: linear regression on correlated features ($\kappa \sim 10^6$), deep learning Hessians ($\kappa \sim 10^4$), Gaussian processes with RBF kernels ($\kappa \sim 10^{12}$). Yet many practitioners ignore it, leading to mysterious training failures, poor generalization, and numerical instabilities. Understanding conditioning is the bridge between linear algebra and ML practice.

Purpose

Understand conditioning ($\kappa(A)$): the fundamental property that controls solution sensitivity to input perturbations. Learn the perturbation theorem: small relative errors in $b$ are amplified by $\kappa(A)$ when solving $Ax = b$. Ill-conditioned problems ($\kappa(A) \gg 1$) are numerically fragile (tiny input noise → large output errors); well-conditioned problems ($\kappa(A) \approx 1$) are robust. Discover why ill-conditioning is endemic to ML: feature correlation, polynomial features, and kernel approximations all produce $\kappa(A) \in [10^6, 10^{12}]$. Learn to recognize ill-conditioning early (via eigenvalue ratios, covariance analysis) and apply cures (standardization, regularization, better algorithms). Understand that choosing the right factorization (SVD, QR, Cholesky) can mitigate but not cure ill-conditioning; the root problem is the data, not the algorithm.

Problem

Solve Ax=b, perturb b, and measure solution sensitivity; compare to cond(A).

Solution (Math)

Perturbation bound: $\|\Delta x\|/\|x\| \lesssim \kappa(A)\|\Delta b\|/\|b\|$. Ill-conditioned problems amplify noise.

We use:

  • Data matrix $X\in\mathbb{R}^{n\times d}$ (rows are examples).
  • Vectors are column vectors by default.
  • $\|x\|_2$ is Euclidean norm; $\langle x,y\rangle=x^Ty$.
Solution (Python)

import numpy as np

A = np.array([[1., 0.],
              [0., 1e-6]])
b = np.array([1., 1.])
db = np.array([0., 1e-6])

x1 = np.linalg.solve(A, b)
x2 = np.linalg.solve(A, b+db)

rel_db = np.linalg.norm(db)/np.linalg.norm(b)
rel_dx = np.linalg.norm(x2-x1)/np.linalg.norm(x1)

print("cond(A):", np.linalg.cond(A))
print("rel_db:", rel_db)
print("rel_dx:", rel_dx)
Code Introduction

This section demonstrates conditioning ($\kappa(A)$) and its impact on solution sensitivity. We construct an ill-conditioned matrix, perturb the right-hand side $b$, and verify the perturbation theorem: small relative errors in $b$ are amplified by $\kappa(A)$.

The Conditioning Number:

For a matrix $A$, the condition number measures sensitivity to perturbations: \[ \kappa_2(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} = \frac{\sigma_1}{\sigma_d} \] where $\sigma_i$ are singular values (largest to smallest). Interpretation: - $\kappa \approx 1$: Well-conditioned. Small perturbations → small solution changes. - $\kappa \sim 10^4$: Moderately ill-conditioned. Accuracy reduced by ~4 orders of magnitude. - $\kappa \sim 10^{14}$: Severely ill-conditioned. Nearly all accuracy lost on 64-bit precision.

Perturbation Theorem:

If $\Delta b$ perturbs $b$, the solution perturbation $\Delta x$ satisfies: \[ \frac{\|\Delta x\|}{\|x\|} \leq \kappa(A) \frac{\|\Delta b\|}{\|b\|}. \]

This bound is tight—ill-conditioned matrices can (and do) achieve near-worst-case amplification.

Example: A 2×2 Diagonal Matrix:

Consider: \[ A = \begin{pmatrix} 1 & 0 \\ 0 & 10^{-6} \end{pmatrix}. \]

This matrix is diagonal (easy to solve), but extremely ill-conditioned: \[ \sigma_1 = 1, \quad \sigma_d = 10^{-6}, \quad \kappa_2(A) = 10^6. \]

For the right-hand side $b = [1, 1]^\top$ and a tiny perturbation $\Delta b = [0, 10^{-6}]^\top$: - Relative perturbation in $b$: $\frac{\|\Delta b\|}{\|b\|} = \frac{10^{-6}}{\sqrt{2}} \approx 0.7 \times 10^{-6}$ (0.00007%). - Relative change in solution: $\frac{\|\Delta x\|}{\|x\|} \approx \kappa(A) \times 0.7 \times 10^{-6} = 10^6 \times 0.7 \times 10^{-6} \approx 0.7$ (70%!).

Tiny input noise (0.00007%) → 70% output error. This is amplification by the condition number.

Code Walkthrough:

import numpy as np

# Construct an ill-conditioned diagonal matrix
A = np.array([[1., 0.],
              [0., 1e-6]])

# Nominal RHS
b = np.array([1., 1.])

# Perturbation (tiny, in second component)
db = np.array([0., 1e-6])

# Solve the two problems
x1 = np.linalg.solve(A, b)
x2 = np.linalg.solve(A, b + db)

# Compute relative perturbations
rel_db = np.linalg.norm(db) / np.linalg.norm(b)
rel_dx = np.linalg.norm(x2 - x1) / np.linalg.norm(x1)

# Compute condition number
cond_A = np.linalg.cond(A)

print("cond(A):", cond_A)           # Output: 10^6
print("rel_db:", rel_db)             # Output: ~7e-7 (0.00007%)
print("rel_dx:", rel_dx)             # Output: ~0.7 (70%)
print("Amplification factor:", rel_dx / rel_db)  # Output: ~10^6

Output Interpretation:

  • cond(A) = 1e6: Severe ill-conditioning. Condition number of 1 million.
  • rel_db = 7e-7: The perturbation is tiny (0.00007% of $b$’s magnitude).
  • rel_dx = 0.7: The solution changes by 70% (relative error).
  • Amplification: rel_dx / rel_db ≈ 1e6: The perturbation is amplified by the condition number.

Fundamental Principle:

For any matrix $A$ and any perturbation $\Delta b$, the solution perturbation is bounded by $\kappa(A)$. Ill-conditioned systems cannot be solved accurately. Recognize ill-conditioning early (via condition number, singular values, data correlation) and apply cures: standardization, feature selection, regularization, or better algorithms.

What This Reveals:

  • Ill-conditioning is inherent to the problem, not the algorithm. No solver can fix it.
  • Forward error (solution error) can be orders of magnitude worse than backward error (arithmetic precision).
  • Understanding conditioning transforms debugging: training difficulty → check conditioning; generalization issues → regularize.
Numerical Implementation Details
  • Condition number ($\ell_2$ norm): $\kappa_2(A) = \sigma_1 / \sigma_d$ (ratio of largest to smallest singular values). Computed via SVD: cond = U.shape[0] / U.shape[1] (approximate) or np.linalg.cond(A) (exact, uses SVD).
  • Perturbation bound (norm-wise): For perturbed RHS $b' = b + \Delta b$ with $\|\Delta b\| \leq \epsilon \|b\|$, the solution error satisfies $\|\Delta x\| / \|x\| \leq \kappa(A) \epsilon + O(\epsilon^2)$.
  • Componentwise condition number: Relative error in individual components can be much larger than norm-wise. The condition number matrix $C$ (Skeel’s condition number) is component-wise bound; use when individual variable accuracy matters.
  • Estimating condition number: np.linalg.cond(A) costs $O(d^3)$ (full SVD). For large matrices, use np.linalg.cond(A, 'fro') (Frobenius norm, cheaper) or estimate via iterative methods.
  • Threshold for ill-conditioning: $\kappa(A) > 10^{14}$ (near machine precision) is “effectively singular” on 64-bit doubles ($\epsilon \approx 2.22 \times 10^{-16}$). $\kappa(A) > 10^8$ is severely ill-conditioned. $\kappa(A) > 10^4$ is ill-conditioned for most applications.
  • Regularization via Tikhonov: Solve $(A^T A + \lambda I)^{-1} A^T b$ (ridge regression). This shifts small singular values up, reducing condition number: $\kappa(A^T A + \lambda I) \approx \sqrt{\kappa(A^T A)} / \sqrt{\lambda}$ for appropriate $\lambda$.
  • Algorithm comparison: SVD always reveals conditioning (shows all singular values). LU hides it (pivoting can mask). QR exposes it via $R$. Cholesky for SPD reveals conditioning via factor norm growth.
  • Preconditioning: Solve $P^{-1} A x = P^{-1} b$ where $P$ is chosen so $P^{-1} A$ is better conditioned. Examples: diagonal scaling, incomplete factorizations. Cheap in iterative solvers; direct solvers benefit less.
What This Example Demonstrates
  • Perturbation theorem: Relative solution change is bounded: $\frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \frac{\|\Delta b\|}{\|b\|}$. Small perturbations in $b$ can produce large changes in $x$ if $\kappa(A)$ is large.
  • Conditioning number as sensitivity: $\kappa(A)$ measures the worst-case amplification factor. $\kappa(A) = 10^6$ means a $10^{-8}$ relative error in $b$ can produce a $10^{-2}$ relative error in $x$ (amplification of $10^6$).
  • Ill-conditioning is data, not algorithm: No algorithm can fix an ill-conditioned problem; the problem is inherent to $A$. Robust algorithms (SVD, QR) reveal this numerically; unstable algorithms (normal equations) hide it temporarily.
  • Backward error analysis: Finite-precision arithmetic introduces error equivalent to solving $(A + \Delta A)x = b + \Delta b$ with $\|\Delta A\|/\|A\| \approx \epsilon \cdot \kappa(A)$. This explains why ill-conditioned systems lose accuracy even on well-implemented solvers.
  • Regularization cures conditioning: Adding $\lambda I$ shifts eigenvalues, reducing $\kappa(A + \lambda I)$. Ridge regression combines statistical regularization (prevent overfitting) with numerical regularization (improve conditioning).
  • Recognizing ill-conditioning: Large condition numbers appear in: correlated features (feature matrix $X$), polynomial regression (Vandermonde matrix), kernel approximations (RBF kernel matrix), deep learning (Hessian/Fisher).
  • Algorithm choice matters: SVD/QR are stable and reveal conditioning; LU with partial pivoting is less stable; normal equations hide conditioning (condition number squares). Cholesky for SPD is stable but doesn’t reduce conditioning.
  • ML consequence: Ill-conditioned models are fragile to data noise, training is slower (learning rate must be tiny), generalization is poor, hyperparameter tuning is sensitive. Practitioners often misdiagnose as “bad learning rate” when the root cause is ill-conditioning.
Notes

Part 1: Condition Number and Perturbation Sensitivity

For nonsingular $A \in \mathbb{R}^{d \times d}$, the condition number is: \[ \kappa(A) = \|A\| \|A^{-1}\|. \] For the $\ell_2$ norm (spectral norm), this simplifies to the singular value condition number: \[ \kappa_2(A) = \frac{\sigma_1}{\sigma_d} \] where $\sigma_1 \geq \cdots \geq \sigma_d > 0$ are singular values. Interpretation: $\kappa(A)$ is the ratio of the largest to smallest singular value—the “spread” of singular values.

Perturbation theorem: If $\Delta b$ is a small perturbation to $b$, and $\Delta x$ is the resulting perturbation to the solution $x = A^{-1} b$, then: \[ \frac{\|\Delta x\|}{\|x\|} \leq \kappa(A) \frac{\|\Delta b\|}{\|b\|} + O\left(\kappa(A) \frac{\|\Delta A\|}{\|A\|}\right). \] Well-conditioned: $\kappa(A) \approx 1$. Small perturbations → small solution changes. Example: orthogonal $Q$, where $\kappa(Q) = 1$.

Ill-conditioned: $\kappa(A) \gg 1$. Small perturbations → potentially large solution changes. Example: nearly singular $A$.

Part 2: Finite-Precision Arithmetic and Backward Error

When solving $Ax = b$ on a computer with machine precision $\epsilon \approx 10^{-16}$ (double precision), the computed solution $\hat{x}$ satisfies: \[(A + \Delta A) \hat{x} = b + \Delta b,\] where $\|\Delta A\| / \|A\| \approx \epsilon \cdot \kappa(A)$ and $\|\Delta b\| / \|b\| \approx \epsilon$ (backward error analysis, Wilkinson 1961). This means: - Well-conditioned ($\kappa \approx 1$): $\|\Delta A\| / \|A\| \approx \epsilon$; accuracy is near machine precision. - Moderately ill-conditioned ($\kappa \sim 10^4$): $\|\Delta A\| / \|A\| \approx 10^{-12}$; accuracy reduced to $\sim 10^{-12}$. - Severely ill-conditioned ($\kappa \sim 10^{14}$): $\|\Delta A\| / \|A\| \approx 1$; essentially all accuracy is lost.

Conclusion: No algorithm can produce better accuracy than $O(\epsilon \cdot \kappa(A) \cdot \|x\|)$ on ill-conditioned problems. The problem is data-limited, not algorithm-limited.

Part 3: Recognizing and Mitigating Ill-Conditioning

Sources of ill-conditioning in ML: 1. Correlated features: $X = [x_1, x_2, \ldots, x_d]$ with $\text{corr}(x_i, x_j) \approx 1$ for $i \ne j$ → singular values decay rapidly → $\kappa(X) \gg 1$. 2. Polynomial features: $[1, t, t^2, \ldots, t^p]$ (Vandermonde matrix) with $t \in [0, 1]$ → exponentially decaying singular values → $\kappa \sim 10^{2p}$. 3. Kernel matrices: RBF kernel $K_{ij} = \exp(-\gamma \|x_i - x_j\|^2)$ → slowly decaying spectrum → $\kappa \sim 10^{8}$ or more, depending on $\gamma$ and data spread. 4. Deep learning Hessians: Neural network Hessians are often severely ill-conditioned ($\kappa \sim 10^4$ or worse), especially near local minima. 5. Overparameterization: More parameters than data → rank-deficiency or near-singularity.

Cures: 1. Standardization: Scale features to zero mean and unit variance. Reduces (but doesn’t eliminate) $\kappa(X)$. 2. Feature selection/PCA: Remove correlated features or project to principal components. Reduces condition number dramatically. 3. Regularization (Ridge/Tikhonov): Add $\lambda I$ to normal equations or Hessian. Shifts small singular values up → improves conditioning. Fundamental technique in ML. 4. Better algorithms: SVD instead of normal equations; Cholesky for SPD; QR for least squares. These are more stable than LU or direct inversion. 5. Preconditioning: In iterative methods, solve $P^{-1}A x = P^{-1} b$ with $P$ chosen so $P^{-1}A$ is better conditioned.

Why This Matters for ML

  • Training difficulty: Ill-conditioned models require tiny learning rates (gradient steps must be small to avoid divergence). Training is orders of magnitude slower.
  • Generalization: Ill-conditioned models have large sensitivity to noise → overfitting risk increases. Regularization simultaneously improves generalization and conditioning.
  • Hyperparameter sensitivity: Ill-conditioned Hessians make learning rates, batch sizes, and other hyperparameters extremely sensitive. Tuning becomes painful.
  • Second-order optimization: Newton’s method solves $H \delta w = -g$ (Hessian $H$, gradient $g$). Ill-conditioned $H$ makes Newton steps unreliable; trust-region and damping are essential.
  • Uncertainty quantification: Bayesian posteriors in ill-conditioned models are difficult to sample from or approximate; covariance structure is hard to represent.
  • Federated learning: Ill-conditioning makes optimization algorithms (SGD, coordinate descent) slow to converge; communication costs explode.

ML Examples and Patterns

  1. Linear regression on correlated features: $X \in \mathbb{R}^{100 \times 10}$ with $\kappa(X) \sim 10^6$ (high multicollinearity). Normal equations produce wildly inaccurate weights. Ridge regression ($\lambda \in [0.1, 1.0]$) improves conditioning to $\kappa \sim 10^3$; generalization improves, solution is stable.
  2. Polynomial regression: Fit polynomial degree $p = 10$ to $n = 20$ points over $[0, 1]$. Vandermonde matrix has $\kappa \sim 10^{20}$. Solution is essentially random. Reduce polynomial degree or use orthogonal polynomial basis (Chebyshev, Legendre) to fix.
  3. Gaussian process with RBF kernel: Covariance matrix $K + \sigma^2 I$ with $\kappa(K) \sim 10^{12}$. Adding noise ($\sigma^2 I$) helps, but inducing point methods or sparse approximations are necessary for scalability and stability.
  4. Neural network Hessian at convergence: Second-order methods (natural gradient, K-FAC) require solving Hessian systems. Ill-conditioned Hessian (many small eigenvalues) makes Newton steps unreliable. Damping ($H + \lambda I$) is essential.
  5. Federated ridge regression: Clients solve local ridge regression with $\lambda$ chosen for both regularization and conditioning. Ill-conditioning increases communication rounds; conditioning must be considered in algorithm design.

Connection to Linear Algebra Theory

  • Spectral theorem for SPD matrices: $A = Q\Lambda Q^T$ (orthogonal $Q$, diagonal $\Lambda$ of eigenvalues). Condition number is $\kappa = \lambda_{\max} / \lambda_{\min}$ (ratio of largest to smallest eigenvalue).
  • Singular value decomposition: $A = U\Sigma V^T$ where $\Sigma = \text{diag}(\sigma_1, \ldots, \sigma_d)$. Condition number: $\kappa_2(A) = \sigma_1 / \sigma_d$. SVD exposes conditioning numerically.
  • QR factorization: $A = QR$ where $Q$ orthogonal, $R$ upper triangular. $\kappa(A) = \kappa(R)$ (same as $R$, since $\kappa(Q) = 1$). Solving $Rx = Q^T b$ avoids amplification of conditioning present in normal equations.
  • Gram matrix: $G = X^T X$ has $\kappa(G) = \kappa(X)^2$ (condition number squares). This is why normal equations $(X^T X)^{-1} X^T y$ are numerically unstable for ill-conditioned $X$.

Numerical and Implementation Notes

  • Always compute and check conditioning before solving. If $\kappa(A) > 10^8$, reconsider the problem (standardize data, use regularization, switch algorithms).
  • For least squares, use np.linalg.lstsq(X, y) (SVD-based, reveals conditioning) instead of np.linalg.solve(X.T @ X, X.T @ y) (condition number squared).
  • Precompute $\kappa(A)$ once; if large, cache the SVD or use it to decide regularization strength.
  • In iterative algorithms, monitor $\kappa$ of Hessian/covariance; if growing, increase damping/regularization.

Numerical and Shape Notes

  • Shapes: $A \in \mathbb{R}^{d \times d}$ (square), $b, x \in \mathbb{R}^d$ (vectors), $\Delta b, \Delta x \in \mathbb{R}^d$ (perturbations).
  • Singular values: $\sigma_1 \geq \cdots \geq \sigma_d \geq 0$ (non-increasing). Condition number $\kappa = \sigma_1 / \sigma_d$ (ratio).
  • For $m \times d$ data matrix $X$ with $m \geq d$: $\kappa_2(X) = \sigma_1(X) / \sigma_d(X)$. Normal equations form $m \times m$ Gram matrix: $\kappa(X^T X) = \kappa(X)^2$.

Pedagogical Significance

Conditioning is the bridge between linear algebra and numerical practice in ML. It explains why theoretically correct algorithms (normal equations, direct matrix inversion) fail in practice on real data. Students learn that structure matters: recognizing correlation, redundancy, and near-singularity enables smart algorithm and regularization choices. Understanding conditioning transforms debugging: “bad learning rate” becomes “ill-conditioned Hessian”→add damping/regularization. This example teaches mathematical maturity: understanding limits of computation, when algorithms fail, and how to diagnose and fix problems systematically.

Connection to Broader Examples
  • Least squares (Ex 92, 93): Normal equations $(X^T X)^{-1} X^T y$ have condition number $\kappa(X^T X) = \kappa(X)^2$. Conditioning of Gram matrix is squared conditioning of data matrix. SVD/Cholesky solve this by working with $X$ directly.
  • SVD (Ex 90): Reveals all singular values, exposing conditioning. SVD is the most stable approach; condition number directly visible as $\sigma_1 / \sigma_d$.
  • PCA (Ex 91): Covariance matrix eigenvalues determine conditioning. Ill-conditioned covariance (widely varying variance) produces unreliable PC estimates; regularization helps.
  • Power iteration (Ex 88): Eigenvalue separation ($\lambda_1 / \lambda_2$) determines convergence rate. Ill-conditioning (clustered eigenvalues) slows convergence exponentially.
  • Cholesky (Ex 93): SPD matrix conditioning determines solution accuracy. Ill-conditioning doesn’t break Cholesky (still backward stable), but solution is inaccurate. Add regularization $\lambda I$ to improve conditioning.
  • Orthogonality (Ex 86): Orthogonal matrices have $\kappa(Q) = 1$ (perfectly conditioned). Least squares via QR exploits this: conditioning of $R$ from $X = QR$ is same as $X$, not squared as in normal equations.
  • Rank/nullspace (Ex 87): Numerical rank depends on conditioning and singular value threshold. Ill-conditioned matrix has gradual decay of singular values; choosing numerical rank is ambiguous.
  • Ridge regression (ML): Fundamental application: regularization improves conditioning and prevents overfitting. Parameter $\lambda$ controls both bias and conditioning—double duty.

Comments