Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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$.
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})$.
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.
