I.3.7.2: Low Rank Approximation of a Matrix

Given an $n\times m$ matrix $X$ we want to minimize $$\sigma(A,B)=\text{tr }(X-AB')'(X-AB')$$ over the $n\times p$ matrices $A$ and the $m\times p$ matrices $B$. In other words, we find the projection of $X$, in the Frobenius norm, on the set of matrices of rank less than or equal to $p$.

The block relaxation iterations are $$\begin{align*} B^{(k+1)}&=X'A^{(k)}((A^{(k)})'A^{(k)})^{-1}\\ A^{(k+1)}&=XB^{(k+1)}((B^{(k+1)})'B^{(k+1)})^{-1}, \end{align*}$$ or $$A^{(k+1)}=\left[XX'A^{(k)}((A^{(k)})'XX'A^{(k)})^{-1} (A^{(k)})'\right]A^{(k)}.$$

$$A^{(k)}(B^{(k+1)})'=P_A^{(k)}X,$$ $$A^{(k+1)}(B^{(k+1)})'=XP_B^{(k+1)},$$

It follows that $(A^{(k)})'(A^{(k+1)}-A^{(k)})=0$ and, thus, for all $k$ $$\|A^{(k+1)}-A^{(k)}\|^2=\|A^{(k+1)}\|^2-\|A^{(k)}\|^2\geq 0.$$ Thus $||A^{(k)}||^2$ increases to a limit less than or equal to the upper bound $\alpha$. Also $$\sum_{i=1}^k \|A^{(i+1)}-A^{(i)}\|^2=\|A^{(k+1)}\|^2-\|A^{(0)}\|^2\leq\alpha-\|A^{(0)}\|^2,$$ and consequently $\|A^{(i+1)}-A^{(i)}\|$ converges to zero.

Now suppose $\tilde A^{(k)}=A^{(k)}S$, with $S$ nonsingular. Then $\tilde B^{(k+1)}=B^{(k+1)}S^{-t}$, and thus $$\tilde A^{(k)}(\tilde B^{(k+1)})'=A^{(k)} (B^{(k+1)})'.$$ In addition $\tilde A^{(k+1)}=A^{(k+1)}S$, and thus $$\tilde A^{(k+1)}(\tilde B^{(k+1)})'=A^{(k+1)} (B^{(k+1)})'.$$

Alternative $$\begin{align*} B^+&=X'A,\\ A^+&=XB^+((B^+)'B^+)^{-1}=XX'A(A'XX'A)^{-1}, \end{align*}$$ $$\begin{align*} B^+&=X'A(A'XX'A)^{-\frac12},\\ A^+&=XB^+=XX'A(A'XX'A)^{-\frac12}, \end{align*}$$ $$A^+(B^+)'=X\{X'A(A'XX'A)^{-1}A'X\}$$