Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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|cite|improve this answer

Your Answer


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.