---
title: Team_4_251
---

***Wonderful! 30/30***
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."
A line, y=x.
3. Find projections of the four points on $H$.
(1.5, 1.5) and (3.5, 3.5) found by using the Midpoint Formula.
5. Find $p_1$, $p_2$, $p_3$, $p_4$.
p1=p2=$\frac{3}{2} \sqrt{2}$
p3=p4=$\frac{7}{2} \sqrt{2}$

**Mathematize 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$
$$F(x_1, x_2)=\sum_{i=1}^{n}||v_i-(x\cdot{v_i})x||^2$$

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

$$\max_{x_1,x_2} G(x_1, x_2)$$
subject to the constraint $x_1^2+x_2^2=1$

$(v_i-(x\cdot{v_i})x)\cdot(v_i-(x\cdot{v_i})x)$
=$v_i\cdot{v_i}-2(x\cdot{v_i})^2+(x\cdot{v_i})^2$
=$v_i\cdot{v_i}-(x\cdot{v_i})^2$

We want to maximize the subtrahend, $x\cdot{v_i}$, in order to minimize the whole expression.

$$\max_{x_1,x_2} G(x_1, x_2)=\max\sum_{i=1}^{n}(x\cdot{v_i})^2$$

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)$

$G(x_1,x_2)$ is a quadratic form.

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}$$

$$G(x_1, x_2)=x^{T}\cdot{M^T}\cdot{M}\cdot{x}$$

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

$$x\cdot{x}=x^Tx=1$$

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

$L(x, \lambda)=G(x)-\lambda(x^Tx-I)$
$L'(x, \lambda)=2x^T(M^TM)-2\lambda(x^TI)=0$

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

$\lambda$ is an eigenvalue and $x$ is an unit eigenvector of $M^TM$.

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$.

M dot the eigenvector, <$1/\sqrt{2},
1/\sqrt{2}$>, that corresponds to $\lambda=58$, the largest eigenvalue:

$$ \begin{bmatrix}
1 & 2\\
2 & 1\\
3 & 4\\
4 & 3
\end{bmatrix}\cdot{\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}$$
p1=$\frac{3}{2} \sqrt{2}$
p2=$\frac{3}{2} \sqrt{2}$
p3=$\frac{7}{2} \sqrt{2}$
p4=$\frac{7}{2} \sqrt{2}$

9. (Extra Credit) Find a way (by rotation) to compute the points denoted by the red squares in data_toy.pdf. This does not affect any computations above, and is simply extra work to provide visual help.

We observed the four blue points can best be viewed as lying along the axis that is at a 45-degree angle. The matrix
$$ E=\begin{bmatrix}
1/\sqrt{2} & -1/\sqrt{2}\\
1/\sqrt{2} & 1/\sqrt{2}
\end{bmatrix}\ $$
can be viewed as a rotation 45 degrees counterclockwise.
Colomns of E, <$1/\sqrt{2},1/\sqrt{2}$> and <$-1/\sqrt{2}, 1/\sqrt{2}$>, can also be considered a basis for the rotated coordinate system, we call it base B. We would like to know the coordinates of the four points in B. The first components or x-coordinates of the four points(4 red squares) in B will be p1, p2, p3, p4. The way we find v1, v2, v3, v4 in B is using the inverse of matrix E that is the same with $E^T$ for orthonormal:
$$ \begin{bmatrix}
1/\sqrt{2} & 1/\sqrt{2}\\
-1/\sqrt{2} & 1/\sqrt{2}
\end{bmatrix}\cdot{\begin{bmatrix}
1\\
2
\end{bmatrix}}=\begin{bmatrix}
3/\sqrt{2}\\
1/\sqrt{2}
\end{bmatrix}$$
$$ \begin{bmatrix}
1/\sqrt{2} & 1/\sqrt{2}\\
-1/\sqrt{2} & 1/\sqrt{2}
\end{bmatrix}\cdot{\begin{bmatrix}
2\\
1
\end{bmatrix}}=\begin{bmatrix}
3/\sqrt{2}\\
-1/\sqrt{2}
\end{bmatrix}$$
$$ \begin{bmatrix}
1/\sqrt{2} & 1/\sqrt{2}\\
-1/\sqrt{2} & 1/\sqrt{2}
\end{bmatrix}\cdot{\begin{bmatrix}
3\\
4
\end{bmatrix}}=\begin{bmatrix}
7/\sqrt{2}\\
1/\sqrt{2}
\end{bmatrix}$$
$$ \begin{bmatrix}
1/\sqrt{2} & 1/\sqrt{2}\\
-1/\sqrt{2} & 1/\sqrt{2}
\end{bmatrix}\cdot{\begin{bmatrix}
4\\
3
\end{bmatrix}}=\begin{bmatrix}
7/\sqrt{2}\\
-1/\sqrt{2}
\end{bmatrix}$$

so we got:
p1=$\frac{3}{2} \sqrt{2}$
p2=$\frac{3}{2} \sqrt{2}$
p3=$\frac{7}{2} \sqrt{2}$
p4=$\frac{7}{2} \sqrt{2}$

Team 4 Problem #2

$x_1=(4.1, -5.7, 1.4, -13.4, -7.6, -8.2, 5.2, -0.1, -11.6, -0.1)$
$x_2=(-0.7, -0.5, 0.9, 0.1, 0.4, 0.8, 0.2, 0.6, 0.7, 1.2)$

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...v_{10}$ 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$
$$F(x_1, x_2)=\sum_{i=1}^{10}||v_i-(x\cdot{v_i})x||^2$$

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

$$\max_{x_1,x_2} G(x_1, x_2)$$
subject to the constraint $x_1^2+x_2^2=1$

$(v_i-(x\cdot{v_i})x)\cdot(v_i-(x\cdot{v_i})x)$
=$v_i\cdot{v_i}-2(x\cdot{v_i})^2+(x\cdot{v_i})^2$
=$v_i\cdot{v_i}-(x\cdot{v_i})^2$

We want to maximize the subtrahend, $x\cdot{v_i}$, in order to minimize the whole expression.

$$\max_{x_1,x_2} G(x_1, x_2)=\max\sum_{i=1}^{10}(x\cdot{v_i})^2$$

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)$

$G(x_1,x_2)$ is a quadratic form.

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...10$ as its rows.

$$ 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}$$

$$G(x_1, x_2)=x^{T}\cdot{M^T}\cdot{M}\cdot{x}$$
5. Write the constraint $x_1^2+x_2^2=1$ as a product of two vectors.

$$x\cdot{x}=x^Tx=1$$
6. Use Lagrange multiplyers to solve the maximization problem. Google how to differentiate $G(x_1, x_2)$.

$L(x, \lambda)=G(x)-\lambda(x^Tx-I)$
$L'(x, \lambda)=2x^T(M^TM)-2\lambda(x^TI)=0$

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

$\lambda$ is an eigenvalue and $x$ is an unit eigenvector of $M^TM$.

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

$$M^T\cdot{M}=\begin{bmatrix}
517.44 & -16.96\\
-16.96 & 4.69
\end{bmatrix}$$

$\lambda=4.130$ and $518.0004$

Since we are maximizing, we will use $518.0004$ and got the eigenvector \begin{bmatrix}
-30.266\\
1
\end{bmatrix}
with the constraint $x_1^2+x_2^2=1$, x is $<-0.999,0.033>$ which we rounded to $<-1, 0>$, we choose to use $<1,0>$,with its first component positive, instead. Both are eigenvectors satisfying $x_1^2+x_2^2=1$ and correspond to $\lambda=518.0004$, the largest eigenvalue.

$M\cdot{<1, 0>}$

$$ \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}\cdot{\begin{bmatrix}
1\\
0
\end{bmatrix}}=\begin{bmatrix}
4.1 \\
-5.7 \\
1.4 \\
-13.4 \\
-7.6 \\
-8.2 \\
5.2 \\
-0.1 \\
-11.6 \\
-0.1
\end{bmatrix}$$

that is
$p1=4.1$ \
$p2=-5.7$ \
$p3=1.4$ \
$p4=-13.4$ \
$p5=-7.6$\
$p6=-8.2$ \
$p7=5.2$ \
$p8=-0.1$ \
$p9=-11.6$ \
$p10=-0.1$