Ex. 14.11

Classical multidimensional scaling. Let \(\bb{S}\) be the centered inner product matrix with elements \(\langle x_i-\bar x, x_j-\bar x \rangle\). Let \(\lambda_1 > \lambda_2 > ... > \lambda_k\) be the \(k\) largest eigenvalues of \(\bb{S}\), with associated eigenvectors \(\bb{E}_k=(\bb{e}_1, \bb{e}_2, ..., \bb{e}_k)\). Let \(\bb{D}_k\) be a diagonal matrix with diagonal entries \(\sqrt{\lambda_1}, \sqrt{\lambda_2}, ...., \sqrt{\lambda_k}\). Show that the solutions \(z_i\) to the classical scaling problem (14.100) are the rows of the \(\bb{E}_k\bb{D}_k\).

Soln. 14.11

Similar to \(\bS\), let \(\bM\) be the be the centered inner product matrix with elements \(\langle z_i-\bar z, z_j-\bar z \rangle\), and we can write

\[\begin{equation} \bM = \begin{pmatrix} z_1^T \\ z_2^T \\ \vdots \\ z_N^T \end{pmatrix} \begin{pmatrix} z_1 & z_2 & \dots & z_N \end{pmatrix}.\non \end{equation}\]

Then (14.100) becomes

\[\begin{equation} \text{trace}[(\bS-\bM)^T(\bS-\bM)] = \|\bS-\bM\|_F^2.\non \end{equation}\]

Note that \(z_i\in \mathbb{R}^k\), the problem reduces to the best rank-\(k\) approximation for \(\bS\). Consider the eigen-decomposition of \(\bS=\bb{E}\bb{D}^2\bb{E}^T\), from Ex. 13.5, we know that

\[\begin{eqnarray} \bM &=& \sum_{l=1}^k\lambda_l\bb{e}_l\bb{e}_l^T\non\\ &=& \bb{E}_k\bb{D}_k \cdot (\bb{E}_k\bb{D}_k)^T\non\\ &=& \begin{pmatrix} \sqrt{\lambda_1}\bb{e}_1 & \sqrt{\lambda_2}\bb{e}_2 & \dots & \sqrt{\lambda_k}\bb{e}_k \end{pmatrix} \begin{pmatrix} \sqrt{\lambda_1}\bb{e}_1^T \\ \sqrt{\lambda_2}\bb{e}_2^T \\ \vdots \\ \sqrt{\lambda_k}\bb{e}_k \end{pmatrix} .\non \end{eqnarray}\]

thus we see solutions \(z_i\) correspond to the rows of \(\bb{E}_k\bb{D}_k\). Specifically, \(z_i^T\in\mathbb{R}^{1\times k}\) are the rows of \(\bb{E}_k\bb{D}_k\).