\documentclass{slides}
\begin{document}
\begin{slide}
\begin{center}
SOME MATLAB-BASED METHODS OF
USE IN COGNITIVE PSYCHOLOGY:
ULTRAMETRICS, ADDITIVE TREES,
ANTI-ROBINSON FORMS,
MULTIDIMENSIONAL (CITY-BLOCK)
SCALING, OH MY!
Lawrence Hubert
University of Illinois
\end{center}
\end{slide}
\begin{slide}
\begin{center}
DATA REPRESENTATION USES OF AN
ITERATIVE PROJECTION STRATEGY
FOR SOLVING LINEAR SYSTEMS
OF EQUATIONS
\end{center}
\end{slide}
\begin{slide}
A common problem in linear algebra:
Given $\mathbf{A} = \{a_{ij}\}$ of order $m \times n$, $\mathbf{x}' = \{x_{1},\ldots,x_{n}\}$, $\mathbf{b}' = \{b_{1},\ldots,b_{m}\}$, and assuming the linear system $\mathbf{Ax} = \mathbf{b}$ is consistent, find $\mathbf{x}$.
Matrix factorization may be the most well-known strategy for solving such linear systems of equations, but another method, typically attributed to Kaczmarz (1937) and based on an iterative projection strategy, could also be used.
The latter has some very close connections with several more recent approaches in the applied statistics/psychometrics literature to the representation of a data matrix.
A close relative to the Kaczmarz strategy is known as Dykstra's method for solving linear inequality constrained weighted least-squares tasks (JASA, 1983).
\end{slide}
\begin{slide}
Kaczmarz's method can be characterized as follows:
Define the set $C_{i} = \{\mathbf{x} \ | \ \sum_{j=1}^{n} a_{ij} x_{j} = b_{i}\}$, for $1 \leq i \leq m$.
The projection of any $n \times 1$ vector $\mathbf{y}$ onto $C_{i}$ is simply $\mathbf{y} - (\mathbf{a}_{i}' \mathbf{y} - b_{i}) \mathbf{a}_{i}(\mathbf{a}_{i}' \mathbf{a}_{i})^{-1}$, where $\mathbf{a}_{i}' = \{a_{i1},\ldots,a_{in}\}$.
Begin with a vector $\mathbf{x}_{0}$, and successively project $\mathbf{x}_{0}$ onto $C_{1}$, and that result onto $C_{2}$, and so on, and cyclically and repeatedly reconsidering projections onto the sets $C_{1},\ldots,C_{m}$.
At convergence we have a vector $\mathbf{x}_{0}^{*}$ closest (in vector 2-norm) to $\mathbf{x}_{0}$ satisfying $\mathbf{Ax}_{0}^{*} = \mathbf{b}$.
\end{slide}
\begin{slide}
Dykstra's method can be characterized as follows:
Given $\mathbf{A} = \{a_{ij}\}$ of order $m \times n$, $\mathbf{x}_{0}' = \{x_{01},\ldots,x_{0n}\}$,
$\mathbf{b}' = \{b_{1},\ldots,b_{m}\}$, and $\mathbf{w}' = \{w_{1},\ldots,w_{n}\}$, where $w_{j} > 0$ for all $j$, find $\mathbf{x}_{0}^{*}$ such that $\mathbf{a}_{i}' \mathbf{x}_{0}^{*} \leq b_{i}$ for $1 \leq i \leq m$ and $\sum_{i=1}^{n} w_{i} (x_{0i} - x_{0i}^{*})^{2} $ is minimized.
Again, (re)define the (closed convex) sets $C_{i} = \{ \mathbf{x} \ | \ \sum_{j=1}^{n} a_{ij} x_{j} \leq b_{i} \}$ and when a vector $\mathbf{y} \notin C_{i}$, its projection onto $C_{i}$ (in the metric defined by the weight vector $\mathbf{w}$) is
$\mathbf{y} - (\mathbf{a}_{i}' \mathbf{y} - b_{i})\mathbf{a}_{i}\mathbf{W}^{-1}(\mathbf{a}_{i}'\mathbf{W}^{-1}\mathbf{a}_{i})^{-1}$,
where $\mathbf{W}^{-1} = \mathrm{diag} \{w_{1}^{-1},\ldots,w_{n}^{-1}\}$.
\end{slide}
\begin{slide}
We again initialize the process with the vector $\mathbf{x}_{0}$ and each set $C_{1},\ldots,C_{m}$ is considered in turn.
If the vector being carried forward to this point when $C_{i}$ is (re)considered does not satisfy the constraint defining $C_{i}$, a projection onto $C_{i}$ occurs.
The sets $C_{1},\ldots,C_{m}$ are cyclically and repeatedly considered but with one difference from the operation of Kaczmarz's method --- each time a constraint set $C_{i}$ is revisited, any changes from the previous time $C_{i}$ was reached are first ``added back''.
This last process ensures convergence to an optimal solution $\mathbf{x}_{0}^{*}$ (see Dykstra, 1983).
\end{slide}
\begin{slide}
The Dykstra method is currently serving as the major computational tool for a variety of newer data representation devices in applied statistics/psychometrics.
For an arbitrary symmetric proximity matrix $\mathbf{A}$ (of order $p \times p$ and with diagonal entries typically set to zero), a number of applications of Dykstra's method have been discussed for approximating $\mathbf{A}$ in a least-squares sense by $\mathbf{A}_{1} + \cdots + \mathbf{A}_{K}$, where $K$ is typically small (e.g., 2 or 3) ---
each $\mathbf{A}_{k}$ is patterned in a particularly informative way that can be characterized by a set of linear inequality constraints that its entries should satisfy.
\end{slide}
\begin{slide}
We will note three exemplar classes of patterns that $\mathbf{A}_{k}$ might have, and all with a substantial history in the AS/P literature.
In each instance, Dykstra's method can be used to fit the additive structures satisfying the inequality constraints once they are identified,
possibly through an initial combinatorial optimization task seeking an optimal reordering of a given (residual) data matrix,
or in some instances in a heuristic form to identify the constraints to impose in the first place.
\end{slide}
\begin{slide}
Linear and circular unidimensional scales:
The entries in $\mathbf{A}_{k}$ should be represented by a linear unidimensional scale:
$a_{ij(k)} = |x_{j} - x_{i}|$ for some set of coordinates $x_{1},\ldots,x_{n}$;
(or $|x_{j} - x_{i}| - c$, for an additional additive constant $c$)
or a circular unidimensional scale:
$a_{ij(k)} = \min \{ |x_{j} - x_{i}|, \ x_{0} - |x_{j} - x_{i}| \}$ for some set of coordinates $x_{1},\ldots,x_{n}$ and $x_{0}$ representing the circumference of the circular structure
(or $\min \{ |x_{j} - x_{i}|, \ x_{0} - |x_{j} - x_{i}| \} - c$, for an additional additive constant $c$)
\end{slide}
\begin{slide}
Ultrametric and additive trees:
The entries in $\mathbf{A}_{k}$ should be represented by an ultrametric:
for all $i, j,$ and $h$, $a_{ij(k)} \leq \max \{a_{ih(k)}, a_{jh(k)} \}$;
(or equivalently, among $a_{ij(k)}$, $a_{ih(k)}$, and $a_{jh(k)}$, the largest two values are equal)
or an additive tree:
for all $i, j, h,$ and $l$, $a_{ij(k)} + a_{hl(k)} \leq \max \{a_{ih(k)} + a_{jl(k)}, a_{il(k)} + a_{jh(k)}\}$.
(or equivalently, among $a_{ij(k)} + a_{hl(k)}$, $a_{ih(k)} + a_{jl(k)}$, and $a_{il(k)} + a_{jh(k)}$, the largest two values are equal)
\end{slide}
\begin{slide}
Order constraints:
The entries in $\mathbf{A}_{k} = \{a_{ij(k)}\}$ should satisfy the anti-Robinson constraints:
there exists a permutation on the first $p$ integers $\rho(\cdot)$ such that $a_{\rho(i) \rho(j)(k)} \leq a_{\rho(i) \rho(j')(k)}$ for $1 \leq i < j < j' \leq p$,
and $a_{\rho(i) \rho(j)(k)} \leq a_{\rho(i') \rho(j)(k)}$ for $1 \leq i < i' < j' \leq p$.
\end{slide}
\begin{slide}
MATLAB (Matrix Laboratory) ---
The computational environment we should be universally expecting to learn and use.
Basic Matlab:
(a) The Mother of all calculators --- where everything can be done with matrices
(b) Programming language --- very powerful and much easier than, for example, C or Fortran (no array dimensioning)
(c) Graphical User Interface Development Environment (GUIDE) --- do your own data collection GUIs or demonstrations
(d) Provides great graphics --- plotting, visualization, animation, image processing
(e) Application Program Interface (API) --- for calling C, Fortran, JAVA routines within the Matlab environment
\end{slide}
Toolboxes (collection of m-files to do analyses within some specific area, and where typically the source code in the m-files is available for modification)
Commercial (though the Mathworks or third-parties) Toolboxes ---
Statistics; Optimization; Image Processing; Neural Networks; Curve Fitting; Splines; Wavelets; Symbolic Math; Bioinformatics; Genetic Algorithm and Direct Search; Mapping (Geographical);
Compiler (m-files direct to C or C++ code)
\begin{slide}
Free (open sources) Toolboxes ---
www.mathworks.com/matlabcentral/ --- 1000 m-files contributed by users
www.mathtools.net/MATLAB/toolboxes.html
Auditory Perception; ILAB (eye movement analyses); Brainstorm (MEG/EEG); Chemometrics; N-way Toolbox; Smoothing; Econometrics; Spatial Statistics; NURBS; ICA (EEG/ERP -- independent component analysis); LYNGBY (fMRI analyses); NIH CORTEX; NMRLAB; Psychophysics; Speech Processing
\end{slide}
\begin{slide}
The Structural Representation of Proximity Matrices With MATLAB ---
This is the Combinatorial Data Analysis (CDA) Toolbox I'm working on
and is available at (my office on the fourth floor):
http://ljhoff.psych.uiuc.edu/cda\_toolbox ---
cda\_toolbox\_manual.pdf
mfile\_headers.pdf
all the m-files I've written for the toolbox
all the *.dat files for the data analysis examples
\end{slide}
\begin{slide}
As two examples of how MATLAB has become the medium for sharing work,
check out ---
http://ljhoff.psych.uiuc.edu/lee\_files
http://ljhoff.psych.uiuc.edu/lee\_site
http://ljhoff.psych.uiuc.edu/Res
\end{slide}
\end{document}