Bounding $\|(I-A)^{-1}\|_2$ for $\rho(A)<1$

Question

I have a large, right sub-stochastic, sparse matrix with spectral radius $\rho(A)<1$.

I'm attempting to bound the spectral norm of $(I - A)^{-1}$ via its Neumann series,

$$\|(I-A)^{-1}\|_2=\Big\|\sum_{n=0}^\infty A^n\Big\|_2$$

For any $N$ such that $\|A^N\|<1$, I surmise that the following bounds are known in the literature,

$$\;\|(I-A)^{-1}\|_2\leq\frac{1}{1-\|A^N\|_2}\Big\|\sum_{n=0}^{N-1} A^n\Big\|_2\hspace{10mm}\text{(spectral bound)}$$

$$\|(I-A)^{-1}\|_2\leq\frac{\sqrt{M}}{1-\|A^N\|_\infty}\Big\|\sum_{n=0}^{N-1} A^n\Big\|_\infty\hspace{10mm}\text{(infinity bound)}$$

where $M$ is the dimension of $A$.

The spectral bound is of particular interest as it converges to the spectral norm. On the other hand, the infinity bound is notably more tractable. Due to the problem of fill-in, powers of $A$ cannot be explicitly formed, however because its entries are nonnegative, the infinity norm of $A^N$ may be iteratively computed as follows,

\begin{align} &x={\bf 1}\\ &\text{for i in 1:N}\\ &\hspace{8mm}x=Ax\\ &\text{done}\\ &\text{return}\max(x) \end{align}

A similar algorithm can be used to compute $\|\sum_{n=0}^{N-1} A^n\|_\infty$.

Conversely, to compute the spectral norm of $A^N$, one must use power iteration, which necessitates a double loop. Furthermore, the infinity norm has the added benefit that, due to its sub-stochasticity, $\|A^N\|_\infty<1$ for small $N$.

Ultimately, I am dissatisfied with my attempt to solve this problem. Is there a better bound for $\|(I-A)^{-1}\|_2$? or a faster way to compute its given spectral bound, other than power iteration? Or failing that, some other approach for estimating the spectral norm of $(I-A)^{-1}$?

Answer 1

Suppose $A$ can be written as $A = RB$, for $B$ symmetric and $R$ diagonal positive definite. Then there exists a non-iterative method for obtaining a superb bound on the spectral norm of $(I-A)^{-1}$.

First observe that $R^{-1}-B$ is clearly symmetric, and indeed positive definite, as it is diagonally dominant and the product of invertible matrices.

The following inequality holds,

$$\|(I-A)^{-1}\|_2=\|(I-RB)^{-1}\|_2\leq\|R^{-1}\|_2\|(R^{-1}-B)^{-1}\|_2$$

Given that $Q=R^{-1}-B$ has positive eigenvalues, if we shift its spectrum in the negative direction by $\lambda_\text{max}(Q)$, then the smallest eigenvalue of $Q$ will become the largest eigenvalue (in magnitude) of $Q-\lambda_\text{max}(Q)I$.

Therefore, we have,

$$\|R^{-1}\|_2\|Q^{-1}\|_2=\frac{\|R^{-1}\|_2}{\lambda_\text{max}(Q)-\|Q-\lambda_\text{max}(Q)I\|_2}$$

---

All things considered, the presupposition of such a factorization of $A$ should not be regarded as particularly unlikely. Indeed, any stochastic (or sub-stochastic) matrix which is built from an undirected graph may be decomposed in this fashion – as was true in my case. Moreover, if $R$ is the row normalization matrix for an adjacency matrix $B$, then $R^{-1}-B$ is simply the graph Laplacian, and $I-A$ the random walk normalized Laplacian.

Answer 2

An important observation concerning the two bounds presented in my original question is that the following inequality is true for any sub-multiplicative norm,

$$\|(I-A)^{-1}\|\leq\frac{1}{1-\|A^N\|}\Big\|\sum_{n=0}^{N-1}A^n\Big\|$$

provided of course that $\rho(A)<1$ and $\|A^N\|<1$.

Therefore, another interesting bound may be computed as follows,

\begin{align} \|(I-A)^{-1}\|_2&\leq\sqrt{\|(I-A)^{-1}\|_1\|(I-A)^{-1}\|_\infty}\\[3pt] &\leq\sqrt{\frac{1}{(1-\|A^N\|_1)(1-\|A^N\|_\infty)}\Big\|\sum_{n=0}^{N-1}A^n\Big\|_1\Big\|\sum_{n=0}^{N-1}A^n\Big\|_\infty} \end{align}

for all $N$ such that $\max(\|A^N\|_1,\|A^N\|_\infty)<1$.

In some cases, this inequality produces a much tighter bound than the infinity bound for an equivalent amount of computation. The iterative algorithms for computing the relevant 1-norm quantities are identical to those for the infinity norm, with $A^T$ in place of $A$.