Stress Majorization

Stress majorization is an optimization strategy used in multidimensional scaling (MDS) where, for a set of n m-dimensional data items, a configuration X of n points in r(<-dimensional space is sought that minimizes the so called stress function . Usually r is 2 or 3, i.e. the (r x n) matrix X lists points in 2- or 3-dimensional Euclidean space so that the result may be visualised (i.e. an MDS plot). The function is a loss or cost function that measures the squared differences between ideal (-dimensional) 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 (their separation) in the -dimensional data space. Note that 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).

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 (in terms of guarantees on, and rate of, convergence) 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 ("Scaling by majorizing a convex function").

Read more about Stress Majorization:  The SMACOF Algorithm, Use in Graph Drawing

Famous quotes containing the word stress:

    “A society which is clamoring for choice, which is filled with many articulate groups, each urging its own brand of salvation, its own variety of economic philosophy, will give each new generation no peace until all have chosen or gone under, unable to bear the conditions of choice. The stress is in our civilization.”
    —Margaret Mead (1901–1978)