if $n \times n$ full rank matrix $A$ has condition number $\kappa$, what would be the condition number of $A^TA$? Preferably If the derivation includes the following definition of $\kappa$: $$ \kappa = \sigma_{max} / \sigma_{min} $$ Where $\sigma$ are the non-zero singular-values of $A$.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
I assume you mean the condition number defined by the Euclidean norm, i.e. $$ \kappa = \|A\|\cdot \|A^{-1}\| $$ Note also that $\|A\| = \|\sqrt{A^TA}\|$. Conclude that $\kappa(A^TA) = \kappa(A)^2$.
answered Jul 6, 2015 at 17:50
-
$\begingroup$ Not quite. You forgot a square. Also, this is assuming the operator norm induced by the Euclidean norm. There are other matrix norms that are used in defining condition numbers. $\endgroup$ Commented Jul 6, 2015 at 17:56
-
$\begingroup$ Side note: one option for solving $Ax = b$ numerically could be to solve $A^T A x = A^T b$ using the conjugate gradient method, a method which requires the coefficient matrix to be symmetric. However, this approach has the disadvantage that the condition number of $A^T A$ is the square of the condition number of $A$. $\endgroup$– littleOCommented Jul 6, 2015 at 18:05
-
$\begingroup$ @RobertIsrael whoops, fixed. Thank you. $\endgroup$ Commented Jul 6, 2015 at 18:12
-
1$\begingroup$ $\|A\| \cdot \|A^{-1}\| = \lambda_{max}/\lambda_{min}$ when $A$ is symmetric, but this is not generally the case. The condition number is not usually defined to be the ratio of those eigenvalues. Can we assume that $A$ is symmetric? $\endgroup$ Commented Jul 7, 2015 at 18:31
-
1$\begingroup$ @Hayer in that case, then notice that $\|A\| = \sigma_{max}(A)$, and that $\|A^{-1}\| = \sigma_{max}(A^{-1}) = \frac 1{\sigma_{min}(A)}$ $\endgroup$ Commented Jul 8, 2015 at 3:31
$\begingroup$
$\endgroup$
The result is true for rectangular matrices.
Let $p\geq q$ and $A\in M_{p,q}(\mathbb{R})$ be a full column rank matrix. We consider $||A||_2=\sup \dfrac{||Ax||_2}{||x||_2}$ and $cond(A)=||A||.||A^+||$ where $A^+$ is the pseudo-inverse of $A$. Then $cond(A)^2=cond(A^TA)$ (exercise)
In particular, if we want to use the Gauss method of least squares for $Ax-b$, then we must solve $A^TAx=A^Tb$; thus the condition number of this calculation is $cond(A)^2$. Finally, if $A,b$ are known with $N$ significant digits and if $cond(A)\approx 10^k$, then $x$ is known with $N-2k$ significant digits.