I.5.1: Introduction

An Alternating Least Squares or ALS algorithm is defined as a block relaxation algorithm applied to a least squares loss function. Least squares loss functions are somewhat loosely defined. We will discuss what we have in mind, before giving some of the history of ALS methods.

We start with have a functions $f$ of the form $$f(x)=\sum_{j=1}^m\sum_{\ell=1}^m w_{j\ell}g_j(x)g_\ell(x),$$ where $W$ is an $m\times m$ fixed positive semi-definite matrix of weights, and we minimize $f$ over $x\in\mathcal{X}$.

One obvious property of least squares loss functions is that they are bounded below by zero, which means that a decreasing sequence of loss function values $f^{(k)}=f(x^{(k)}),$ generated for example by an iterative algorithm, necessarily converges.

Alternating least squares methods by definition use block relaxation, so we introduce a block structure. As usual the block structure is designed to make the minimization subproblems relatively easy to solve. A first step towards simplicity is to $$f(x_1,\cdots,x_p)=\sum_{j=1}^m\sum_{\ell=1}^mw_{j\ell}g_j(x_1,\cdots,x_p)g_\ell(x_1,\cdots,x_p),$$ which must be minimized over $x_s\in\mathcal{X}_s$, where $\mathcal{X}=\mathcal{X}_1\otimes\cdots\otimes\mathcal{X}_p$. To make the problem interesting for block optimization we have separated the constraints on $x$ into separate constraints on the $n$ blocks $x_i$.

In many ALS examples there is additional structure. A familar special case has the form $$f(x_1,x_2)=\sum_{j=1}^m\sum_{\ell=1}^mw_{j\ell}(g_j(x_1)-h_j(x_2))(g_\ell(x_1)-h_\ell(x_2))$$ Of course $x_1$ and $x_2$ can be further partitioned into blocks if that is convenient. Even more structure is introduced into the ALS problem when the functions $g_j$ and $h_j$ are polynomials or multilinear functions.

As explained in section introduction/history the term Alternating Least Squares was first used in De Leeuw [1968]. There certainly were ALS methods before 1968. Examples are the missing data methods in factorial analysis of variance pioneered by Yates [1933], the iterative principal factor analysis method of Thomson [1934], or the MINRES method for factor analysis by Harman and Jones [1966]. The systematic use of ALS techniques in psychometrics and multivariate analysis started after the pioneering work of Kruskal [1964a, 1964b, 1965] in nonmetric multidimensional scaling. Applications De Leeuw, Young, and Takane started the ALSOS system of techniques and programs around 1973 (see Young et al [1980]), Applications and De Leeuw, with many others, at Leiden University started the Gifi system around 1975 (see Gifi [1990]).