0
$\begingroup$

Sorry this is quite a specific question, happy to reword the title however you think is more appropriate, but for a given $m$ x $n$ matrix A, and an initial, random $n$ x $k$ matrix $v$, I have this loop which calculates:

U = A*V; 
[U,UR] = qr(U,0);
V = A'*U;
[V,VR] = qr(V,0);

until $|UR-VR|\approx0$

I understand that UR and VR are diagonal matrices where the ith diagonal entry stores the norm values relating the ith column of U and V respectively, which are unit vectors.

But I'm confused as to why there is convergence other than the circular relationship between $U$ and $V$, and also how they are significant.

Any pointers would be helpful!

$\endgroup$
2
$\begingroup$

As you are asking for tracks helping to understand what this algorithm is made for, here is a partial, mainly experimental, answer.

First of all : let us recall that Matlab instruction [Q,R]=qr(M) gives "the" QR factorization $M=QR$ of matrix $M$ into an orthogonal matrix $Q$ and an upper triangular matrix $R$.

Experimental constatation : the absolute values of the entries of diagonal matrices $UR, VR$ always converge to the singular spectrum (set of singular values) of $A$. Moreover, matrix $V$ converges to the matrix of singular vectors that is found in svd decomposition $A=USV^T$.

The eigenvalues of matrix A^TA are known to be the singular values of $A$.

Here is a computation done with the notations of the Matlab program below (expanding - with different notations - the 4 lines given by the asker) showing how the symmetrical matrix $A^TA$ is involved in the algorithm.

$$\begin{cases}U_i&=&AV_i&\\ Q_iR_i&=&AV_i & \ \text{By left-multiplying LHS and RHS by } \ A^T \ : \\ A^TQ_iR_i&=&A^TAV_i &\\ WR_i&=&(A^TA)V_i & \\ (V_{i+1})(S_{i}R_i)&=&(A^TA)(V_i) & \\ \end{cases}$$

In the hypothesis where $R_i$ and $S_i$ close to (identical) diagonal matrices (which in fact they tend to be), we find a version of the power iteration algorithm (http://mlwiki.org/index.php/Power_Iteration) for symmetric matrices. But I am conscious that this is not a rigorous approach.

I attempted also to approach, unsuccessfuly, a version of the so-called QR algorithm ("without shifts") for computing eigenvalues of $A^TA$ : see for this method, the excellent slideshow

https://www-users.cs.umn.edu/~saad/csci5304/FILES/LecN13.pdf

Appendix : Here is the equivalent program on which I have been working (with a fixed number of steps) :

m=4;n=3;k=5;
A=2*rand(m,n)-1; % in order to have negative and positive entries
V=2*rand(n,k)-1;
for q=1:50;
   U = A*V;
   [Q,R] = qr(U,0);
   W = A'*Q;
   [V,S] = qr(W,0);
end;
U,V, % with R1 (almost) identical to R2
[U1,S,V1]=svd(A); % (almost) identical to the set abs(diag(R1)) 
$\endgroup$
  • $\begingroup$ Hi thanks for your answer! I can see some of the parallels between your code and mine, though I'd note that w.r.t. Matlab's qr code, my example actually calls the "economy-sized decomposition" where, "If m > n, only the first n columns of Q and the first n rows of R are computed. If m<=n, this is the same as [Q,R] = qr(A)." (mathworks.com/help/matlab/ref/qr.html). Also in my case A is not symmetric as it is not square! $\endgroup$ – user61871 May 6 at 16:26
  • $\begingroup$ I noticed that you use qr factorizations for matrices that could be rectangular, but I hadn't thought that they are never square... $\endgroup$ – Jean Marie May 6 at 16:33
  • 1
    $\begingroup$ In fact, following your remark, I have completely revised my answer : the convergence is toward the singular spectrum (svd(A)) of $A$ that doesn't need anymore to be neither square nor symmetrical ! $\endgroup$ – Jean Marie May 6 at 16:47
  • $\begingroup$ Besides, can I ask you where you have found this algorithm/program ? $\endgroup$ – Jean Marie May 6 at 16:50
  • 1
    $\begingroup$ OK, so u and v are the left/right singular vectors of A? Do you know any references for this so I can read up? Definitely, still confused haha. The program was in a problem set of mine! $\endgroup$ – user61871 May 6 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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