CANDECOMP

An algorithm to solve the INDSCAL problem.

In the analysis of the INDSCAL three-way data matrix (numberOfPoints × numberOfDimensions × numberOfSources) we seek to minimize the function:

f(X, W1,..., WnumberOfSources) = ∑i=1..numberOfSources | SiXWiX′ |2

where Si is a known symmetric numberOfPoints × numberOfPoints matrix with scalar products of distances for source i, X is the unknown configuration numberOfPoints × numberOfDimensions matrix, X′ its transpose, and, Wi is the diagonal numberOfDimensions × numberOfDimensions weight matrix for source i. The function above has no analytical solution for X and the Wi. It can be solved, however, by an iterative procedure which Carroll & Chang have christened CANDECOMP (CANonical DECOMPosition). This method minimizes, instead of the function given above, the following function:

g(X, Y, W1,..., WnumberOfSources) = ∑i=1..numberOfSources | SiXWiY′ |2

where X and Y are both numberOfPoints × numberOfDimensions configuration matrices.

The algorithm proceeds as follows:

1. Initialize the W matrices and the configuration matrix X. This can for example be done according to a procedure given in Young, Takane & Lewyckyj (1978).

2. An alternating least squares minimization process is started as described that sequentially updates Y, X an W (Carroll & Chang (1970)):

2.1. Solve for a new Y given X and the Wi
2.2. Solve for a new X given the Wi and the new Y.
2.3. Solve for the Wi given the new X and Y.

Evaluate the goodness-of-fit criterion and either repeat the minimization sequence (2.1–2.3) or continue.

3. Done: make Y equal to X and solve a last time for the Wi.

Note: during the minimization the following constraints are effective:

The configuration must be centered.
The sum of squared coordinates in the configuration space is one for each dimension, i.e., the configuration always has unit variance in each dimension.

Links to this page


© djmw, December 1, 1997