Low-rank updates of matrix functions
It addresses the computational bottleneck of updating matrix functions in dynamic networks, offering a novel method with theoretical guarantees.
The paper proposes a method for efficiently updating matrix functions under low-rank modifications, achieving exactness for polynomials of degree ≤ m and demonstrating convergence for matrix exponentials and Markov functions. Experiments on network analysis show cheap updates for centrality measures.
We consider the task of updating a matrix function $f(A)$ when the matrix $A\in{\mathbb C}^{n \times n}$ is subject to a low-rank modification. In other words, we aim at approximating $f(A+D)-f(A)$ for a matrix $D$ of rank $k \ll n$. The approach proposed in this paper attains efficiency by projecting onto tensorized Krylov subspaces produced by matrix-vector multiplications with $A$ and $A^*$. We prove the approximations obtained from $m$ steps of the proposed methods are exact if $f$ is a polynomial of degree at most $m$ and use this as a basis for proving a variety of convergence results, in particular for the matrix exponential and for Markov functions. We illustrate the performance of our method by considering various examples from network analysis, where our approach can be used to cheaply update centrality and communicability measures.