I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ and $B$ separately)
EDIT: (I have added the second question here since it was closed as a duplicate of this question. Note that the optimal algorithm for the low rank version $p \ll n$ will not work for this.)
In general, if we have two full rank square matrices, what is the most efficient way to find SVD of a product of two matrices say A×B ? (Is it possible to find the SVD without explicitly multiplying them out?).
Is there a relation between the SVD of the product A×B and the SVD of the individual matrices (A and B) ?
Back to the first question:
One efficient way to get the Singular Value Decomposition when $p \ll n$ is to do a reduced QR on $A$ and $B$ i.e.
$A = Q_A R_A$ and $B = Q_B R_B$.
The above can be done in $\mathcal{O}(p^2n)$ cost.
I could then compute the svd of $R_A R_B^T = U_1 \Sigma V_1^T$ which is $\mathcal{O}(p^3)$.
Hence this will give me $$AB^T = (Q_A U_1) \Sigma (Q_B V_1)^T$$
The total cost is $\mathcal{O}(np^2)$.
However, I am wondering if there are other efficient ways to go about doing this to reduce the coefficient infront of $p^2n$. If I am right, the coefficient infront of $np^2$ is $3$ if we go about doing QR. The reason why I am interested in minimizing the coefficient is that my $n$ is really ginormous. So if I were to implement it, a cost cutting on the coefficient of the $\mathcal{O}(n)$ could be significant.
I am wondering if we could exploit the fact that the left singular vectors must span $A$ and the right singular vectors span $B$
i.e. we know that if $AB^T = U \Sigma V^T$, then
$$A = U \alpha \text{ and } B = V \beta$$
and we want $\alpha \beta^T$ to be diagonal and $U$,$V$ needs to be unitary.
EDIT What I essentially want is an exact rank $r<p$ approximation to the product $AB^T$ in the form $U_r V_r^T$. I am not looking for approximate or probabilistic algorithms.
