---
title: Team 3
---

***wonderful work! 30/30***

Tim Adade, Matt Oakes, Dawn Myers
---
The four points are $v_1=(1,2), v_2=(2,1), v_3=(3,4), v_4=(4,3)$. They are in 2D. We want to reduce dimensionality to one. The result should be four points in $\mathbb {R}^1$: $p_1$, $p_2$, $p_3$, $p_4$.

**Predict the answer**
1. By visual inspection find a hyperplane $H$ that the four points are "closest to."

$y = x$

2. Find projections of the four points on $H$.

$(1.5, 1.5), (3.5, 3.5)$

3. Find $p_1$, $p_2$, $p_3$, $p_4$.

$p_1 = \sqrt{(1.5^2 + 1.5^2)} = \sqrt{(4.5)} =3/\sqrt{2}$
$p_2 = \sqrt{(1.5^2 + 1.5^2)} = \sqrt{(4.5)}=3/\sqrt{2}$
$p_3 = \sqrt{(3.5^2 + 3.5^2)} = \sqrt{(24.5)}=7/\sqrt{2}$
$p_4 = \sqrt{(3.5^2 + 3.5^2)} = \sqrt{(24.5)}=7/\sqrt{2}$

**Mathemitize your approach**

1. $H$ is uniquely defined by a vector ${\bf x}:=(x_1,x_2)$ that we need to find. Let us assume that ${\bf x}$ has unit length. Set up a minimization problem that uses $v_1,v_2,v_3,v_4$ as knowns and ${\bf x}$ as an unknown. This should reflect the fact that $H$ is the hyperplane that the four points are "closest to." You should be able to recognize the mathematical objects that we have studied in this course. Name them. You will end up with
$$\min_{x_1,x_2} F(x_1, x_2)$$
subject to the constraint $x_1^2+x_2^2=1$

$$ \min ||(\hat{v_{i}}- proj_{\hat{x}}(\hat{v_i})||^2 $$

$$ \min \sum_{1}^4 (v_{i} - (v_{i}\cdot x)x)^2$$

$$= \min \sum_{1}^4(v_{i} \cdot v_{i}-2 (v_{i} \cdot x) (v_{i} \cdot x)+ (v_{i} \cdot x)^2x\cdot x)) $$

$$=\min \sum_{1}^4(v_{i} \cdot v_{i}-2 (v_{i} \cdot x) (v_{i} \cdot x)+ (v_{i} \cdot x)^2))$$

$$= \min \sum_{1}^4 (v_{i}^2 - (v_{i}\cdot x)^2)$$

2. Expand $F(x_1, x_2)$ and rewrite your minimization problem as a maximization one

Let $(v_{i} \cdot x)x = v_{i} - y$. Then maximize$\sum_{1}^4 ||proj_{x}v_{i} ||^2$

$$\max_{x_1,x_2} G(x_1, x_2) = \max \sum_{1}^4 (v_{i} \cdot x)^2$$
subject to the constraint $x_1^2+x_2^2=1$

3. Recognize $G(x_1, x_2)$ as an object that we have studied in this course. You might want to explicitly write out $G(x_1, x_2)$
$$ \max \sum_{1}^4(v_{i} \cdot x)^2 = x^TAx,$$where $A$ is $M^TM$

4. Write $G(x_1, x_2)$ in a vector-matrix form using ${\bf x}$ and the matrix $M$ that has $v_i$, $i=1,2,3,4$ as its rows.

$$M = \begin{bmatrix} 1 &2 \\2 &1 \\ 3&4 \\ 4&3\\ \end{bmatrix} $$
$$M^T = \begin{bmatrix} 1 &2 &3&4\\2 &1&4&3 \\ \end{bmatrix} $$
$$M^TM = A = \begin{bmatrix} 30 & 28 \\ 28 & 30\\ \end{bmatrix} $$

5. Write the constraint $x_1^2+x_2^2=1$ as a product of two vectors.

$$\vec{x}^T\vec{x}- 1 = 0$$ where $\vec{x} = \begin{bmatrix}x_{1} \\ x_{2} \end{bmatrix}$

6. Use Lagrange multiplyers to solve the maximization problem. Google how to differentiate $G(x_1, x_2)$.

Take the derivative
$$ x^TAx - \lambda(x^Tx - 1) $$
$$ 2x^TA - 2\lambda x^T = 0 \rightarrow 2x^T = 2\lambda x^T \rightarrow Ax = \lambda x $$

7. Recognize your solutions as a mathematical object heavily studied in this course.

Our solution is an eigenvector of A
Let $E$ be the (orthornormal) eigenvectors of $A$.
$\lambda_{1}$ = 58, $\lambda_{1}$ = 2

$$E = \begin{bmatrix} 1/\sqrt{2} & -1/\sqrt{2} \\1/\sqrt{2} & 1/\sqrt{2}\\ \end{bmatrix} $$

8. Your solution will produce the desired ${\bf x}$. Find a simple matrix multiplication way of obtaining $p_1$, $p_2$, $p_3$, $p_4$.

We are looking for the projected values of $\textbf{x}$ that lie along the new $x-axis$, that corresponds to the eigenvectors associated with the largest eigenvalue.
Let $E_{1}$ be the matrix with the eigenvectors associated with the largest eigenvector to reduce the dimension to 1.

$$ME_{1} = \begin{bmatrix} 1 &2 \\2 &1 \\ 3&4 \\ 4&3\\ \end{bmatrix} \begin{bmatrix} 1/\sqrt{2} \\1/\sqrt{2}\\ \end{bmatrix} = \begin{bmatrix} 3/\sqrt{2} \\3/\sqrt{2} \\ 7/\sqrt{2} \\ 7/\sqrt{2}\\ \end{bmatrix}$$

Now we will perform the same calculations for the following dataset:

$\vec{x_{1}} = [4.1, -5.7, 1.4, -13.4, -7.6, -8.2, 5.2, -0.1, -11.6, -0.1]$

$\vec{x_{2}} = [-0.7, -0.5, 0.9, 0.1, 0.4, 0.8, 0.2, 0.6, 0.7, 1.2]$

First, write $\vec{x_{1}}$ and $\vec{x_{2}}$ in vector-matrix form given by $M$.

$$M = \begin{bmatrix} 4.1 && -0.7 \\ -5.7 && -0.5 \\ 1.4 && 0.9 \\ -13.4 && 0.1 \\ -7.6 && 0.4 \\ -8.2 && 0.8\\ 5.2 && 0.2\\ -0.1 && 0.6 \\ -11.6 && 0.7 \\ -0.1 && 1.2 \end{bmatrix} $$

Form matrix $A$ given by $A = M^{T}M$

$$A = \begin{bmatrix} 517.44 && -16.96 \\ -16.96 && 4.69 \end{bmatrix}$$

Compute the eigenvalues and normalized eigenvectors for matrix $A$

$$\lambda_{1} = 518.00036585$$
$$e_{1} = \begin{bmatrix} 0.99945461 \\ -.03302242 \end{bmatrix}$$
$$\lambda_{2} = 4.12963415$$
$$e_{2} = \begin{bmatrix} .03302242 \\ .99945461 \end{bmatrix}$$

Mulitply $M$ by the matrix of eigenvectors $E=\begin{bmatrix} e_{1} && e_{2} \end{bmatrix}$ to rotate the original data.

$$ME = \begin{bmatrix} 4.1 && -0.7 \\ -5.7 && -0.5 \\ 1.4 && 0.9 \\ -13.4 && 0.1 \\ -7.6 && 0.4 \\ -8.2 && 0.8\\ 5.2 && 0.2\\ -0.1 && 0.6 \\ -11.6 && 0.7 \\ -0.1 && 1.2 \end{bmatrix} \begin{bmatrix} 0.99945461 && .03302242 \\ -.03302242 && .99945461 \end{bmatrix}$$

$$ME = \begin{bmatrix} 4.1208796 && -0.56422631 \\
-5.68038007 && -0.6879551 \\
1.36951628 && 0.94574054 \\
-13.39599403 && -0.34255496 \\
-7.60906401 && 0.14881146 \\
-8.22194575 && 0.52877985 \\
5.19055949 && 0.3716075 \\
-0.11975891 && 0.59637052 \\
-11.61678918 && 0.31655816 \\
-0.13957236 && 1.19604329 \end{bmatrix}$$

Multiply matrix $M$ by the eigenvector corresponding to the largest eigenvalue to obtain the projection on the $x_{1}$-axis

$$\begin{bmatrix} 4.1 && -0.7 \\ -5.7 && -0.5 \\ 1.4 && 0.9 \\ -13.4 && 0.1 \\ -7.6 && 0.4 \\ -8.2 && 0.8\\ 5.2 && 0.2\\ -0.1 && 0.6 \\ -11.6 && 0.7 \\ -0.1 && 1.2 \end{bmatrix}\begin{bmatrix} 0.99945461 \\ -.03302242 \end{bmatrix} = \begin{bmatrix} 4.1208796 \\ -5.68038007 \\ 1.36951628 \\ -13.39599403 \\ -7.60906401 \\
-8.22194575 \\ 5.19055949 \\ -0.11975891 \\ -11.61678918 \\ -0.13957236] \end{bmatrix}$$

Finally, plot all the data and put the projections into a table.


Here is python code to generate the plots based on the provided datasets.

import numpy as np
import matplotlib.pyplot as plt

#Create X and y vectors from data
#dataset 1
xs = np.array([1,2,3,4]).reshape(4,1)
ys = np.array([2,1,4,3]).reshape(4,1)
#dataset 2
#xs=np.array([4.1, -5.7, 1.4 ,-13.4 ,-7.6, -8.2, 5.2, -0.1, -11.6, -0.1])
#ys=np.array([-0.7, -0.5, 0.9, 0.1, 0.4, 0.8, 0.2,0.6, 0.7, 1.2])
xs = np.reshape(xs, (len(xs), 1))
ys = np.reshape(ys, (len(ys), 1))

#Create matrix M where columns correspond to x and y vectors 
M = np.concatenate((xs,ys), axis=1)

#A = M.T /cdot M
A = M.T.dot(M)

#Obtain eigenvalues and eigenvectors of A
eig_vals, eig_vecs = np.linalg.eig(A)

#The eigenvector matrix corresponds to a rotation matrix that we apply to the data
#columns 0 and 1 will be the rotated xs and ys
ME = M.dot(eig_vecs)
xs_r = ME[:,0]
ys_r = ME[:,1]

#Multiply the matrix M by the largest eigenvector (corresponding to the largest eigenvalue)
#to obtain location on the x-axis. 
x_projs = M.dot(eig_vecs[:,0])

#Plotting
#1. Plot the original data
#2. Plot the rotated data
#3. Plot the projections on the x-axis
#4. Table of projection values
fig, (ax1, ax2) = plt.subplots(2,1, figsize=(10,10))
ax1.scatter(xs, ys, c='blue')
ax1.scatter(x_projs, np.zeros(len(x_projs)), marker='x')
ax1.scatter(xs_r,ys_r, c='red')
ax1.legend(['Original Data', 'Rotated Data', 'Datapoints in $R^1$'])
ax1.grid()
ax2.table(cellText=[[i] for i in x_projs ], rowLabels = ['p%s' % i for i in range(1, len(x_projs) +1)], loc='center')
ax2.axis("off")
plt.show()

Dataset 1 plot