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:

    “Anyone who wishes to combine domestic responsibilities and paid employment with the least stress and most enjoyment might start by pondering this paradox: the first step to better functioning is to stop blaming herself for not functioning well enough.”
    —Faye J. Crosby (20th century)