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:

    “While ... we cannot and must not hide our concern for grave world dangers, and while, at the same time, we cannot build walls around ourselves and hide our heads in the sand, we must go forward with all our strength to stress and to strive for international peace. In this effort America must and will protect herself.”
    —Franklin D. Roosevelt (1882–1945)