Return to Question

added 89 characters in body

Source Link

edited May 15, 2020 at 2:12

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.)

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)$?
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]$.

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)$?
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!

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)$?
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]$.

Source Link

asked May 15, 2020 at 0:07

CComp

Computational complexity of computing the trace of a matrix product under some structure

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)$?
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!