Rank-1 correction of matrix exponential

Question

I need to approximate the following in $O(d)$ time for $d\times d$ diagonal $A$ and rank-1 $B$ $$u^T \exp(-A+B) v$$

Here $u,v$ are vectors in $\mathbb{R^+}^d$, $A,B$ are positive semi-definite and $B$ is relatively small

The following approximations take $O(d)$ to compute and get me within factor of 2 of true value on sample data

However, adding more terms from the Zassenhaus expansion seems to make the approximation worse, any tips?

How is your title correct, what is the matrix that receives a rank-1 update? — Lutz Lehmann, Mar 18 at 12:55
the argument of the matrix function. IE, I can compute $f(X)$ cheaply, and need to compute $f(X+rank1)$ where $f(X)=u^T e^X v$ — Yaroslav Bulatov, Mar 18 at 16:07

Federico Poloni · Accepted Answer · 2023-03-18 09:15:42Z

4

There is work on low-rank updates of matrix functions, for instance this one:

Beckermann, Bernhard; Kressner, Daniel; Schweitzer, Marcel, Low-rank updates of matrix functions, SIAM J. Matrix Anal. Appl. 39, No. 1, 539-565 (2018). ZBL1390.15024.

It could be a useful starting point if you wish to explore in that direction.

answered Mar 18 at 9:15

Federico Poloni

11.1k1 gold badge30 silver badges55 bronze badges

Add a comment |

1 Answer 1