Stress majorization

The stress function \sigma can be expanded as follows: : \sigma(X)=\sum_{i Note that the first term is a constant C and the second term is quadratic in X (i.e. for the Hessian matrix V the second term is equivalent to trX'VX) and therefore relatively easily solved. The third term is bounded by: : \sum_{i where B(Z) has: : b_{ij}=-\frac{w_{ij}\delta_{ij}}{d_{ij}(Z)} for d_{ij}(Z)\ne 0, i \ne j and b_{ij}=0 for d_{ij}(Z)=0, i\ne j and b_{ii}=-\sum_{j=1,j\ne i}^n b_{ij}. Proof of this inequality is by the Cauchy-Schwarz inequality, see Borg (pp. 152–153). Thus, we have a simple quadratic function \tau(X,Z) that majorizes stress: : \sigma(X)=C+\,\operatorname{tr}\, X'VX - 2 \,\operatorname{tr}\, X'B(X)X : \le C+\,\operatorname{tr}\, X' V X - 2 \,\operatorname{tr}\, X'B(Z)Z = \tau(X,Z) The iterative minimization procedure is then: • at the k^{th} step we set Z\leftarrow X^{k-1} • X^k\leftarrow \min_X \tau(X,Z) • stop if \sigma(X^{k-1})-\sigma(X^{k}) 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 drawing. 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 \delta_{ij} are usually set to the graph-theoretic distances between nodes i and j and the weights w_{ij} are taken to be \delta_{ij}^{-\alpha}. Here, \alpha is chosen as a trade-off between preserving long- or short-range ideal distances. Good results have been shown for \alpha=2. == References ==