When solving a linear system $Ax = b$, the accuracy of the solution depends heavily on the matrix's condition number, denoted as $\kappa(A)$. Intuitively, the condition number measures how much a tiny error or numerical perturbation in the input data can blow up in the final solution. If a matrix has a condition number of $10^3$, a rounding error in the 6th decimal place can corrupt the solution up to the 3rd decimal place.
In many real-world applications—ranging from 3D computer vision to training physics-informed neural networks—we encounter overdetermined systems where we seek to minimize a residual, formulated as a least-squares problem:
$$\min_x \|Ax - b\|^2$$
The textbook method to solve this is to set the gradient to zero, yielding the normal equations:
$$A^T A x = A^T b$$
While algebraically straightforward, this transformation conceals a catastrophic numerical penalty: it squares the condition number of the system. If the original matrix has a condition number $\kappa(A)$, the new system matrix $A^T A$ has a condition number of $\kappa(A)^2$.
As noted by Demmel et al., Zeng et al., and Mohr et al., this squaring effect drastically amplifies numerical instability. For example, in standard 32-bit single-precision floating-point arithmetic, we only have about 7 decimal digits of precision. If $\kappa(A) = 10^4$, the condition number of the normal equations skyrockets to $\kappa(A^T A) = 10^8$. At this point, the numerical noise completely overwhelms the signal, rendering the system unsolvable in single precision. Consequently, the direct solution of normal equations is generally discouraged in numerical computing, as highlighted by Meier et al..
The Square Root Remedy: Working Directly with the Jacobian
To avoid squaring the condition number, modern algorithms bypass the formation of $A^TA$ entirely. Instead of squaring the operator and then solving, they operate directly on the original matrix $A$ (often a Jacobian matrix in optimization contexts) using orthogonal factorizations like the QR decomposition.
Consider decomposing $A$ into an orthogonal matrix $Q$ (where $Q^TQ = I$) and an upper triangular matrix $R$:
$$A = QR$$
Because orthogonal matrices preserve geometric lengths and do not amplify noise, the condition number of $Q$ is exactly 1. Consequently, the condition number of the remaining triangular matrix $R$ is identical to the original matrix: $\kappa(R) = \kappa(A)$.
Substituting this into the least-squares objective transforms the problem:
$$\|Ax - b\|^2 = \|QRx - b\|^2 = \|Rx - Q^T b\|^2$$
We can now solve the system $Rx = Q^T b$ directly via back-substitution. Because we never formed $A^TA$, the condition number governing our computation remains $\kappa(A)$ rather than $\kappa(A)^2$.
This "square root" approach yields massive practical advantages. For instance, in large-scale 3D reconstruction, Demmel et al. developed a Square Root Bundle Adjustment ($\sqrt{\text{BA}}$) framework. By using QR-decomposition-based nullspace marginalization instead of the traditional Schur complement (which forms a Hessian matrix and thus squares the condition number), the authors achieved a breakthrough: they solved massive optimization problems using single-precision (32-bit) floats with the exact same accuracy as standard double-precision solvers, but at twice the computational speed. Similarly, Chandrasekaran et al. leveraged QR factorization to design a stable algorithm for indefinite linear least-squares problems, overcoming the inherent instability of the traditional $A^TJA$ normal equation formulation.
Squaring in Deep Learning: Minimax Games for Neural PDEs
The penalty of condition number squaring is not confined to classical linear algebra; it also severely limits deep learning models that embed physical laws. Physics-Informed Neural Networks (PINNs) train a neural network $u_\theta$ to solve a differential equation $\mathcal{D}u = f$ by minimizing the squared residual over a set of collocation points:
$$\mathcal{L}(\theta) = \|\mathcal{D}u_\theta - f\|^2$$
As explained by Zeng et al., minimizing the square of a differential equation's residual is the continuous analogue of forming the normal equations. This operation squares the condition number of the underlying differential operator, creating an incredibly rugged optimization landscape characterized by sharp, ill-conditioned gradients that standard gradient-descent optimizers struggle to navigate.
To solve this, Zeng et al. introduced Competitive PINNs (CPINNs). Instead of squaring the residual, the authors reframed PDE training as an adversarial zero-sum game between the network solver $u$ and a discriminator $v$:
$$\min_u \max_v \left( \langle \mathcal{D}u - f, v \rangle - \frac{1}{2}\|v\|^2 \right)$$
In this minimax formulation, the discriminator acts as a localized probe that identifies where the PDE residual is large, while the solver attempts to minimize those discrepancies. Crucially, the objective depends linearly on the differential operator $\mathcal{D}u$ rather than quadratically. By avoiding the squared residual loss, CPINNs prevent condition number amplification, allowing gradient-based optimization to achieve up to four orders of magnitude higher accuracy than traditional PINNs.
Managing Intrinsic Ill-Conditioning
While bypassing the normal equations prevents us from worsening the condition number, what happens if the baseline matrix $A$ is intrinsically ill-conditioned from the start? This frequently occurs when dealing with structured matrices, such as the Vandermonde matrices common in statistical signal processing (Elkhalil et al.) or empirical design matrices constructed from finite, noisy samples in reinforcement learning (Avila Pires et al.). When $A$ is nearly singular, even direct solvers or sparse recovery algorithms like those studied by Huang et al. can break down.
In these extreme scenarios, researchers rely on regularization and perturbation theory to restore stability:
- Random Perturbations: A remarkable theoretical result by Van Vu demonstrates that adding a small amount of random noise to an arbitrary, highly ill-conditioned matrix makes the resulting matrix well-conditioned with high probability. This explains why naturally occurring systems rarely exhibit worst-case numerical instability.
- Smoothed Analysis: Expanding on this intuition, Shah et al. provided a smoothed analysis of condition numbers under low-rank perturbations, offering a mathematical foundation for why injecting structured perturbations can stabilize large-scale linear solvers.
- Proximal Inversion: From an optimization perspective, Rondepierre et al. showed that applying the Proximal Point Algorithm to matrix inversion acts as an implicit regularizer, iteratively guiding ill-conditioned systems toward stable, noise-resilient solutions.
Ultimately, whether by adding regularizing perturbations to an inherently ill-conditioned operator or by utilizing QR and minimax formulations to avoid squaring the condition number, the goal remains the same: preserving the fidelity of our data by keeping the condition number as small as mathematically possible.
Key Foundational Work
A Stable and Efficient Algorithm for the Indefinite Linear Least-Squares Problem (1998) — contributed 4 concept elements to this direction.
The condition number of a randomly perturbed matrix (2007) — contributed 1 concept elements to this direction.