---
title: Team_3_251
---
***score 15/15***

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."
The line $y=x$.
3. Find projections of the four points on $H$.
$(\frac{1+2}{2}, \frac{2+1}{2})=(1.5, 1.5),
(\frac{3+4}{2}, \frac{4+3}{2})=(3.5, 3.5)$

5. Find $p_1$, $p_2$, $p_3$, $p_4$.
$p_1=\frac{3}{2}\sqrt{2}, p_2=\frac{3}{2} \sqrt{2} , p_3= \frac{7}{2} \sqrt{2}, p_4=\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$
Projection of $v_1$ onto $x$ is $(x \cdot v_i)x$

$$\min_{x} F(x)=\sum_{i=1}^{n}\lvert\lvert v_i-(x\cdot v_i)x\lvert\lvert^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)(x\cdot v_i)+(x \cdot v_i)(x \cdot v_i)(x\cdot x)=$$

$$v_i \cdot v_i-2(x \cdot v_i)(x\cdot v_i)+(x \cdot v_i)(x \cdot v_i)=$$

$$v_i \cdot v_i-(x \cdot v_i)^2=$$

$$\max_{x} G(x)=\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)$

$$\max_{x} G(x)=\sum_{i=1}^{4} (x \cdot v_i)^2$$

$$=(1x_1+2x_2)^2+(2x_1+1x_2)^2+(3x_1+4x_2)^2+(4x_1+3x_2)^2$$

This 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)=x^T(M^TM)x$$

$$=(1x_1+2x_2)^2+(2x_1+1x_2)^2+(3x_1+4x_2)^2+(4x_1+3x_2)^2=x^T(M^TM)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)$.

Lagrange function is $$L(x,\lambda )=G(x)-\lambda (x^Tx-1)$$

Take a derivative with respect to $x$, and set it equal to zero.

$$L(x,\lambda )=G(x)-\lambda (x^TIx-1)=x^t(M^TM)x-\lambda (x^TIx-1)$$

$$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 of $M^TM$, and $x$ is an eigenvector.

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^TM= \begin{bmatrix}
30 & 28\\
28 & 30\\
\end{bmatrix}$$

$$det (M^TM-\lambda I)=(30-\lambda)(30-\lambda)-(28\cdot28)$$

$$=900-60\lambda + \lambda^2-784$$

$$=\lambda^2-60\lambda+116$$

$$=(\lambda-58)(\lambda-2)$$

$$\lambda_1=58, \lambda_2=2$$

Choose $\lambda_1=58$ because we're maximizing.

$$M^TM-58I=\begin{bmatrix}
-28 & 28\\
28 & -28\\
\end{bmatrix}$$

$$-28x_1=-28x_2$$

$$28x_1=28x_2$$

$$x_1=x_2$$

$${\bf x}=\begin{bmatrix}
1\\
1\\
\end{bmatrix}$$

Normalize ${\bf x}$ by multiplying ${\bf x}$ by $\frac{1}{\sqrt{2}}$ to get ${\bf x}=\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}}\\
\end{bmatrix}$

$$M \cdot {\bf x}= \begin{bmatrix}
1 & 2\\
2 & 1\\
3 & 4\\
4 & 3
\end{bmatrix} \cdot
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}}\\
\end{bmatrix} =\begin{bmatrix}
\frac{3}{2}\sqrt{2} \\
\frac{3}{2}\sqrt{2} \\
\frac{7}{2} \sqrt{2} \\
\frac{7}{2} \sqrt{2}
\end{bmatrix}=\begin{bmatrix}
p_1 \\
p_2 \\
p_3 \\
p_4
\end{bmatrix}$$

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.