5
$\begingroup$

I have a matrix $A\in \mathbb{C}^{N\times N}$ and I need to calculate $||A^{-1}||_{2}$ efficiently. Can it be done without having to evaluate the inverse explicitly?

In general, I am looking for methods of calculating $||A^{-1}||_{2}$ that are faster than just doing the following in Matlab:

norm(inv(A))

If no faster method is possible, or actually, just in general, I am alternatively interested in efficient ways to calculate an approximation or upper bound of $||A^{-1}||_{2}$.

Does anyone have any insight on this?

Edit: Note that the form of the matrix $A$ is in fact $A = I-B$ and this $I-B$ is very well conditioned (as $A$ has arisen due to preconditioning). I don't know if this makes any difference to how efficiently $||A^{-1}||_2$ an be computed but I just thought I'd mention it in case.

$\endgroup$
1
  • $\begingroup$ Is A a sparse matrix? fully dense? $\endgroup$ Jan 3, 2020 at 21:36

1 Answer 1

4
$\begingroup$

You might want to use the fact that:

$$ ||A||_2=\sigma_\max(A) $$

where $\sigma_\max$ is the largest singular value. If you are interested in details, this Math SO question should be interesting. Thus,

$$ ||A^{-1}||_2=\frac{1}{\sigma_\min(A)} $$ where $\sigma_\min$ is the smallest singular value.

You certainly want to avoid the actual calculation of the inverse and at least change it by a much more numerically stable Singular Vector Decomposition. Unfortunately, it is also a $\mathcal O(N^3)$ operation, where $N$ is the size of your matrix.

Now, if $N$ is too large, you might want to be interested in the algorithms of estimating singular values or even condition numbers, as

$$ \kappa_2(A)=||A||_2||A^{-1}||_2=\frac{\sigma_\max(A)}{\sigma_\min(A)} $$

which might be your actual motivation of calculating the $||A^{-1}||_2$ in the first place.

If your matrix $A$ happens to be normal ($A^HA=AA^H)$, then

$$ \kappa_2(A)=\frac{|\lambda_\max(A)|}{|\lambda_\min(A)|} $$ where $A^H$ represents a conjugate transpose, while $\lambda_\max(A)$ and $\lambda_\min(A)$ are the maximum and minimum eigenvalues of $A$ respectively. In this case, some calculations can be simplified.

Relevant material to start with:

Now, what to use in practice, would depend on your particular reasons for calculating this quantity, matrix size, available computational resources, and, potentially, matrix structure.

$\endgroup$
9
  • 1
    $\begingroup$ I find the Spectra to be a useful and easy library for calculating top-k eigenvalues. For appropriate matrices, these can then be manipulated through @Anton's answer to give the desired results. $\endgroup$
    – Richard
    Dec 30, 2019 at 23:54
  • $\begingroup$ I think the formula should actually be $\|A^{-1}\|_2 = \frac{1}{\sigma_\text{min}(A)}$. $\endgroup$ Dec 30, 2019 at 23:57
  • 2
    $\begingroup$ @WolfgangBangerth I have no idea how did I miss that while typing. Thanks! Worth to mention that singular values are non-negative, thus magnitude is not needed. $\endgroup$
    – Anton Menshov
    Dec 31, 2019 at 0:07
  • 1
    $\begingroup$ @sonicboom the smallest eigenvalue won't give you what you need. You need the smallest singular value (which are directly related to eigenvalues of $AA^H$, not just $A$) $\endgroup$
    – Anton Menshov
    Jan 2, 2020 at 10:44
  • 2
    $\begingroup$ @sonicboom that's not how it works. singular values cannot be obtained by calculating eigenvalues of $A$ and taking a square root in a general case. See my comment above and edits to the answer. $\endgroup$
    – Anton Menshov
    Jan 3, 2020 at 15:53

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.