Stress majorization is an optimization strategy used in multidimensional scaling (MDS) where, for a set of
-dimensional data items, a configuration
-dimensional space is sought that minimizes the so-called stress function
dimensional Euclidean space so that the result may be visualised (i.e. an MDS plot).
is a cost or loss function that measures the squared differences between ideal (
-dimensional) distances and actual distances in r-dimensional space.
is a weight for the measurement between a pair of points
is the euclidean distance between
is the ideal distance between the points (their separation) in the
-dimensional data space.
can be used to specify a degree of confidence in the similarity between points (e.g. 0 can be specified if there is no information for a particular pair).
gives a plot in which points that are close together correspond to points that are also close together in the original
-dimensional data space.
For example, Kruskal[1] recommended an iterative steepest descent approach.
However, a significantly better (in terms of guarantees on, and rate of, convergence) method for minimizing stress was introduced by Jan de Leeuw.
[2] De Leeuw's iterative majorization method at each step minimizes a simple convex function which both bounds
from above and touches the surface of
, 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 ("Scaling by MAjorizing a COmplicated Function").
can be expanded as follows: Note that the first term is a constant
the second term is equivalent to tr
Proof of this inequality is by the Cauchy-Schwarz inequality, see Borg[3] (pp. 152–153).
Thus, we have a simple quadratic function
The iterative minimization procedure is then: This algorithm has been shown to decrease stress monotonically (see de Leeuw[2]).
Stress majorization and algorithms similar to SMACOF also have application in the field of graph drawing.
[4][5] That is, one can find a reasonably aesthetically appealing layout for a network or graph by minimizing a stress function over the positions of the nodes in the graph.
are usually set to the graph-theoretic distances between nodes
is chosen as a trade-off between preserving long- or short-range ideal distances.
Good results have been shown for