Stress majorization
Stress majorization is an optimization strategy used in multidimensional scaling where, for a set of ' '-dimensional data items, a configuration ' of points in -dimensional space is sought that minimizes the so-called stress function. Usually ' is or, i.e. the ' matrix ' lists points in or dimensional Euclidean space so that the result may be visualised. The function is a cost or loss function that measures the squared differences between ideal distances and actual distances in r-dimensional space. It is defined as:
where is a weight for the measurement between a pair of points, is the euclidean distance between and and is the ideal distance between the points in the -dimensional data space. Note that can be used to specify a degree of confidence in the similarity between points.
A configuration which minimizes gives a plot in which points that are close together correspond to points that are also close together in the original -dimensional data space.
There are many ways that could be minimized. For example, Kruskal recommended an iterative steepest descent approach. However, a significantly better method for minimizing stress was introduced by Jan de Leeuw. De Leeuw's iterative majorization method at each step minimizes a simple convex function which both bounds from above and touches the surface of at a point, called the supporting point. In convex analysis such a function is called a majorizing function. This iterative majorization process is also referred to as the SMACOF algorithm.
The SMACOF algorithm
The stress function can be expanded as follows:Note that the first term is a constant and the second term is quadratic in and therefore relatively easily solved. The third term is bounded by:
where has:
and for
and.
Proof of this inequality is by the Cauchy-Schwarz inequality, see Borg.
Thus, we have a simple quadratic function that majorizes stress:
The iterative minimization procedure is then:
- at the step we set
- stop if otherwise repeat.