|
0
|
Hi everyone: I have a matrix M that is positive semi-definite, i.e., all eigenvalues are non-negative. I wonder to make it invertible, what is the best strategy ? 1) add an small identity matrix: $\delta$ * I, then compute the inverse matrix. or 2) simple compute the pseudo-inverse $M^+$ ? Which one is better and why ? |
||||||||||||||||
|
|
2
|
The choice that you make can result in a huge difference in the solution. Neither method is particularly good and both can be quite unstable. For example, suppose that $M=[1\;0\;0\; 0;\; 0 \; 1 \; 0 \; 0; \; 0 \; 0 \; 0 \; 0;\; 0 \; 0 \; 0 \; 0]$ and $N=[1;\; 1; \; 1; \; 1]$. What do you want $L$ to be in this situation? Why? Now, suppose that you try using $\delta = 1 \times 10^{-14}$. Then your approximation to $M^{1/2}$ is $M^{1/2}=[1\;0\;0\; 0;\; 0 \; 1 \; 0 \; 0; \; 0 \; 0 \; 1 \times 10^{-7} \; 0;\; 0 \; 0 \; 0 \; 1 \times 10^{-7}]$ and your approximation to $M^{-1/2}$ is $M^{-1/2}=[1\;0\;0\; 0;\; 0 \; 1 \; 0 \; 0; \; 0 \; 0 \; 1 \times 10^{7} \; 0;\; 0 \; 0 \; 0 \; 1 \times 10^{7}]$. In this case, the least squares solution is $L=[1; \; 1; \; 1 \times 10^{14} \; 1 \times 10^{14}]$. In the same example, if you use the pseudoinverse, then you'd get $L=[1; \; 1; \; 0 \; 0]$. Using the pseudoinverse effectively eliminated from consideration any projection of $N$ onto the null space of $M$. That might be what you want to do. However, if $M$ is ill-conditioned, then it becomes practically impossible to distinguish small eigenvalues of $M$ from $0$ eigenvalues. As a result the computation using the pseudoinverse also becomes extremely unstable and dependent on the tolerance used in computing the pseudoinverse. This isn't good either. Continuing the example, suppose that $M=[1\;0\;0\; 0;\; 0 \; 1 \; 0 \; 0; \; 0 \; 0 \; 1 \times 10^{-14} \; 0;\; 0 \; 0 \; 0 \; 1 \times 10^{-14}]$. The pseudoinverse solution is then $L=[1; \; 1; \; 1 \times 10^{14};\; 1 \times 10^{14}]$ Now, suppose that due to a rounding tolerance in computing the pseudoinverse, you compute $\mbox{pinv}(M)=[1\;0\;0\; 0;\; 0 \; 1 \; 0 \; 0; \; 0 \; 0 \; 0 \; 0;\; 0 \; 0 \; 0 \; 0]$ Then you'd get $L=[1; \; 1; \; 0 \; 0]$ again. You really need to back up a bit and explain to us why you're trying to solve this particular least squares problem in a situation where $M$ might be singular. It's likely that you need to deal with this possible ill-conditioning at a higher level by using some sort of regularization approach that is based on the particular aspects of your underlying problem. |
|||||||||
|
