\documentclass{article} \setlength{\oddsidemargin}{0.0in} \setlength{\textwidth}{6.5in} \setlength{\textheight}{8.5in} \setlength{\topmargin}{0.0in} \begin{document} \Large \begin{center} Classical Scaling via Torgerson and Guttman \end{center} \bigskip Torgerson Classical Scaling is based on the following result: \bigskip Let $\mathbf{A}$ be a symmetric matrix of order $n \times n$. Suppose we want to find a matrix $\mathbf{B}$ of rank 1 (of order $n \times n$) in such a way that the sum of the squared discrepancies between the elements of $\mathbf{A}$ and the corresponding elements of $\mathbf{B}$ (i.e., $\sum_{j=1}^{n} \sum_{i=1}^{n} (a_{ij} - b_{ij})^{2}$) is at a minimum. It can be shown that the solution is $\mathbf{B} = \lambda \mathbf{kk'}$ (so all columns in $\mathbf{B}$ are multiples of $\mathbf{k}$), where $\lambda$ is the largest eigenvalue of $\mathbf{A}$\ and $\mathbf{k}$ is the corresponding normalized eigenvector. This theorem can be generalized. Suppose we take the first $r$ largest eigenvalues and the corresponding normalized eigenvectors. The eigenvectors are collected in an $n \times r$ matrix $\mathbf{K} = \{\mathbf{k}_{1},\ldots,\mathbf{k}_{r}\}$ and the eigenvalues in a diagonal matrix $\mathbf{\Lambda}$. Then $\mathbf{K \Lambda K'}$ is an $n \times n$ matrix of rank $r$ and is a least-squares solution for the approximation of $\mathbf{A}$ by a matrix of rank $r$. It is assumed, here, that the eigenvalues are all positive. If $\mathbf{A}$ is of rank $r$ by itself and we take the $r$ eigenvectors for which the eigenvalues are different from zero collected in a matrix $\mathbf{K}$ of order $n \times r$, then $\mathbf{A}$ = $\mathbf{K \Lambda K'}$. Note that $\mathbf{A}$ could also be represented by $\mathbf{A} = \mathbf{LL'}$, where $\mathbf{L} = \mathbf{K \Lambda^{1/2}}$ (we factor the matrix), or as a sum of $r$ $n \times n$ matrices --- $\mathbf{A} = \lambda_{1} \mathbf{k_{1}k_{1}'} + \cdots + \lambda_{r} \mathbf{k_{r}k_{r}'}$. \bigskip \section*{Metric Multidimensional Scaling -- Torgerson's Model (Gower's Principal Coordinate Analysis)} Suppose I have a set of $n$ points that can be perfectly represented spatially in $r$ dimensional space. The $i^{th}$ point has coordinates $(x_{i1},x_{i2},\ldots,x_{ir})$. If $d_{ij} = \sqrt{\sum_{k=1}^{r} (x_{ik} - x_{jk})^{2}}$ represents the Euclidean distance between points $i$ and $j$, then \[ d_{ij}^{*} = \sum_{k=1}^{r} x_{ik}x_{jk}, \mathrm{where} \] \begin{equation} d_{ij}^{*} = - \frac{1}{2} (d_{ij}^{2} - A_{i} - B_{j} + C) ; \end{equation} \[ A_{i} = (1/n)\sum_{j=1}^{n} d_{ij}^{2} ; \] \[ B_{j} = (1/n)\sum_{i=1}^{n} d_{ij}^{2} ; \] \[ C = (1/n^{2})\sum_{i=1}^{n}\sum_{j=1}^{n} d_{ij}^{2} . \] Note that $\{d_{ij}^{*}\}_{n \times n} = \mathbf{XX'}$, where $\mathbf{X}$ is of order $n \times r$ and the entry in the $i^{th}$ row and $k^{th}$ column is $x_{ik}$. So, the Question: If I give you $\mathbf{D} = \{d_{ij}\}_{n \times n}$, find me \emph{a} set of coordinates to do it. The Solution: Find $\mathbf{D}^{*} = \{d_{ij}^{*}\}$, and take its Spectral Decomposition. This is \emph{exact} here. \bigskip To use this result to obtain a spatial representation for a set of $n$ objects given \emph{any} ``distance-like'' measure, $p_{ij}$, between objects $i$ and $j$, we proceed as follows: (a) Assume (i.e., pretend) the Euclidean model holds for $p_{ij}$. (b) Define $p_{ij}^{*}$ from $p_{ij}$ using (1). (c) Obtain a spatial representation for $p_{ij}^{*}$ using a suitable value for $r$, the number of dimensions (at most, $r$ can be no larger than the number of positive eigenvalues for $\{p_{ij}^{*} \}_{n \times n}$): \[ \{p_{ij}^{*} \} \approx \mathbf{XX'} \] (d) Plot the $n$ points in $r$ dimensional space. \section*{A Well Known General Optimization Result Justifying the Guttman Scaling Method (The Courant-Fischer Theorem)} For an $n \times n$ symmetric matrix $\mathbf{A}$, let $\lambda_{1} \geq \cdots \geq \lambda_{n}$ be its eigenvalues, and $\mathbf{P}_{1}, \ldots, \mathbf{P}_{n}$ the corresponding eigenvectors. Then, \[ \mathbf{A} = \lambda_{1}\mathbf{P}_{1}\mathbf{P}_{1}^{'} + \cdots + \lambda_{n}\mathbf{P}_{n}\mathbf{P}_{n}^{'} \] \noindent and \[ \mathbf{I} = \mathbf{P}_{1}\mathbf{P}_{1}^{'} + \cdots + \mathbf{P}_{n}\mathbf{P}_{n}^{'}\] \noindent The maximum of \[ \frac{\mathbf{X}'\mathbf{A}\mathbf{X}}{\mathbf{X}'\mathbf{X}} \] is $\lambda_{1}$, and obtained at $\mathbf{P}_{1}$; the minimum is $\lambda_{n}$, and obtained at $\mathbf{P}_{n}$; the maximum subject to being a solution orthogonal (i.e., inner products are zero) to $\mathbf{P}_{1}, \ldots, \mathbf{P}_{k}$ is $\lambda_{k+1}$, and is obtained for $\mathbf{P}_{k+1}$. \section*{A Guttman Result} If $\mathbf{B}$ is a symmetric matrix of order $n$, having all its elements non-negative, the following quadratic form defined by the matrix $\mathbf{A}$ must be positive semi-definite: \[ \sum_{i