Preconditioning and Spectral Conditioning

Why Conditioning and Statistical Accuracy Are Different

Inverse problems can be difficult for two distinct reasons. A numerical algorithm may converge slowly because the forward operator has singular values spread across a wide range. Separately, an estimator may be statistically unstable because noise is amplified in directions associated with small singular values. Preconditioning is often used to address the first issue, but it does not automatically resolve the second.

The distinction is easiest to see in a finite-dimensional linear model. Let \(A\) be an \(m\)-by-\(p\) matrix with full column rank, and suppose \(y=Ax+\varepsilon\), where \(x\in\mathbb{R}^p\) is the unknown parameter vector and \(E[\varepsilon]=0\), \(\operatorname{Cov}(\varepsilon)=\Sigma\). A right preconditioner is an invertible \(p\)-by-\(p\) matrix \(P\). Writing \(x=Pz\) changes the forward matrix from \(A\) to \(AP\). This can make the new coordinates numerically more convenient; whether it changes the statistical estimator depends on what objective is solved in those coordinates.

The Gram matrix of the transformed operator is \((AP)^T(AP)=P^TA^TAP\). Its eigenvalues are the squared singular values of \(AP\). Thus a well-chosen \(P\) can bring these eigenvalues closer together and reduce the condition number of the system an algorithm must solve. If normal equations are used, their condition number is the square of the condition number of the corresponding design matrix.

How a Right Preconditioner Changes the Spectrum

A preconditioner does not generally multiply every singular value by the same constant. It changes the directions as well as the lengths represented by the operator. The following bounds give a general comparison. They are useful for understanding what is possible, but they do not guarantee that an arbitrary preconditioner improves conditioning.

Proof. For any vector \(v\), \(\|APv\|_2\leq \|A\|_2\|P\|_2\|v\|_2\). Taking the supremum over unit vectors gives \(s_{\max}(AP)\leq s_{\max}(A)s_{\max}(P)\). Also, for every unit vector \(v\), \(\|APv\|_2\geq s_{\min}(A)\|Pv\|_2\geq s_{\min}(A)s_{\min}(P)\). Taking the infimum gives \(s_{\min}(AP)\geq s_{\min}(A)s_{\min}(P)\). Dividing these inequalities yields the upper bound. For the lower bound, apply that upper bound to \(A=(AP)P^{-1}\): \(\kappa_2(A)\leq\kappa_2(AP)\kappa_2(P^{-1})=\kappa_2(AP)\kappa_2(P)\). Rearranging proves the result. \(\square\)

The choice of preconditioner matters. A matrix that scales one direction helpfully can scale another in the wrong direction. Conditioning is a property of the pair consisting of the operator and the chosen coordinates, not a guarantee attached to the word “preconditioner.”

When Reparameterization Leaves the Estimator Unchanged

Suppose the task is unregularized least squares and \(A\) has full column rank. The unique least-squares estimator is \(\hat{x}=(A^TA)^{-1}A^Ty\). Reparameterizing with \(x=Pz\) and minimizing \(\|APz-y\|_2^2\) changes the matrix in the optimization problem but not the fitted estimator in the original coordinates.

Proof. The normal equations in the \(z\) coordinates are \(P^TA^TAP\hat{z}=P^TA^Ty\). The matrix \(P^TA^TAP\) is invertible because \(A\) has full column rank and \(P\) is invertible. Its inverse is \(P^{-1}(A^TA)^{-1}P^{-T}\), as is verified by multiplication. Therefore

Thus the exact estimator in the original coordinates is unchanged, even though the transformed problem may be easier for an iterative solver. \(\square\)

This invariance has a statistical consequence. If \(E[\varepsilon]=0\), the estimator’s expectation, bias, and covariance are unchanged by an exact invertible reparameterization followed by an exact unregularized least-squares solution. For example, under \(\Sigma=\sigma^2I\), the covariance remains \(\sigma^2(A^TA)^{-1}\). Improved conditioning can help compute that estimator more reliably; it does not, by itself, add information to the data or reduce its statistical variance.

Regularization Can Change Bias and Variance

The invariance result depends on solving the same unregularized problem. If instead one minimizes \(\|APz-y\|_2^2+\lambda\|z\|_2^2\), the penalty in the original \(x\) coordinates is \(\lambda\|P^{-1}x\|_2^2\), not generally \(\lambda\|x\|_2^2\). The transformed problem can therefore define a different estimator, with different bias and variance.

Write \(H=A^TA+\lambda R\). Since \(H\) is symmetric and invertible, \(E[\hat{x}_R]=H^{-1}A^TAx\), so the bias is \(-\lambda H^{-1}Rx\). The estimator is a linear function of \(y\), with matrix \(H^{-1}A^T\); hence

These expressions show that a changed penalty may reduce variance in some directions while increasing bias. The overall mean squared error under squared Euclidean loss is \(\|E[\hat{x}_R]-x\|_2^2+\operatorname{tr}\{\operatorname{Cov}(\hat{x}_R)\}\). This is a statistical trade-off, not a consequence of conditioning alone.

For completeness, if \(H_z=P^TA^TAP+\lambda I\), then the estimator from the \(z\)-penalized problem is \(\hat{x}=P H_z^{-1}P^TA^Ty\). Its covariance is

The final factor is \(P^T\): the covariance of a linear map \(By\) is \(B\Sigma B^T\), and here \(B=P H_z^{-1}P^TA^T\). This form is symmetric, as a covariance matrix must be.

Left Preconditioning and a Common Pitfall

A left preconditioner acts on the equations or residuals rather than on the unknown coordinates. For a square nonsingular system \(Ax=y\), replacing the equation by \(QAx=Qy\), with invertible \(Q\), preserves the exact solution. For an overdetermined least-squares problem, however, minimizing \(\|Q(Ax-y)\|_2^2\) generally changes the objective to a weighted least-squares problem. It can then change the estimator’s bias and covariance. Applying a transformation to an iterative algorithm solely to solve the original objective is not the same as changing the objective itself.

Common mistake: “The preconditioner reduces the condition number, so it reduces the estimator’s variance.” This conclusion does not follow. Conditioning describes sensitivity of the numerical linear system to perturbations and affects algorithmic convergence and roundoff. Statistical variance is determined by the estimator’s map from the random data to the estimate, together with the noise covariance. An exact coordinate change that preserves the estimator leaves its statistical variance unchanged; a changed penalty may alter it, but also changes bias.

Preconditioning is valuable because a better-conditioned representation can make an inverse problem more tractable computationally. The crucial distinction is whether the method merely changes how the same estimator is computed or changes the estimator itself. In the first case, conditioning may improve without changing statistical risk. In the second, the resulting bias–variance trade-off must be evaluated on its own merits.