I.5.4.5: Scaling and Splitting

Early on in the development of ALS algorithms some interesting complications where discovered. Let us consider canonical correlation analysis with optimal scaling. There we want to minimize $$\sigma(X,Y,A,B)=\hbox{tr }(XA-YB)'(XA-YB),$$ where the $X$ and the $Y$ are optimally scaled or transformed variables. This problem is analyzed in detail in Van der Burg and De Leeuw \cite{canals}. This seems like a perfectly straightforward ALS problem. It can be formulated as a problem with the two blocks $(X,Y)$ and $(A,B),$ or as a problem with the four blocks $X,Y,A,B.$ But no matter how one formulates it, a normalization must be chosen to prevent trivial solutions. In the spirit of canonical analysis it makes sense to require $A'X'XA=\mathcal{I}$ or $B'Y'YB=\mathcal{I}.$ Both sets of conditions basically lead to the same solution, but in the intermediate iterations the normalization condition creates a problem, because it involves elements from two different blocks. Also, although $A'X'XA=\mathcal{I}$ is a simple constraint on $A$ for given $X,$ it is not such a simple constraint on $X$ for given $A.$

The solution to this dilemma, basically due to Takane, is to constrain either $(X,A)$ or $(Y,B),$ always update the unconstrained block, and switch normalizations after each update. Global convergence (at least of loss function values) is guaranteed by the following analysis.

Theorem: $\min_A\min_{B'Y'YB=\mathcal{I}}\sigma(X,Y,A,B)= \min_{A'X'XA=\mathcal{I}}\min_B\sigma(X,Y,A,B)=\sum_{s=1}^p(1-\rho_s^2(X,Y)).$

Proof: $$\min_A\sigma(X,Y,A,B)=\text{ tr }B'Y'YB-B'Y'X(X'X)^{-1}X'YB,$$ and minimizing the right-hand side over $B'Y'YB=\mathcal{I}$ clearly proves the first part of the Theorem. The second part goes the same. QED