The Majorization Method for MDS

The first is an algorithm for multidimensional scaling, developed by De Leeuw [1977]. We want to minimize $$\sigma(X)=\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m w_{ij}(\delta_{ij}-d_{ij}(X))^2,$$ with $d_{ij}(X)$ again Euclidean distance, i.e. $$d_{ij}(X)=\sqrt{(x_i-x_j)'(x_i-x_j)}.ƒ$$ We suppose weights $w_{ij}$ and dissimilarities $\delta_{ij}$ are symmetric and hollow (zero diagonal), and satisfy $$\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m w_{ij}\delta_{ij}^2=1.$$ We now define the following objects $$\begin{align} \eta^2(X)&\mathop{=}\limits^{\Delta}\sum_{i=1}^m\sum_{j=1}^m w_{ij}d_{ij}(X)^2,\\ \rho(X)&\mathop{=}\limits^{\Delta}\sum_{i=1}^m\sum_{j=1}^m w_{ij}\delta_{ij}d_{ij}(X). \end{align}$$ Thus $$\sigma(X)=1-2\rho(X)+\frac{1}{2}\eta^2(X).$$ The next step is to use matrices. Let $$\begin{align} v_{ij}&= \begin{cases}-w_{ij}& \text{if $i\not= j,$}\\ \sum_{k\not=i}^m w_{ik}& \text{if $i=j$,} \end{cases}\\ b_{ij}(X)&= \begin{cases} -\frac{w_{ij}\delta_{ij}}{d_{ij}(X)}& \text{if $i\not= j,$}\\ \sum_{k\not=i}^m\frac{w_{ik}\delta_{ik}}{d_{ik}(X)}& \text{if $i=j$.} \end{cases} \end{align}$$ Now $\sigma(X)=1-\hbox{tr}X'B(X)X+\frac{1}{2}\text{tr}X'VX.$ By Cauchy-Schwarz, $d_{ij}(X)\geq\frac{(x_i-x_j)'(y_i-y_j)}{d_{ij}(Y)},$ which implies $\hbox{tr}X'B(X)X\geq\hbox{tr}X'B(Y)Y.$ Now let $\overline X=V^+B(X)X.$ This is called the Guttman-transform of a matrix $X.$ Using this transform we see that for all pairs of configurations $(X,Y)$ $$\begin{align} \sigma(X)&\leq 1-\hbox{tr }X'B(Y)Y+\frac{1}{2}\text{tr }X'VX=\\ &=1-\hbox{tr }XV\overline Y+\frac{1}{2}\text{tr }X'VX=\\ &=1-\frac{1}{2}\text{tr }\overline Y'V\overline Y+ \frac{1}{2}\text{tr }(X-\overline Y)'V(X-\overline Y), \end{align}$$ while for all configurations $X$ we have $$\sigma(X)=1-\frac{1}{2}\text{tr }\overline X'V\overline X+ \frac{1}{2}\text{tr }(X-\overline X)'V(X-\overline X).$$