Stress Majorization - The SMACOF Algorithm

The SMACOF Algorithm

The stress function can be expanded as follows:

$\sigma(X)=\sum_{i<j\le n}w_{ij}(d_{ij}(X)-\delta_{ij})^2 =\sum_{i<j}w_{ij}\delta_{ij}^2 + \sum_{i<j}w_{ij}d_{ij}^2(X)-2\sum_{i<j}w_{ij}\delta_{ij}d_{ij}(X)$

Note that the first term is a constant and the second term is quadratic in X (i.e. for the Hessian matrix V the second term is equivalent to tr) and therefore relatively easily solved. The third term is bounded by:

$\sum_{i<j}w_{ij}\delta_{ij}d_{ij}(X)=\,\operatorname{tr}\, X'B(X)X \ge \,\operatorname{tr}\, X'B(Z)Z$

where has:

for

and for

and .

Proof of this inequality is by the Cauchy-Schwartz inequality, see Borg (pp. 152–153).

Thus, we have a simple quadratic function that majorizes stress:

$\sigma(X)=C+\,\operatorname{tr}\, X'VX - 2 \,\operatorname{tr}\, X'B(X)X\le C+\,\operatorname{tr}\, X' V X - 2 \,\operatorname{tr}\, X'B(Z)Z = \tau(X,Z)$

The iterative minimization procedure is then:

at the kth step we set
stop if otherwise repeat.

This algorithm has been shown to decrease stress monotonically (see de Leeuw).

Read more about this topic: Stress Majorization