I.5.3: Convergence Rate of ALS

The least squares loss function, in the most general form we consider here, is $$f(x)=\frac12\sum_{j=1}^m\sum_{\ell=1}^m w_{j\ell}g_j(x)g_\ell(x),$$ with $W$ a fixed symmetric positive semi-definite matrix of weights.

Thus $$\mathcal{D}f(x)=\sum_{j=1}^m\sum_{\ell=1}^m w_{j\ell}g_j(x)\mathcal{D}g_\ell(x),$$ and $$\mathcal{D}^2f(x)=\sum_{j=1}^m\sum_{\ell=1}^m w_{j\ell} \left\{g_j(x)\mathcal{D}^2g_\ell(x)+\mathcal{D}g_j(x)(\mathcal{D}g_\ell{x})'\right\}.$$

Note: Older piece follows (fix) 03/12/15

It is easy to apply the general results from the previous sections to ALS. The results show that it is important that the solutions to the subproblems are unique. The least squares loss function has some special structure in its second derivatives which we can often exploit in a detailed analysis. If $$\sigma(\omega,\xi)=\sum_{i=1}^n (f_i(\omega)-g_i(\xi))^2,$$ then $$\mathcal{D}^2\sigma= \begin{bmatrix} S_1&0\\ 0&S_2 \end{bmatrix} + \begin{bmatrix} G'G&-G'H\\ -H'G&H'H \end{bmatrix},$$ with $G$ and $H$ the Jacobians of $f$ and $g,$ and with $S_1$ and $S_2$ weighted sums of the Hessians of the $f_i$ and $g_i,$ with weights equal to the least squares residuals at the solution. If $S_1$ and $S_2$ are small, because the residuals are small, or because the $f_i$ and $g_i$ are linear or almost linear, we see that the rate of ALS will be the canonical correlation between $G$ and $H.$