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}$

Question

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.

Answer 1

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:

• L. Qi, "Some simple estimates for singular values of a matrix," Lin. Algebra Appl., vol. 56, pp. 105–119, Jan. 1984
• Estimation of condition numbers of very large matrices with practical advice using PETSc
• Similar PETSc-driven discussion for sparse matrices
• Different approach using Cholesky factorization using CHOLMOD

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.