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:

    “It is not stressful circumstances, as such, that do harm to children. Rather, it is the quality of their interpersonal relationships and their transactions with the wider social and material environment that lead to behavioral, emotional, and physical health problems. If stress matters, it is in terms of how it influences the relationships that are important to the child.”
    —Felton Earls (20th century)