1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yes I'm looking at k>>d, but wasn't clear how to generalize the Laplace approach to dpr1 case. $\endgroup$ Mar 10 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$ Mar 10 at 5:13
  • 1
    $\begingroup$ It seems you can get a single eigenvector in O(d), but full eigendecomposition needs d^2 $\endgroup$ Mar 10 at 5:24

Your Answer

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

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