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.

  • $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Nov 12 '19 at 20:13
  • $\begingroup$ @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$. $\endgroup$ – Federico Poloni Nov 12 '19 at 20:24
  • $\begingroup$ Ah, fair, yes. But the point is still that "solution $x=0$" is not a useful indicator of whether the problem is ill-posed. $\endgroup$ – Wolfgang Bangerth Nov 13 '19 at 19:48
  • $\begingroup$ @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. $\endgroup$ – Federico Poloni Nov 13 '19 at 23:09
  • $\begingroup$ 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$? $\endgroup$ – Wolfgang Bangerth Nov 14 '19 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.