Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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