1 Answers
Stress majorization is an optimization strategy used in multidimensional scaling where, for a set of n {\displaystyle n} m {\displaystyle m} -dimensional data items, a configuration X {\displaystyle X} of n {\displaystyle n} points in r {\displaystyle r} {\displaystyle } -dimensional space is sought that minimizes the so-called stress function σ {\displaystyle \sigma }. Usually r {\displaystyle r} is 2 {\displaystyle 2} or 3 {\displaystyle 3} , i.e. the {\displaystyle } matrix X {\displaystyle X} lists points in 2 − {\displaystyle 2-} or 3 − {\displaystyle 3-} dimensional Euclidean space so that the result may be visualised. The function σ {\displaystyle \sigma } 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 w i j ≥ 0 {\displaystyle w_{ij}\geq 0} is a weight for the measurement between a pair of points {\displaystyle } , d i j {\displaystyle d_{ij}} is the euclidean distance between i {\displaystyle i} and j {\displaystyle j} and δ i j {\displaystyle \delta _{ij}} is the ideal distance between the points in the m {\displaystyle m} -dimensional data space. Note that w i j {\displaystyle w_{ij}} can be used to specify a degree of confidence in the similarity between points.
A configuration X {\displaystyle X} which minimizes σ {\displaystyle \sigma } gives a plot in which points that are close together correspond to points that are also close together in the original m {\displaystyle m} -dimensional data space.
There are many ways that σ {\displaystyle \sigma } 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 σ {\displaystyle \sigma } from above and touches the surface of σ {\displaystyle \sigma } at a point Z {\displaystyle Z} , 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.