\documentclass[12pt]{article}  
\usepackage{epsfig}

\title{Some Intuitions behind PCA} 

\author{William W. Cohen}

\begin{document}

\maketitle

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\newcommand{\trm}[1]{{\it {#1}}}
\newcommand{\vek}[1]{\mbox{\bf #1}}
%\newcommand{\vek}[1]{{\vec{#1}}}
\newcommand{\vu}{\vek{u}}
\newcommand{\vv}{\vek{v}}
\newcommand{\vw}{\vek{w}}
\newcommand{\vx}{\vek{x}}
\newcommand{\vy}{\vek{y}}
\newcommand{\vz}{\vek{z}}
\newcommand{\sign}{{\rm sign}}
\newcommand{\norm}[1]{{|\!|{#1}|\!|}}
\newcommand{\normSq}[1]{{|\!|{#1}|\!|}^2}

\newcommand{\matWithRows}[1]{\left[\begin{array}{c}
                                    \vdots\\%
                                    -~ {#1} ~-\\%
                                    \vdots%
                                   \end{array}\right]}
\newcommand{\matWithCols}[1]{\left[\begin{array}{ccc}
                                          &|&  \\%
                                    \ldots&{#1}&\ldots\\%
                                          &|& \\%
                                   \end{array}\right]}

\section{The covariance matrix $C_X$}

Consider a data matrix $X$ where the $t$-th row corresponds to an
instance $\vx^t$, with $n$ instances each with $m$ features.
\[ X = 
    \left[ 
      \begin{array}{llll}
        x^1_1  & x^1_2  & \ldots & x^1_m \\
        \vdots & \ddots &        & \vdots \\
        x^n_1  & \ldots &        & x^n_m\\
      \end{array}
    \right] = \matWithRows{\vek{x}^t}
\]
Sometimes, to remind myself I'm talking about feature values, I will
use $f_j^t$ to denote the $j$-th feature of $\vx^t$ (aka, $X(t,j)$)
Likewise I will use $\vek{f}_i$ to denote the $i$-th column vector of
$X$: the vector of all values taken on by the $i$-th feature of the
examples. 
\[ X = 
    \left[ 
      \begin{array}{llll}
        x^1_1  & x^1_2  & \ldots & x^1_m \\
        \vdots & \ddots &        & \vdots \\
        x^n_1  & \ldots &        & x^n_m\\
      \end{array}
    \right] = \matWithCols{\vek{f}_i}
\]
If you like, $\vek{f}_i$ is a ``signature'' of the $i$-th feature on
the dataset $X$.  Sometimes I will use $F_i$ for the corresponding
random variable.

A first observation: consider the matrix $C_X = X^T X$, whose entries
are the pairwise inner products, not of the instances $\vx^t$, but of
the column vectors $\vek{f}_i$ of the matrix $X$. So the entries of
$C_X$ measure the similarity of two features:
\[
   C_X(i,j) = \sum_t f^t_i f^t_j
\]
The notation $C_X$ is chosen because if $X$ has a zero mean, then
$\frac{1}{n} C_X(i,j)$ is the \emph{sample covariance} of features $i$
and $j$ on the sample $X$.

if you're happier thinking about discrete features, then another way
of thinking about this is the following: if the features $f_i$ are
always $+1$ or $-1$, then define
\[ {\rm AGREE}(i,j) = \mbox{number of examples $\vx^t\in{}X$ where $f^t_i\not=f^t_j$}
\] 
and define ${\rm DISAGREE}(i,j)$ analogously.  It is also true that
\[
   C_X(i,j) = {\rm AGREE}(i,j) - {\rm DISAGREE}(i,j)
\]
and that
\[
   \frac{1}{n}C_X(i,j) = P(f^t_i=f^t_j) - P(f^t_i\not=f^t_j)
\]
where the probabilities are the empirical probabilities taken over the
sample $X$.  To summarize: $C_X(i,j)$ is (some sort of) measure of
agreement between the features $\vek{f}_i$ ande $\vek{f}_j$, and if
for all the features $f^t_i \in \{+1,-1\}$, then $C_X(i,j)\in[-1,+1]$.

\section{Eigenvectors of $C_X$ are ``consistent predictors''}

Suppose I wanted to predict the likely value of $F_i$ from another
feature $F_j$.  If these were Gaussians with zero means and unit
variances, I would naturally estimate using $f_i \approx C(i,j) f_j$.

This is easiest if $C_X(i,j)$ is close to an extreme;
then the obvious cases are
\begin{itemize}
\item $C_X(i,j) \approx +1$ and $F_j = +1$: predict $F_i= +1$.
\item $C_X(i,j) \approx -1$ and $F_j = +1$: predict $F_i= -1$.
\item $C_X(i,j) \approx +1$ and $F_j = -1$: predict $F_i= -1$.
\item $C_X(i,j) \approx -1$ and $F_j = -1$: predict $F_i= +1$.
\end{itemize}
On the other hand, if $C_X(i,j)\approx 0$, then it seems that no
prediction for $F_i$ can be made confidently.  So a simple formula for
predicting $F_i$ from $F_j$ using a single real number in $[-1,+1]$,
where small predicted values indicate low confidence, might be
\[ f_i \mbox{~is predicted as~} C_X(i,j)\cdot{}f_j \]

Of course, $f_i$ could be predicted just as easily from $f_{j'}$ for
$j'\not=j$.  If I wanted to combine all of these predictions I might
weight them all equally to get
\begin{equation} \label{eq:predict}
 f_i \mbox{~is predicted as~} \frac{1}{n} \sum_{j\not=i} C_X(i,j)\cdot{}f_j 
\end{equation}

Now, suppose I want to predict an entire instance $\vek{e}$ that is
``likely'' according to the sample $X$.  A natural goal is a set of
feature values $\vek{e}=\langle e_1,\ldots,e_m\rangle$ that are
internally consistent with respect to the (confidence-weighted)
prediction scheme of Equation~\ref{eq:predict}, i.e., a potential
instance $\vek{e}$ where
\[ \forall i, e_i = \frac{1}{n} \sum_j C_X(i,j) e_j
\]
A slightly weaker condition would be that there's some constant $\lambda$ so that
\[ \forall i, \lambda e_i = \frac{1}{n} \sum_j C_X(i,j) e_j
\]
or in other words
\[
  \exists \lambda: \lambda \vek{e} = C_X \vek{e}
\]
or in still other words, \emph{$\vek{e}$ is an eigenvector of $C_X$}.

To summarize: eigenvectors $\vek{e}^i$ of $C_X$ are the same length as
instances $\vx$, and they have the nice property that their feature
values are internally consistent with respect to the (admittedly
simple-minded) prediction scheme of Equation~\ref{eq:predict}.

The eigenvectors are thus broadly similar to clusters in k-means, or
mixture components in a generative model, in that some subsets of the
features can be used to predict the other features' values.

\section{Using the consistent predictors}

Let $\vek{e}^1,\ldots,\vek{e}^m$ be the eigenvectors of $C_X$, in
decreasing order by their eigenvalues, and let $\Lambda$ be the
diagonal matrix of eigenvalues.  Let $E$ be a matrix where the row
vectors are the $\vek{e}^i$'s, and let $E_k$ be a matrix with just the 
first $k$ eigenvectors:
\[ E = 
    \left[ 
      \begin{array}{llll}
        e^1_1  & e^1_2  & \ldots & e^1_m \\
        \vdots & \ddots &        & \vdots \\
        e^k_1  & \ldots &        & e^k_m\\
      \end{array}
    \right] = \matWithRows{\vek{e}^i}
\]
Let's consider the matrix product $Z = X E^T$, or more interestingly perhaps,
the matrix $Z_k = X E_k^T$:
\[ Z_k = 
    \left[ 
      \begin{array}{llll}
        x^1_1  & x^1_2  & \ldots & x^1_m \\
        \vdots & \ddots &        & \vdots \\
        x^n_1  & \ldots &        & x^n_m\\
      \end{array}
    \right]
    \times 
    \left[ 
      \begin{array}{llll}
        e^1_1  & e^2_1  & \ldots & e^1_k \\
        e^1_2  & e^2_2  & \ldots & e^2_k \\
        \vdots & \ddots &        & \vdots \\
        e^1_m  & \ldots &        & e^m_k\\
      \end{array}
    \right]
    = 
    \left[ 
      \begin{array}{llll}
        \vx^1\cdot\vek{e}^1  & \vx^2\cdot\vek{e}^2  & \ldots & \vx^1\cdot\vek{e}^k \\
        \vdots & \ddots &        & \vdots \\
        \vx^n\cdot\vek{e}^1  & \vx^n\cdot\vek{e}^2  & \ldots & \vx^n\cdot\vek{e}^k \\
      \end{array}
    \right]
\]
This matrix has one row $\vz^t$ for each instance $\vx^t$, but the
columns (features) are different.  Instead of the original feature
space, we now have the values 
\[ \vz^t 
  = \langle z^t_1, \ldots, z^t_k \rangle
  = \langle \vx^t\cdot\vek{e}^1,\ldots,\vx^t\cdot\vek{e}^k \rangle
\]
If you think of dot-product as kind of similarity score (as I do) then
\emph{the $i$-th feature of $\vz^t$ is the similarity of $\vx^t$ to
  the $i$-th eigenvector $\vek{e}^i$}.  In otherwords, the instances
$\vx^t$ have been mapped to a new space where each dimension indicates
how similar/different the instance $\vx^t$ to some
consistently-predictable potential instance.

If you again think of the eigenvectors as similar to clusters, or
mixture components, the new space that $\vx^t$ has been mapped into is
like a space of posteriors for the components.

\section{From PCA to SVD}

We started out looking at the correlations between the variables of
$X$, by computing the dot-products of the ``feature signatures''
$\vek{f}_i$, via computing $C_X=X^TX$.  What if we do the same trick
to $Z$?  It turns out the answer is ``not much'': in particular, the
corresponding signatures in $Z$ are not correlated.

Let's use $\vek{g}_i$ for the $i$-th column of $Z$: 
\[  Z  = X E^T = \matWithRows{\vek{z}^t} = \matWithCols{\vek{g}_i}
\]
In $C_Z = Z^T Z$, what do the entries look like?  Well,
\[ C_Z(i,j) = \vek{g}_i \cdot \vek{g}_j
\]
and, treating $\vek{e}^j$ as a column vector, $\vek{g}_i = X\vek{e}_i$.
So 
\begin{eqnarray*}
C_Z(i,j) & = & \vek{g}_i \cdot \vek{g}_j \\
         & = & \vek{g}_i^T \vek{g}_j \\
         & = & (X\vek{e}_i)^T  (X\vek{e}_j)\\
         & = & \vek{e}_i^T X^T X \vek{e}_j\\
         & = & \vek{e}_i^T (X^T X) \vek{e}_j\\
         & = & \vek{e}_i^T \lambda_j \vek{e}_j \\
         & = & \lambda_j \vek{e}_i^T  \vek{e}_j
\end{eqnarray*}
the last step holding since $\vek{e}_j$ is an eigenvector of $X^TX$.
If we assume we have scaled the $\vek{e}_i$'s to unit L2 norm, and
recall that the eigenvectors are all orthogonal, then we finally get
that
\[ 
   C_Z(i,j)  = \left\{ \begin{array}{ll}
                         \lambda_i & \mbox{if $i=j$} \\
                         0 & else
                       \end{array}
               \right.     
\]
So $Z$ is a somewhat special transformation of $X$: in this
transformed space, the correlation coefficient between any pair of
distinct variables is zero, and the variance of each individual
variable is $\lambda_i$.  

If we like, we can also rescale $Z$ so that it has unit variances as
well.  Let $\Sigma$ be a diagonal matrix with
$\Sigma(i,i)={\sqrt{\lambda_i}}$, and consider $U=Z\Sigma^{-1}$.
It's pretty simple to show that $U^T U = I$.

So this suggests some alternative ways to represent the original
matrix X.  Since $Z = X E^T$, and $Z=U\Sigma$, we have
\begin{eqnarray*}
X E^T & = & Z \\
X     & = & Z E \\
X     & = & U \Sigma E
\end{eqnarray*}
So now X is decomposed into a product of three factors,
\begin{itemize}
\item $U$, a unit-variance matrix with uncorrelated features, formed
  by projecting $X$ using PCA and scaling;
\item $\Sigma$, a diagonal matrix; and
\item $E$, the matrix of eigenvectors of $C_X$, aka ``to
  self-consistent predictions''.
\end{itemize}
This is called SVD, the \emph{singular valued decomposition} for $X$:
the ``decomposition'' is factoring $X$, and the ``singular values''
are the diagonal elements of $\Sigma$.
The more usual notation is 
\[ X      =  U \Sigma V
\] 

An important point is that we can replace $Z$ with $Z_k$ and $\Sigma$
with $\Sigma_k$ (the first $k$ rows and columns of $\Sigma$).  The
full decomposition then becomes
\[ X \approx Z_k E_k = U_k \Sigma_k E_k = U_k \Sigma_k V_k
\] 
Note here are $Z_k$ is a tall narrow matrix ($n$ rows and $k$
columns), and hence so is $U_k$, $\Sigma_k$ is a square matrix, and
$E_k$ (aka $V_k$) is a long wide matrix $k$ rows and $n$ columns).
Again, the rows of $Z_k$ (and hence $U_k)$ corresponding to instances
$\vek{x}^t$, represented by their similarity to the first few
eigenvectors $\vek{e}_1$,\ldots,$\vek{e}_k$. The rows of $E_k$ (aka
$V_k$) correspond to hypothetical instances that are
``self-consistent'' according to $C_X$.

\end{document}

