What do these matrices converge to?

Question

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!

Answer 1

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