# “Geometry of ill-conditioning” for least-squares problems

It is an idea that dates back to Demmel, 1987 that the condition number of a problem is often related to the distance to the closest ill-posed problems. In Section 3 of the above paper, the author cites as examples linear systems/matrix inversion (1/condition number = relative distance to the closest singular matrix), polynomial root-finding, and eigenvalue calculation (1/condition number = relative distance to the closest problem with double roots).

Can the condition number of least-squares problems $$\min \|Ax-b\|$$ be interpreted in the same sense?

The first idea that comes to mind is considering 'ill-posed problems' as those with solution $$x=0$$ and those in which $$A$$ does not have full column rank, but in this case I cannot make much sense of the $$\kappa(A)^2$$ that appears in the formulas.

• No, the problem would be ill-posed if $A$ does not have full row rank. In that case, $\kappa(A^TA)$ is infinite because $A^TA$ has a zero eigenvalue. – Wolfgang Bangerth Nov 12 '19 at 20:13
• @WolfgangBangerth I guess this is just a matter of agreeing on a shape for $A$. Assume $A$ tall thin, for this question; then the nontrivial rank to check is the column rank, which corresponds to the singularity of $A^TA$. – Federico Poloni Nov 12 '19 at 20:24
• Ah, fair, yes. But the point is still that "solution $x=0$" is not a useful indicator of whether the problem is ill-posed. – Wolfgang Bangerth Nov 13 '19 at 19:48
• @WolfgangBangerth Why do you think so? If $b$ is orthogonal to $\operatorname{Im} A$, then the condition number of the least-squares problem is $\infty$: a tiny relative change in the input data $b$ produces a huge relative change in the solution $x$. That's pretty much the definition of an ill-posed problem. – Federico Poloni Nov 13 '19 at 23:09
• Yes, I don't disagree :-) But what does this have to do with the proposed definition that the problem is considered ill-posed if it has solution $x=0$? – Wolfgang Bangerth Nov 14 '19 at 2:03