What do these matrices converge to?

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.

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

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

• 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! – user61871 May 6 at 16:26
• I noticed that you use qr factorizations for matrices that could be rectangular, but I hadn't thought that they are never square... – Jean Marie May 6 at 16:33
• 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 ! – Jean Marie May 6 at 16:47
• Besides, can I ask you where you have found this algorithm/program ? – Jean Marie May 6 at 16:50
• 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! – user61871 May 6 at 17:02