An ill-conditioned matrix

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,

-

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.

-
Thanks J.M. and @alex. However if we take the pseudoinverse of CtC, instead of C, (and then multiply by Ct) are we better off? – Omri Sep 6 '11 at 10:19
Why would you do that, @Omri? Merely forming $\mathbf C^T\mathbf C$ is already a bad idea. – J. M. Sep 6 '11 at 10:55
Yes, you are right. Nevertheless, when I used $(C^{T} C)^{-1} C^{T}$ where the inverse here is the pseudoinverse, instead of simply a pseudoinverse of C, in the context of Fisher Discriminant Analysis (for inverting the sample covariance matrix) I got better generalization errors for small samples... it is strange. – Omri Sep 6 '11 at 13:44
How much better is "better"? Tell you what @Omri, how about telling me what the largest and smallest singular values of your matrix are? – J. M. Sep 6 '11 at 13:50
It's substantially better in multiple runs and multiple data scenarios - about 20% smaller misclassification error. The largest singular value of C is 1.13 and the smallest 0.031. – Omri Sep 6 '11 at 14:57

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.

-