2

I'm a little unsure about how to classify conditioning issues with solving least squares equations via the normal equations approach. I'm hoping to get verification that what I say below is correct, and have it pointed out if it is wrong. There seems to be two possible issues in terms of conditioning.

  1. A has a high condition number. Then I'm pretty sure that $\kappa(A^TA) = \kappa(A)^2$, so thus we have even a worse situation in solving $A^TAx = A^Tb$. Is this true?

  2. The textbook I am looking at seems to be more concerned with $A^TA$ being numerically singular. For example if:

$A = \left( \begin{array}{cc} 1 & 1 \\ 0 & \epsilon \\ \epsilon & 0 \end{array} \right) $

Then we have

$A^TA = \left( \begin{array}{cc} 1+\epsilon^2 & 1 \\ 1 &1+\epsilon^2 \end{array} \right) $

The textbook then says that is $\epsilon$ is small enough then we will run into problems with roundoff error where the matrix will be numerically singular. Is this technically an issue of conditioning as well, or would this fall under some other "category".

Fractal20
  • 1,479
  • 1
  • 13
  • 30
  • In least squares, there's always some $\kappa(A)^2$. If you look on the perturbation bounds (relation between the forward and backward errors), the squared condition number represents the sensitivity of the error with respect to the norm of the residual. So generally, the forward error associated with least squares problems with large residuals is more sensitive. The example just shows that it is generally a bad idea to form the normal equations explicitly. – Algebraic Pavel Dec 16 '13 at 14:07

1 Answers1

2

If $\epsilon$ is "small enough" then the columns of $A$ become "almost" identical, and so "almost" perfectly collinear. Then the $A^TA$ matrix becomes "almost" a matrix of $1$'s, and hence "almost" non-ivertible. So this is too an issue of near-perfect multicollinearity, which is linked to a high condition number. In other words, it is the same issue.

Alecos Papadopoulos
  • 10,388