3
$\begingroup$

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 ?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ "better" for what purpose? The answer depends largely on that. Please add more detail. $\endgroup$
    – Federico Poloni
    Commented Apr 18, 2012 at 21:32
  • $\begingroup$ I mean stability. Will these two approaches differ significantly. My application uses the inverse matrix of the PSD matrix to solve the minimization problem, $\min ~ \| M^{1/2} L - M^{-1/2} N \|_F^{2} $ Here matrices M and N are known, and L is to be computed. I minimize the Frobenious norm, which can be solved by a set of least square problems. So different inverse matrices would affect the final solution of L. I would like to see any references discussing the effect of different transformation approaches (from PSD to PD). $\endgroup$
    – Alex
    Commented Apr 18, 2012 at 22:53
  • 2
    $\begingroup$ What do you know about $M$? In particular do you know whether it is simply rank deficient or whether it might be ill conditioned? In terms of the eigenvalues of $M$ are the nonzero eigenvalues well separated from the 0 eigenvalues, or could you have small nonzero eigenvalues? $\endgroup$
    – Brian Borchers
    Commented Apr 19, 2012 at 5:08
  • $\begingroup$ M is guaranteed to be a positive semi-definite (PSD) matrix. There is no guarantee that all eigenvalues are positive. Then, there is a potential problem with my paper because of my careless during the formulation (dmml.asu.edu/users/xufei/Papers/ICDM2011.pdf page 3). So I want to find a ``good'' solution in terms of stability for this matrix inversion problem. $\endgroup$
    – Alex
    Commented Apr 20, 2012 at 16:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks Brian, very intuitive examples. The stability is exactly what I am concerned. The high level picture is that I want to solve a document clustering problem which can be finally converted to solve a set of least square problems. Then I get the potentially ill-conditioned matrix M. And now I need to find a good way to solve this problem. $\endgroup$
    – Alex
    Commented Apr 20, 2012 at 17:06
  • $\begingroup$ I am also interested in if there is any theoretical analysis to the stability of computing inverse ill-conditioned matrices. $\endgroup$
    – Alex
    Commented Apr 20, 2012 at 21:46
  • 1
    $\begingroup$ Solving rank deficient and discrete ill-posed least squares problems is a very well studied subject. There's an inevitable tradeoff between stability of the computed solution with respect to round-off as well as error in the right hand side (your $N$ matrix) and biasing the solution away from a true least squares solution. By adjusting the regularization term, you can control in what direction the solution is biased by the regularization. By adjusting a regularization parameter you can control the trade-off between stability and bias. See for example Per Hansen's book. $\endgroup$
    – Brian Borchers
    Commented Apr 21, 2012 at 2:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .