Stress majorization
Encyclopedia
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 complicated function").
can be expanded as follows:
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
used in multidimensional scaling
Multidimensional scaling
Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
(MDS) where, for a set of n, m-dimensional data items, a configuration X of n points in r(<
. Usually r is 2 or 3, i.e. the (r x n) matrix X lists points in 2- or 3-dimensional Euclidean spaceEuclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
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 distanceEuclidean distance
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
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 LeeuwJan de Leeuw
Jan de Leeuw was born December 19, 1945, Voorburg, The Netherlands; he currently resides in Cuddy Valley, California.-Background:Jan de Leeuw is Distinguished Professor of Statistics and Founding Chair of the Department of Statistics, University of California, Los Angeles He is the founding...
. 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 analysisConvex analysis
Convex analysis is the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex minimization, a subdomain of optimization theory....
such a function is called a majorizing function. This iterative majorization process is also referred to as the SMACOF algorithm ("Scaling by majorizing a complicated function").
The SMACOF algorithm
The stress function can be expanded as follows:-
Note that the first term is a constant
and the second term is quadratic in X (i.e. for the Hessian matrixHessian matrixIn mathematics, the Hessian matrix is the square matrix of second-order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named...
V the second term is equivalent to tr
) and therefore relatively easily solved. The third term is bounded by:
-
where
has:
-
for 
and
for 
and
.
Proof of this inequality is by the Cauchy-Schwartz inequality, see Borg (pp. 152–153).
Thus, we have a simple quadratic function
that majorizes stress:
-
The iterative minimization procedure is then:
- at the kth step we set
-
- stop if
otherwise repeat.
This algorithm has been shown to decrease stress monotonically (see de Leeuw).
Use in graph drawing
Stress majorization and algorithms similar to SMACOF also have application in the field of graph drawingGraph drawingGraph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
. That is, one can find a reasonably aesthetically-appealing layout for a network or graph by minimizing a stress function over the positions of the nodes in the graph. In this case, the
are usually set to the graph-theoretic distances between nodes i and j and the weights 
are taken to be 
. Here, 
is chosen as a trade-off between preserving long- or short-range ideal distances. Good results have been shown for 
.
- at the kth step we set
-
-