4
$\begingroup$

If C is an ill-conditioned matrix and I want to get the inverse, one way is to take a pseudo-inverse of some sort. Instead, is the following, which uses the (normal) inverse, also a way to deal with this? Instead of $ C^{-1} $ use, $(C^{T} C)^{-1} C^{T} $ Thanks,

2 Answers 2

5

If $\mathbf C$ is ill-conditioned; $\mathbf C^T \mathbf C$ is even more so; that is because this operation squares the condition number of your matrix $\mathbf C$.

If we consider the singular value decomposition of $\mathbf C=\mathbf U\mathbf \Sigma\mathbf V^T$, where $\mathbf \Sigma$ is the diagonal matrix of singular values $\mathrm{diag}(\sigma_i)$, then the (2-norm) condition number $\kappa_2(\mathbf C)=\frac{\max\sigma_i}{\min\sigma_i}$. If $\min\sigma_i$ is tiny, then $\mathbf C$ is ill-conditioned.

If we try to substitute in the singular value decomposition, we have

$\mathbf C^T \mathbf C=(\mathbf U\mathbf \Sigma\mathbf V^T)^T(\mathbf U\mathbf \Sigma\mathbf V^T)=\mathbf V\mathbf \Sigma\mathbf U^T\mathbf U\mathbf \Sigma\mathbf V^T=\mathbf V\mathbf \Sigma^2\mathbf V^T$

where we used the fact that $\mathbf U$ is orthogonal.

From the singular value decomposition of $\mathbf C^T \mathbf C=\mathbf V\mathbf \Sigma^2\mathbf V^T$, we see that $\kappa_2(\mathbf C^T \mathbf C)=\frac{(\max\sigma_i)^2}{(\min\sigma_i)^2}$. If $\min\sigma_i$ is tiny, $(\min\sigma_i)^2$ is even tinier; thus $\mathbf C^T \mathbf C$ is even more ill-conditioned than the original.

Your best bet is to use the singular value decomposition itself to form the pseudoinverse:

$\mathbf C^\dagger=\mathbf V\mathbf \Sigma^\dagger \mathbf U^T$

where to form $\mathbf \Sigma^\dagger$, the entries of $\mathbf \Sigma$ are either reciprocated if greater than the machine epsilon (or some power of it) multiplied by $\max\sigma_i$, or made zero otherwise.

  • 0
    Huh. So the smallest isn't that small... that is peculiar indeed. What computing environment is this, @Omri?2011-09-06
4

I believe that wouldn't work. Intuitively, a matrix is ill-conditioned if its close to a singular matrix in a certain sense; if that is the case for the matrix $C$, then $C^T C$ will also be close to a singular matrix.

To be precise, the condition number of a matrix is defined in terms of its singular values: $ \kappa(C) = \frac{\sigma_{\rm max}(C)}{\sigma_{\rm min}(C)} = \sqrt{\frac{\lambda_{\rm max}(C^T C)}{\lambda_{\rm min}(C^T C)}}.$ The matrix is ill-conditioned if $\kappa(C)$ is large. Now because $C^T C$ is symmetric,

$ \kappa(C^T C) = \sqrt{\frac{\lambda_{\rm max}((C^T C)^2)}{\lambda_{\rm min}((C^T C)^2)}} = \kappa(C)^2,$ so that if $\kappa(C)$ is large, $\kappa(C^T C)$ is larger still.