Most of the material in this notebook is from the following textbook: [Pattern Recognition and Machine Learning-ch-12](http://users.isr.ist.utl.pt/~wurmd/Livros/school/Bishop%20-%20Pattern%20Recognition%20And%20Machine%20Learning%20-%20Springer%20%202006.pdf)


### Mathematical Discussion of PCA - Content

1. [Notation](#notation)

2. [What is PCA?](#what_is_pca)

3. [The idea behind PCA](#the_idea_behind_pca)

4. [The mathematics of PCA](#mathematics_of_pca)

5. [Solving maximization problem](#solving_maximization_problem)

5. [Conclusion](#conclusion)



### Notation [↩](#content)
[](#notation)

- A vector in $\mathbb{R}^{n}$ is written as $\vec{u} = (u_1, \cdots, u_{n})$. So when we think a vector as an $n\times1$ matrix, we represent it as a column vector:

$$ \vec{u} = \begin{bmatrix}
    u_1 \\
    u_2 \\
    \vdots\\
    u_n
\end{bmatrix}_{ n\times1}$$

with this notation the transpose of a vector is a $1\times n$ matrix:

$$
\vec{u}^{\top} = \begin{bmatrix}
    u_1 & u_2 & \cdots & u_n
\end{bmatrix}_{ 1\times n}
$$

Note that for simplicity, we will omit '$\to$' symbol whenever the computations are complicated.
- For the dot-product we can use any of the following notations:

 - If we think of vectors abstractly: $u \cdot v = v \cdot u = u_1 v_1 + \cdots + u_n v_u$
 
 - If we consider vectors as $n\times 1$ matrices: 
 
 $$
 u^{\top}\cdot v = \begin{bmatrix}
    u_1 & u_2 & \cdots & u_n
\end{bmatrix}\begin{bmatrix}
    v_1 \\
    v_2 \\
    \vdots\\
    v_n
\end{bmatrix} = v^{\top}\cdot u =  \begin{bmatrix}
    v_1 & v_2 & \cdots & v_n
\end{bmatrix}\begin{bmatrix}
    u_1 \\
    u_2 \\
    \vdots\\
    u_n
    \end{bmatrix}
     = u_1 v_1 + \cdots + u_n v_n
 $$
 - Note that the dot product of two vector coincides with the matrix multiplication of them when we consider these vector as $n\times 1$-matrices.
 
### What is PCA? [↩](#content)
[](#what_is_pca)

PCA is an algorithm that allows us to reduce the number of features by finding special directions in the dataset that explains the variation more efficiently. In this notebook we would like to understand why this is useful and how this algorithm works mathematically. 



Suppose we would like to work with a dataset of dimension $N\times D$. This means we have N-observations and D-features. Note that such dataset can be represented as an $N$ by $D$ matrix $X$. Our goal is to find a direction (a vector of dimension $N$) such that the projection of the dataset $X$ onto the line through this direction will have maximum variance. 

__Note 1__ Even though this algorithm is very similar to the least square method here we don't have any 'target' variable. 

__Note 2__ This algorithm can be applied to the dataset iteratively to explain more variance in the dataset and then we can stop after we reach a certain criteria or a number of dimensions.

__Note 3__ Even though this is a dimension reduction algorithm, PCA is not a feature extraction technique. We will see that each 'special' direction will be expressed as the linear combinations of the all initial features. So at the end we will end up with less features but to create them we need all of the initial features. 

__Note 4__ If you have linear algebra background, PCA is basically writing the dataset matrix in a new basis formed by the eigenvectors of the covariance matrix of $X$.

### The idea behind PCA - a very simple case: Dimension reduction from 2 --> 1[↩](#content)
[](#the_idea_behind_pca)

To understand the essence of PCA algorithm and dive into mathematics of it, let's consider the following simple case below. The data is two dimensional and each observation is marked with a pink dot. Here the green line is called __the first principal direction__ and the projections of the datapoints on this line is given by the dashed lines. Note that, we choose the green line among all other lines passing through the origin so that if we would choose another line variance of the projections on this line would be smaller.




After we find the first principal direction, we will choose the second principal direction as a direction which is perpendicular to the first and explains most of the remaining variance. Here since there are only two dimensions the other direction is determined immediately after the first direction. After we find principal directions, we will use these directions as 'axis' and the projections of the datapoints as the 'new' components of the dataset.



([Image source](http://www-bcf.usc.edu/~gareth/ISL/))

Now, if we want to reduce the dimension from two to one then we can drop the second principal direction and just work with the projection of data onto the first principal direction. PCA guarantees that this is the best choice in terms of capturing the variance in the dataset. 

As we can see, this algorithm implicitly assumes that the information(signal) comes from variance of the data and small variance contains a little information hence can be considered as noise. With this motivation, this algorithm iteratively finds the directions that captures the most of the variance and also records how much variance is left after the projections. This allow us to reduce dimension with a control over the loss of information.


## Mathematics of PCA:[↩](#content)
[](#mathematics_of_pca)

### Maximum Variance Formulation

There are two different formulation that give us the algorithm of PCA. One of them is the one that we mentioned above and the other one is to minimum error formulation. We will first look at the mathematics behind the maximum variance formulation.


Suppose we are given a dataset with $N$-observations(rows) and $D$-features(columns). We will denote this dataset with $X$ and mathematicall $X$ is a matrix of shape $N \times D$. In this setting, each observation is represented by a $D$ dimensional vector which we will denote by $x_{i} = (x_{i1}, x_{i2}, \cdots x_{iD})$. Note that we have $N$ such vectors. 


$$ X = 
\begin{bmatrix}
    ----    &  x_{1}^{\top} &  ----   \\
    \vdots    &  \vdots    &  \vdots    \\
    ----    &  x_{i}^{\top} &  ----      \\
     \vdots    &  \vdots    &  \vdots     \\
     ----    &  x_{N}^{\top} &  ----  
\end{bmatrix}_{N\times D}
$$

Before finding a direction that maximizes the variance of the projections, let's first understand how we will find the variance of projections of $x_i$ onto a given direction $v = (v_1, \cdots, v_{D})$. Recall that mathematically a direction is represented by a vector of unit lenght. So we assume that $\lVert v \rVert = 1$. 

Again if we recall the scalar projection of a vector $\vec{a}$ onto a unit vector $\vec{b}$ is given by the dot product. More explicitly: $ \text{proj}_{b}a = \dfrac{a.b}{\lVert b \rVert}$



([Image sourse](https://mathinsight.org/dot_product))

If we look at the projections of each row-vectors $x_i$ onto a given vector $v$, we will get $N$-numbers each given by the scalar projection formula. 


$$ \begin{align}
p_i &= v^{\top} \cdot x_{i} &  &\text{(projection of each row onto the vector)}\\
\overline{p} &= \frac{1}{N} \sum\limits_{i=1}^{N} p_{i}\\
             &= \frac{1}{N} \sum\limits_{i=1}^{N} v^{\top} \cdot x_{i} & &\text{(the mean of the projections)}\\
             &= v^{\top}\cdot\frac{1}{N} \sum\limits_{i=1}^{N} x_{i}               &     &\text{(recall that $ \vec{a}\cdot\vec{b}+\vec{a}\cdot\vec{c} = \vec{a}\cdot(\vec{b}+\vec{c}))$}
\end{align}
$$


Note that in the last equation we get the following vector $\frac{1}{N} \sum\limits_{i=1}^{N} x_{i}$ . This is summation over each row vector in $X$ and then dividing the corresponding vector by the number of rows. In other words, this is a vector consists of the means of the columns of $X$. We will denote this vector as $\overline{x}$. Then:

$$
\overline{p} = v^{\top} \cdot \overline{x}
$$

So the average of the projections of the rows $x_i$ onto an arbitrary vector $v$ is given by the dot product of this vector with the mean vector of $X$. Note that for the variance we need to subtract each projection from this and then sum their squares over all of the rows of $X$. Let's write this mathematically:

$$
\begin{align}
\sigma^{2} &= \frac{1}{N}\sum\limits_{i=1}^{N}  \left( \overline{p} - p_{i}\right)^{2} \\
       &= \frac{1}{N}\sum\limits_{i=1}^{N} \left( v^{\top}\cdot \overline{x} - v^{\top}\cdot x_{i}\right)^{2}\\
       &= \frac{1}{N}\sum\limits_{i=1}^{N} \left( v^{\top}\cdot\left( \overline{x} -  x_{i} \right) \right)^{2}
\end{align}
$$

Let's focus on the last equation again. Note that the dot product of two vectors is a number and it's square is good old second power in real numbers. However, we can write this as:

$$
\begin{align}
\left(a^{\top}\cdot b\right)^{2} &= \left(a^{\top}\cdot b\right)\left(a^{\top}\cdot b\right) \\
                                 &= \left(a^{\top}\cdot b\right)\left(b^{\top} \cdot a \right) && \text{with the trick $a^{\top}\cdot b = b^{\top} \cdot a$} \\
                                 &= a^{\top} \cdot \left( b\cdot b^{\top} \right) \cdot a \\
              \end{align}
$$

Note that the last equation is a little bit trickier. We used the fact that for vector the dot product and the matrix products are the same and the matrix product is associative (A.(B.C) = (A.B).C) ie. the order of multiplication doesn't matter. Note that this is not the case for the dot product. 

Therefore and finally we get a nice expression for the variance of projections:

$$
\begin{align}
\sigma^{2}&= \frac{1}{N} \sum\limits_{i=1}^{N} \left( v^{\top}\cdot\left( \overline{x} -  x_{i} \right) \right)^{2}\\
          &= \frac{1}{N}\sum\limits_{i=1}^{N} v^{\top} \left( \overline{x} -  x_{i} \right)\left( \overline{x} -  x_{i} \right)^{\top} v
\end{align}
$$

Now one question is begging for an answer: Why should we do all this abracadabra. The answer is the following. In the last equation, the middle term would give us a familiar matrix: $ \frac{1}{N}\left( \overline{x} -  x_{i} \right)\left( \overline{x} -  x_{i} \right)^{\top} = \Sigma$ where $\Sigma $ denotes the covariance matrix of $X$. After this long journey, let's summarize what we get: for a given data matrix $X$ and a unit vector $v$ the variance of the projection of $X$ onto $v$ is given by:

$$
\sigma_{v}^{2} = v^{\top} \Sigma v
$$

where $\Sigma = \frac{1}{N}\left( \overline{x} -  x_{i} \right)\left( \overline{x} -  x_{i} \right)^{\top} $ the covarince matrix of the data matrix $X$.

[More on Covariance Matrix](https://datascienceplus.com/understanding-the-covariance-matrix/)


### Solving maximization problem [↩](#content)

[](#solving_maximization_problem)

Note that the formula above depends on the vector $v$. Our goal in PCA is to find the unit vector $u$ so that $\sigma_{u}^{2}$ is maximum compared to all $D$-dimensional unit vectors . In more technical terms, we would like to find the maximum of a function (let's call it $f(v) = \sigma_{v}^{2}$) with the constraint $\lVert v \rVert =1$. Since this is a maximization problem with a constraint we should use the Lagrange multiplier method <sup id="Lagrange_multiplier_1">[1](#f1)</sup><sup id="Lagrange_multiplier_2">[2](#f2)</sup><sup id="Lagrange_multiplier_3">[3](#f3)</sup>.  According to this method, the maxima of the function $f(v) = \sigma_{v}^{2} = v^{\top} \Sigma v$ with constraint $\lVert v \rVert^{2} =1$ will be a critical point of the function $\mathcal{L}(v, \lambda) = f(v) - \lambda(\lVert v \rVert^{2}-1)$. Then we have to find the gradient $\nabla\mathcal{L} = (\frac{\partial\mathcal{L}}{\partial v}, \frac{\partial\mathcal{L}}{\partial \lambda})$. The partial derivative $\frac{\partial\mathcal{L}}{\partial \lambda}$ simply gives us the constraint condition. So only interesting part comes from $\frac{\partial\mathcal{L}}{\partial v}$. In our case we have the following:

$$
\begin{align}
\frac{\partial\mathcal{L}}{\partial v} = 0 &\iff& 2\Sigma v - 2\lambda v = 0 &&\text{(A short-hand notation for the partial derivatives)}\\
& \iff & \Sigma v = \lambda v &&\text{(Note that this means v is an eigenvector of $\Sigma$)}
\end{align}
$$

So note that any eigen-vector of $\Sigma$ is an candidate for the maxima of $\sigma^{2}$. Recall that for any such vector $u$ with the corresponding eigen-value $\lambda_{u}$ the value of $\sigma_{u}^{2} $ is:

$$
\begin{align}
\sigma_{u}^{2} &= u^{\top} \Sigma u \\
               &= \lambda_{u} \lVert u \rVert^{2}\\
               & = \lambda_{u}
\end{align}
$$
Therefore maximum of $\sigma^{2}$ is achived at the eigenvectors with highest eigenvalue.


### Conclusion and remarks [↩](#content)
[](#conclusion)


Notice that above computation showed that the first principal direction is an eigenvector of length 1 and whose eigenvector is the highest among other eigenvectors. For the second direction we will have the same maximization problem with an additional constraint that the second principal direction $u_2$ will be orthogonal to $u_1$. For more details of finding other directions you can look at: [Introduction to statistical learning - p377](http://www-bcf.usc.edu/~gareth/ISL/). 

__remark 1__ In this notebook we didn't discuss the other but equivalent formulation of PCA which is minimum error formulation. This formulation is kind of inituitive after the approach we disscussed. The idea is the principal directions should be also 'closest' to the datapoints. For more on this formulation you can check [Patter recognition and Machine Learning - p563](http://users.isr.ist.utl.pt/~wurmd/Livros/school/Bishop%20-%20Pattern%20Recognition%20And%20Machine%20Learning%20-%20Springer%20%202006.pdf).

__remark 2__ In application PCA's has some disadvantages. First of all, note that they are sensitive to the outliers. Also the principal directions depends on the scaling of the data. To address these problems usually it is advised that the data is standardized, that is mean zero and standard deviation of the columns are 1. For more on this, please check [Pattern recognition and Machine Learning - p568](http://users.isr.ist.utl.pt/~wurmd/Livros/school/Bishop%20-%20Pattern%20Recognition%20And%20Machine%20Learning%20-%20Springer%20%202006.pdf) and [Inroduction to statistical learning - p380](http://www-bcf.usc.edu/~gareth/ISL/). 



#### Footnotes

 <b id="f1">1</b> [Lagrange multiplier method - Khan Academy](https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/constrained-optimization/a/interpretation-of-lagrange-multipliers). [↩](#Lagrange_multiplier_1)
 
  <b id="f2">2</b> [Lagrange multiplier method - Wikipedia](https://en.wikipedia.org/wiki/Lagrange_multiplier). [↩](#Lagrange_multiplier_2)
  
   <b id="f2">3</b> [Lagrange multiplier method - A detailed blogpost](https://danstronger.wordpress.com/2015/08/08/lagrange-multipliers/). [↩](#Lagrange_multiplier_3)
  

# Ipython code


```python

import ipywidgets as widgets
from IPython.display import display, HTML

javascript_functions = {False: "hide()", True: "show()"}
button_descriptions  = {False: "Show code", True: "Hide code"}


def toggle_code(state):

    """
    Toggles the JavaScript show()/hide() function on the div.input element.
    """

    output_string = ""
    output_args   = (javascript_functions[state],)
    output        = output_string.format(*output_args)

    display(HTML(output))


def button_action(value):

    """
    Calls the toggle_code function and updates the button description.
    """

    state = value.new

    toggle_code(state)

    value.owner.description = button_descriptions[state]


state = False
toggle_code(state)

button = widgets.ToggleButton(state, description = button_descriptions[state])
button.observe(button_action, "value")

display(button)
```






    ToggleButton(value=False, description='Show code')










b26bbfd43c5a9a68166811e39856bf93364f4b4b
ipynb
Jupyter Notebook
concepts/PCA/a_mathematical_discussion_of_pca.ipynb
study-groups/math-study-group
c769d3d9a422eaa945d2f35183cc7eebca14790c
MIT
2019-03-18T18:42:07.000Z
2019-03-18T18:42:07.000Z
concepts/PCA/a_mathematical_discussion_of_pca.ipynb
study-groups/math-study-group
c769d3d9a422eaa945d2f35183cc7eebca14790c
MIT
2019-03-11T18:58:01.000Z
2019-03-13T16:18:54.000Z
concepts/PCA/a_mathematical_discussion_of_pca.ipynb
study-groups/math-study-group
c769d3d9a422eaa945d2f35183cc7eebca14790c
MIT
2019-03-11T16:23:13.000Z
2019-05-31T04:59:27.000Z
Qwen/Qwen-72B
1. YES
2. YES