Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
    
I posted it on math.SE today hoping I could get an answer. –  user4292 Mar 18 '11 at 5:45
    
@Sivaram Ambikasaran, it is common to at least wait a few days before cross-posting on other sites. (You should also link to the cross-posted versions in the question.) –  Kaveh Mar 20 '11 at 9:08
    
Wikipedia claims that Gram-Schmidt orthogonalization has a constant of 2 (instead of 3 for Householder), but I did not check the claim. It might be worth trying. However, in the end you have to somehow orthogonalize the columns of $A$. If you can do that substantially better than QR, then your technique could be used to beat QR in general (which is unlikely). –  Milos Hasan Mar 20 '11 at 22:20
    
@Milos: Thanks. But GS is unstable. Instead of doing QR twice once on A and once on B, can we get around it say by doing QR once just on A or B and then manipulate? or as I have mentioned in the post, is there a way to simplify the entire thing since we know that the left singular vectors span A and the right singular vectors span B? –  user4292 Mar 23 '11 at 5:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.