6
$\begingroup$

I've heard that matrix is inversion is unstable whereas the SVD is stable.

Now, if $A$ is an invertible matrix, then its SVD is $$ A = USV^T $$

Then wouldn't it's inverse just be

$$ A^{-1} = (USV^T)^{-1} = VS^{-1}U^T $$

If the inverse is computed this way, why would it lose stability? Because of the multiplications? What am I missing?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

The big issue is the condition number, which is defined as the ratio of the largest and smallest singular values. Suppose we expect: $$ S = \begin{bmatrix} 10^{-15}\\ &1 \end{bmatrix} $$ If we slightly perturb the inputs, we might end up with a nearby matrix $$ S' = \begin{bmatrix} 2 \cdot 10^{-15}\\ &1 \end{bmatrix} $$ $S'$ close to $S$, and we would consider this stable. Now suppose we want to compute the inverse using SVD.

Notice that $$ S^{-1} = \begin{bmatrix} 10^{15}\\ & 1 \end{bmatrix}\\ S'^{-1} = \begin{bmatrix} 5 \cdot 10^{14}\\ & 1 \end{bmatrix} $$ Here the inverse of $S'$ is nothing like the inverse of $S$, and we might end up with an inverse $A'^{-1}$ which is no where near $A^{-1}$, thus is unstable.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I think I get it now. Ill-conditioning is really a property of the matrix inverse, not of the algorithm with which it is computed. $\endgroup$
    – NNN
    Aug 9 at 8:34
  • 2
    $\begingroup$ @NNN Ill-conditioning is a property of the original matrix that gets inherited by the inverse matrix. It makes to operation of matrix inversion unstable. Splitting off orthogonal or unitary factors is stable, be it Givens rotations, Householder reflectors or full matrices. The ill-condition is then concentrated in the remaining factor, in the SVD in the middle diagonal factor. $\endgroup$
    – Lutz Lehmann
    Aug 9 at 10:27
  • $\begingroup$ @LutzLehmann Since the ill-condition is concentrated in the middle factor in the SVD, isn't it a bit misleading to say that the SVD is numerically stable? $\endgroup$
    – NNN
    Aug 9 at 13:40
  • 5
    $\begingroup$ @NNN No, computing the decomposition itself is stable, there is only a controlled and small loss in accuracy. Using the decomposition to solve linear systems or invert the matrix can be unstable. $\endgroup$
    – Lutz Lehmann
    Aug 9 at 13:44
  • $\begingroup$ another way to think about it is like this. If you have a singular matrix, then it has some 0 eigen/singular values. If you perturb a singular matrix very slightly to make it invertible, it will still have some very very small eigenvalue (because the columns are very nearly linearly independent). Now, if you invert the matrix, this very small eigenvalue will blow up. So the smallest eigenvalue can be arbitrarily small as you move towards a singular matrix, which is why anything to do with inversion can blow up. $\endgroup$
    – Alan Chung
    Aug 10 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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