Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix.

How do I estimate $u^T A^k v$ in $O(d)$ time?

Powers of convergent diagonal $D$ can be computed in $O(d)$ time by utilizing Laplace transform. For a general DPR1 matrix, there's $O(d^2)$ algorithm but I need something that works much faster.


1 Answer 1


It is not necessary to compute $A^k$ in your case. You can do a matrix-vector product with $A=D+pq^T$ in about $5d$ operations, and so multiplying with $A^k$ via $$ A^k v = A (A (A \cdots (Av))) $$ is going to cost you $5kd$ operations. The last dot product, $u^T A^k v$ is going to add $2d$ operations to that, for a total of $(5k+2)d$.

Assuming $k\ll d$, this is likely optimal. If $k\gtrsim d$, then you're already in the $O(d^2)$ case and the Laplace transform case is probably going to win.

  • $\begingroup$ Yes I'm looking at k>>d, but wasn't clear how to generalize the Laplace approach to dpr1 case. $\endgroup$ Commented Mar 10, 2023 at 4:15
  • $\begingroup$ I see, tough. Can you compute the eigenvectors of $A$ in better than $O(d^2)$? If so, you can expand $u,v$ in terms of these eigenvectors, and go from there. $\endgroup$ Commented Mar 10, 2023 at 5:13
  • 1
    $\begingroup$ It seems you can get a single eigenvector in O(d), but full eigendecomposition needs d^2 $\endgroup$ Commented Mar 10, 2023 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.