# Fastest way to calculate the $2$-norm (or an upper bound for the $2$-norm) of the inverse of a matrix $A\in \mathbb{C}^{N\times N}$

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.

• Is A a sparse matrix? fully dense? – Brian Borchers Jan 3 at 21:36

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.

• I think the formula should actually be $\|A^{-1}\|_2 = \frac{1}{\sigma_\text{min}(A)}$. – Wolfgang Bangerth Dec 30 '19 at 23:57
• @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$) – Anton Menshov Jan 2 at 10:44
• @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. – Anton Menshov Jan 3 at 15:53