9
$\begingroup$

It's shown (Yousef Saad, Iterative methods for sparse linear systems, p. 260) that $cond(A'A) \approx cond(A)^2$

Is this true for $AA'$ as well?

In case $A$ is $N\times M$ with $N \ll M$, I observe that $cond(A'A) \gg cond(AA')$

Does that mean formulation in terms of $AA'$ is preferable in this case?

$\endgroup$
  • 2
    $\begingroup$ You're comparing condition numbers of two matrices with vastly different sizes. Without an explanation of why, it seems like that comparison is probably not meaningful. Certainly, if you can accomplish what you need by using the much smaller matrix, you should (even if the conditioning were similar). $\endgroup$ – David Ketcheson Mar 5 '12 at 10:46
  • 1
    $\begingroup$ The new answer by Stefano M below is correct. Please read it and vote it up. $\endgroup$ – David Ketcheson Jul 15 '12 at 6:03
6
$\begingroup$

If $A\in\mathbb{R}^{N\times M}$ with $N<M$, then $$ \mathop{\mathrm{rank}}(A^TA) = \mathop{\mathrm{rank}}(AA^T) = \mathop{\mathrm{rank}}(A) \leq N < M $$ so that $A^TA \in \mathbb{R}^{M\times M}$ cannot be full rank, i.e. it is singular.

Accordingly the condition number is $\kappa_2(A^TA)=\infty$. Due to finite precision arithmetic, if you compute cond(A'A) in matlab you obtain a large number, not Inf.

$\endgroup$
  • $\begingroup$ @OscarB: the singular values of $A$ are just $N$, there is no such a thing as the $M$th singular value! Your derivation is correct, but please note that if $\sigma_i$, $i=1\dots N$ are the sv's of $A$, then $SS^T=\mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2)$, while $S^TS = \mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2, 0, \dots, 0)$ with $M-N$ trailing zeros. $\endgroup$ – Stefano M Jul 13 '12 at 22:41
8
$\begingroup$

Well, let’s look at why $A^TA$ has approximately the squared condition number of $A$. Using the SVD decomposition of $A=USV^T$, with $U \in \mathbb{R}^{N \times N}$, $S \in \mathbb{R}^{N \times M}$, $V \in \mathbb{R}^{M \times M}$, we can express $A^T A$ as

$A^T A=(USV^T)^T USV^T=VS^T U^T U S V^T=V S^T S V^T$

Which we arrive at by noting that $U$ is orthonormal, such that $U^T U=I$. Further we note that $S$ is a diagonal matrix, such that the final decomposition of $A^TA$ can be expressed as $V S^2 V^T$, with $S^2$ meaning $S^T S$, yielding a diagonal matrix with the first N singular values from $S$ squared in the diagonal. This means that since the condition number is the ratio of the first and the last singular value, $cond(A)=\frac{s_1}{s_N}$ for $A \in \mathbb{R}^{N \times M}$,

$cond(A^T A)=\frac{s_1^2}{s_M^2}=(\frac{s_1}{s_M})^2=cond(A)^2$

Now, we can perform the same exercise with $AA^T$:

$AA^T=USV^T (USV^T)^T=USV^T V S^T U^T=U S^2 U^T$

Which means that we get the result $cond(AA^T)=\frac{s_1^2}{s_N^2}$, since $S^2$ here means $SS^T$, a subtle difference from the notation above.

But note that subtle difference! For $A^TA$, the condition number has the M'th singular value in the denominator, while $AA^T$ has the N'th singular value. This explains why you are seeing significant differences in the condition number — $AA^T$ will indeed be “better conditioned” than $A^TA$.

Still, David Ketcheson was correct — you are comparing condition numbers between two vastly different matrices. In particular, what you can accomplish with $A^TA$ will not be the same as what you can accomplish with $AA^T$.

$\endgroup$
  • $\begingroup$ That is a great explanation! I see the difference clearly now. Matrix A is used to build normal equations and with slight changes you can also formulate it as $AA'$, not classical $A'A$. Can you tell as well if it is advantageous to use solver like LSQR instead of solving normal equations? Since LSQR doesn't require to build this product at all. $\endgroup$ – Alexander Mar 5 '12 at 12:54
  • $\begingroup$ Glad it made sense. In general, you need to consider the conditioning of the problem. But, if that is not an issue, you could use either normal equations/QR-factorization(of A)/LSQR, depending on the size of the problem (amongst other things). Unless your problem is large or ill-conditioned, I would probably apply the QR-factorization, but without more knowledge of the problem you are trying to solve, it's hard to tell. I am sure others with more experience could provide more detailed advice. $\endgroup$ – OscarB Mar 5 '12 at 13:24
  • $\begingroup$ The A itself is ill-conditioned (with condition number of $\approx 10^7$), dense and large. QR is not an option. Since it's ill-conditioned I have to add some regularization anyway. Now simple Tikhonov regularization seems to be enough. The point is that if $cond(A) < cond(AA^T) < cond(A^T A)$ (for my case with $N < M$) then using LSQR seems to be always preferable since you do not need to form any product at all. The question is if solutions obtained with normal equations and LSQR are identical? $\endgroup$ – Alexander Mar 5 '12 at 13:59
  • $\begingroup$ Well, as I understand it, LSQR will provide an identical solution to normal equations after "infinitely many" iterations in exact precision. However, for ill-posed problems, the normal equations solution is not the one you want. Instead, you want to use LSQR to iterate until semi-convergence is achieved. However, controlling iterative algorithms in ill-posed problems is a whole other ball-game. Also, depending on the cost of your matrix-vector product and the number of iterations (and thus matvecs) needed, a direct tikhonov solution with bidiagonalization might be better. $\endgroup$ – OscarB Mar 5 '12 at 15:42
  • $\begingroup$ Awesome explanation. +1 for you sir! $\endgroup$ – meawoppl Mar 5 '12 at 22:33
2
$\begingroup$

The claim that $\DeclareMathOperator{\cond}{cond} \cond A^2 \approx \cond A^T A$ (for square matrices) in the question and [Edit: I misread] in Artan's answer is nonsense. Counter-example

$$\newcommand\bigO{\mathcal{O}}A = \begin{pmatrix} \epsilon & 1 \\ 0 & \epsilon \end{pmatrix}, \quad \epsilon \ll 1 $$

for which you can easily check that $\cond A^T A = \bigO(\epsilon^{-4})$ while $\cond A^2 = \bigO(\epsilon^{-2})$.

$\endgroup$
  • $\begingroup$ Ok to stress that $A^2$ and $A^T A$ are in general very dissimilar as what regards eigs, svds, cond number: but in my opinion the question's claim is about $[\mathrm{cond}(A)]^2$. $\endgroup$ – Stefano M Jul 24 '12 at 20:25
  • $\begingroup$ @StefanoM Thanks, it seems I misread, though from the discussion, wasn't the only one. $\endgroup$ – Jed Brown Jul 25 '12 at 0:25
1
$\begingroup$

In exact arithmetic cond(A^2)=cond(A'A)=cond(AA'), see eg. Golub and van Loan, 3rd ed, p70. This is not true in floating point arithmetic if A is nearly rank deficient. The best advise is to follow the above book recipes when solving least square problems, the safest being SVD approach, p257. Use \varepsilon-rank instead when computing SVD, where \varepsilon is the resolution of your matrix data.

$\endgroup$
  • $\begingroup$ I'm sorry, I looked at Golub and Van Loan 3rd ed p. 70, and couldn't find anything backing up the statement cond(A^2)=cond(A^TA)=cond(AA^T). Could you be more specific with your reference? $\endgroup$ – OscarB Mar 9 '12 at 15:06
  • $\begingroup$ There is no statement there, but you can derive from theorem 2.5.2 and the pseudoinverse, section 5.5.4 that cond(AA')=cond(A'A). The reason that I take pseudoinverse is that this is what matters for the least squares problem in hand. The equality after cond(A^2) should be \approx, sorry for the typo. $\endgroup$ – Artan Mar 9 '12 at 20:37
  • $\begingroup$ No, this answer is totally incorrect. See my counter-example. $\endgroup$ – Jed Brown Jul 22 '12 at 17:12
  • $\begingroup$ Saad must have made such a point wrt to some specific context. What is relevant for the question at hand is the proceeding argument. $\endgroup$ – Artan Jul 25 '12 at 20:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.