7
$\begingroup$

I know that it is generally a bad idea to compute the inverse matrix directly. However, if it is necessary to compute the inverse of an ill-conditioned invertible dense matrix, then what can I try?

For example, I know that scaling a matrix may decrease the condition number of it. This may be an example of preconditiong, but I don't know much about the theory of preconditioners.

I also know that the computation technique can be varied depending on properties of the matrix. Questions posted on this site (e.g., 1, 2, 3) have their specific answer, not a general one.

But I can't find the general principle to compute the inverse because I am new to this field. What properties of the matrix should I check to reduce the condition number? Is there any strategy, or, any books/papers which explain more accurate methods to compute the inverse directly?

(I don't know if there is a short answer of this. Feel free to close this question as too broad.)

$\endgroup$
12
$\begingroup$

Though it is a relatively rare situation when you actually have to calculate an inverse of the matrix, not all techniques were created equally.

I would use the term badly-conditioned instead of ill-conditioned. For badly conditioned matrices, you might opt in the SVD-route to calculate the inverse: $$ A=U\Sigma V^H \implies A^{-1}=V\Sigma^{-1}U^H. $$ If your matrix $A$ is actually badly conditioned, you still should be able to perform $\Sigma^{-1}$. However, you see a problem right away: if the condition number is large (ill-conditioning), the relation of $\sigma_1/\sigma_N$ is huge ($\sigma_1,\ldots,\sigma_N$ being the singular values of $A$, the entries constituting a diagonal matrix $\Sigma$, where $\sigma_1\ge\sigma_2\ge\ldots\ge \sigma_N$).

This approach also enables (and is close by virtue of $^{-1}\to ^{+}$) to use a notion of a pseudo-inverse $A^{+}$: $$ A^+=V\Sigma^{+}U^H $$ Now, only non-zero elements of $\Sigma$ are "reciprocated", and you can filter out too small singular values and singular values based on some tolerance (truncated SVD). Again, that does not help the ill-conditioning of the original problem in any way, just offers a way to compute something that should be avoided in a more accurate way.

Again, a more solid answer would be on the topic of avoiding the calculation of the inverse for an ill-conditioned problem.

$\endgroup$
  • $\begingroup$ Is there any theory behind this? I want to know whether this method is one of heuristics, or abstract one with a guarantee. $\endgroup$ – nekketsuuu Mar 23 '18 at 11:28
  • $\begingroup$ There is plenty of theory behind this. You may want to start even with the Wikipedia Page and then proceed according to your needs. There is no heuristic involved, though, there is naturally a truncation tolerance parameter (!) of your choice (see truncated SVD). Regarding the guarantee, I am not sure I understand what are you looking for, as the "guarantee" has to be defined somehow. $\endgroup$ – Anton Menshov Mar 23 '18 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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