7

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.

Federico Poloni
  • 11,344
  • 1
  • 31
  • 59
  • 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 02:03
  • @WolfgangBangerth $b$ is orthogonal to $\operatorname{Im} A$ if and only if the solution is $0$, since the solution of the least-squares problem is the orthogonal projection of $b$ on $\operatorname{Im} A$. So problems with solution $x=0$ are one of the two cases in which the least-squares problem is ill-posed, the other being $\kappa(A)=0$. – Federico Poloni Nov 14 '19 at 07:22
  • Hm, but that's an extreme case. In general, the problem is already ill-posed if $b$ just has a component in the direction of Im $A$, and in that case the solution will not be zero. – Wolfgang Bangerth Nov 14 '19 at 14:08
  • @WolfgangBangerth I am not sure I understand. What do you mean with "$b$ just has a component in the direction of Im $A$"? The generic case? Why should the generic case of a least-squares problem be ill-posed? There are explicit expressions for the condition number of the LS problem (see for instance Chapter 18 in Trefethen-Bau), and they show that the condition number is finite if $\kappa(A) < \infty$ and $b$ is not perpendicular to Im $A$. – Federico Poloni Nov 14 '19 at 14:16
  • Let us continue this discussion in chat. – Federico Poloni Nov 14 '19 at 16:23

0 Answers0