1
$\begingroup$

I have two problems related to computing some trace, and some (possibly suboptimal) answers. My question is about a potential more efficient algorithm for each one. (More interested in an answer to question 1.)

  1. Let $U, V$ and $F$ be three real matrices. All three matrices have size $d \times r$, with $r \ll d$ (that is, $U, V$ and $F$ are ``tall''). I want to compute $\mathrm{trace}(U V^\top F F^\top)$. Computing $A = F^\top U$, $B = V^\top F$ and the trace of $AB$ has complexity $\mathcal{O}(r^2 d)$. Is there any faster algorithm (taking into account $r \ll d$)? Can we get $\mathcal{O}(r d)$?

  2. Let $U, V$ and $M$ be three real matrices. $U$ and $V$ have size $d \times r$ (with $r \ll d$), and $M$ is lower triangular (with positive elements in its diagonal) of size $d \times d$. I want to compute $\mathrm{trace}(U V^\top M M^\top)$. The simple algorithm of computing $A = M^\top U$, $B = V^\top M$, and then the trace of $AB$ has a complexity $\mathcal{O}(r d^2)$. Is there any faster algorithm (taking into account $r \ll d$)?

If this question does not belong here please let me know! (If so, also where can I post it.)

Thanks!

Edit: just for reference, typical values are $d \in [200, 1700]$ and $r \in [3, 15]$.

Improve this question
$\endgroup$
3
  • $\begingroup$ The answer may depend on how "tall" your matrix is; if $r > O(d^{0.7})$ (not a tight bound), then a naive application of the Coppersmith-Winograd algorithm gets the answer faster than the naive algorithm for part 1; for part 2, the restriction is $r > O(d^{0.4})$ (both if I've done my arithmetic right). en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm $\endgroup$
    – user44191
    Commented May 15, 2020 at 1:01
  • $\begingroup$ Thanks. For what I've read about Coppersmith-Winograd algorithm (not much to be honest), it seems to be quite impractical. This is something I'll implement as a part of a bigger algorithm. As a reference, I typically have $d \in [200, 1700]$ and $r \in [3, 15]$. Using $r \ll d$ in the question might have been a slight abuse (maybe?). My biggest concern is for question 1, can I go from $r^2d$ to $rd$? Maybe there's a simple way of verifying that's not possible. $\endgroup$
    – CComp
    Commented May 15, 2020 at 2:08
  • $\begingroup$ If $r$ is at most $15$ in the instances you're dealing with, the difference between $O(r^2 d)$ and $O(r d)$ may not be of much practical importance: a $O(r^2 d)$ algorithm might outperform a $O(r d)$ algorithm, depending on details of implementation. $\endgroup$
    – Robert Israel
    Commented May 15, 2020 at 14:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .