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?

$\endgroup$

1 Answer 1

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.

$\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
    Commented Aug 9, 2023 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$ Commented Aug 9, 2023 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
    Commented Aug 9, 2023 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$ Commented Aug 9, 2023 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
    Commented Aug 10, 2023 at 22:21

Your Answer

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

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