# Orthogonal Projection

### Big Idea
The orthogonal projection of a vector $\mathbf{x} \in \mathbb{R}^n$ onto a subspace $U \subset \mathbb{R}^n$, denoted $\mathrm{proj}_U (\mathbf{x})$, is the point in U that is nearest to $\mathbf{x}$. The difference between x and its projection, $\mathbf{x} - \mathrm{proj}_U (\mathbf{x})$, lies entirely in the orthogonal complement, $U^\perp$.

## Projection onto a Vector
:::info
**Definition**
The **projection** of a vector $\mathbf{x}$ onto a single nonzero vector $\mathbf{u}$ is given by:
$$
\mathrm{proj}_{\mathbf{u}}(\mathbf{x}) = \frac{\langle \mathbf{x} , \mathbf{u} \rangle}{\langle \mathbf{u} , \mathbf{u} \rangle} \mathbf{u}
$$
:::

### Key Properties
:::danger
**Proposition**
Projection onto a vector $\mathbf{u}$ can be achieved through matrix multiplication using the projection matrix, $P$:
$$
\mathrm{proj}_{\mathbf{u}}(\mathbf{x}) = P \mathbf{x}
\ \ \text{where} \ \
P = \frac{1}{\| \mathbf{u} \|^2} \mathbf{u} \mathbf{u}^T
$$

This projection matrix $P$ satisfies the following properties:
* $P^2 = P$, $P^T = P$.
* $\mathcal{R}(P) = \text{Span}\{\mathbf{u}\}$ and $\mathrm{rank}(P) = 1$.
* $\mathcal{N}(P) = \text{Span}\{\mathbf{u}\}^\perp$.
:::

:::warning
**Example (Projection Matrix onto a Vector)**
Find the orthogonal projection matrix $P$ onto the vector
$$
\mathbf{u} = \begin{bmatrix}1\\2\\0\end{bmatrix}
$$

1. Construct the projection matrix $P$:
$$
P = \frac{1}{\|\mathbf{u}\|^2} \mathbf{u}\mathbf{u}^T
= \frac{1}{5}
\begin{bmatrix}
1 & 2 & 0 \\
2 & 4 & 0 \\
0 & 0 & 0
\end{bmatrix}
$$

2. Compute the projection:
$$
\text{Proj}_{\mathbf{u}}\!\left(\begin{bmatrix}3\\4\\5\end{bmatrix}\right)
= P \begin{bmatrix}3\\4\\5\end{bmatrix}
= \begin{bmatrix}\tfrac{11}{5}\\ \tfrac{22}{5}\\ 0\end{bmatrix}.
$$
:::

## Orthogonal Bases
:::info
**Definition**
An **orthogonal basis** for a subspace $U$ is a basis where all vectors in the set $\{ \mathbf{w}_1,\dots,\mathbf{w}_m \}$ are mutually orthogonal ($\langle \mathbf{w}_i , \mathbf{w}_j \rangle = 0$ for $i \not= j$). If all vectors are also *unit vectors* ($\|\mathbf{w}_j\| = 1$), it is an **orthonormal basis**.
:::

:::warning
**Examples:** Consider $\mathbb{R}^2$
* $\{ \begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}0\\1\end{bmatrix} \}$ is an orthonormal basis.
* $\left\{\tfrac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}, \tfrac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}\right\}$ is an orthonormal basis.
* $\{ \begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}1\\-1\end{bmatrix} \}$ is a basis but **not** an orthonormal basis.
:::

:::danger
**Theorem (Gram–Schmidt Orthonormalization Algorithm)**
Let $\{ \mathbf{u}_1, \dots ,\mathbf{u}_m \}$ be a basis of a subspace $U \subseteq \mathbb{R}^n$. The *Gram-Schmidt orthogonalization algorithm* constructs an orthogonal basis of $U$:
\begin{align}
\mathbf{v}_1 &= \mathbf{u}_1 \\
\mathbf{v}_2 &= \mathbf{u}_2 - \mathrm{proj}_{\mathbf{v}_1}(\mathbf{u}_2) \\
\mathbf{v}_3 &= \mathbf{u}_3 - \mathrm{proj}_{\mathbf{v}_1}(\mathbf{u}_3) - \mathrm{proj}_{\mathbf{v}_2}(\mathbf{u}_3) \\
& \ \ \vdots \\
\mathbf{v}_m &= \mathbf{u}_m - \mathrm{proj}_{\mathbf{v}_1}(\mathbf{u}_m) - \mathrm{proj}_{\mathbf{v}_2}(\mathbf{u}_m) - \cdots - \mathrm{proj}_{\mathbf{v}_{m-1}}(\mathbf{u}_m)
\end{align}

Then $\{ \mathbf{v}_1 , \dots , \mathbf{v}_m \}$ is an orthogonal basis of $U$. Furthermore, let
$$
\mathbf{w}_k = \frac{\mathbf{v}_k}{\| \mathbf{v}_k \|} \ \ , \ k=1,\dots,m
$$

Then $\{ \mathbf{w}_1 , \dots , \mathbf{w}_m \}$ is an orthonormal basis of $U$.
:::

:::warning
**Example** Find an orthonormal basis for
$$
U = \text{Span}\left\{
\mathbf{u}_1 =
\begin{bmatrix}1\\0\\1\\0\end{bmatrix},\,
\mathbf{u}_2 =
\begin{bmatrix}1\\1\\1\\0\end{bmatrix},\,
\mathbf{u}_3 =
\begin{bmatrix}1\\1\\0\\0\end{bmatrix}
\right\}
$$

1. Apply the Gram–Schmidt Orthonormalization Algorithm:
* $\mathbf{v}_1 = \mathbf{u}_1 =
\begin{bmatrix}1\\0\\1\\0\end{bmatrix}$
* $\mathbf{v}_2 = \mathbf{u}_2 - \text{Proj}_{\mathbf{v}_1}(\mathbf{u}_2)
= \mathbf{u}_2 - \dfrac{\mathbf{v}_1\cdot \mathbf{u}_2}{\|\mathbf{v}_1\|^2}\,\mathbf{v}_1
= \begin{bmatrix}0\\1\\0\\0\end{bmatrix}$
* $\mathbf{v}_3 = \mathbf{u}_3 -\text{Proj}_{\mathbf{v}_1}(\mathbf{u}_3) -\text{Proj}_{\mathbf{v}_2}(\mathbf{u}_3) = \begin{bmatrix}1\\1\\0\\0\end{bmatrix}- \dfrac{1}{2}\begin{bmatrix}1\\0\\1\\0\end{bmatrix} - \begin{bmatrix}0\\1\\0\\0\end{bmatrix}= \dfrac{1}{2}\begin{bmatrix}1\\0\\-1\\0\end{bmatrix}$
Thus $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$is an orthogonal basis for $U$.
2. Normalization:
$$
\left\{
\mathbf{w}_1 = \dfrac{1}{\sqrt{2}}\begin{bmatrix}1\\0\\1\\0\end{bmatrix},\,
\mathbf{w}_2 = \begin{bmatrix}0\\1\\0\\0\end{bmatrix},\,
\mathbf{w}_3 = \dfrac{1}{\sqrt{2}}\begin{bmatrix}1\\0\\-1\\0\end{bmatrix}
\right\}
$$
is an orthonormal basis for $U$.
:::

## Projection onto a Subpsace
:::info
**Definition**
If $U \subseteq \mathbb{R}^n$ has an orthogonal basis $\{ \mathbf{u}_1, \dots, \mathbf{u}_m \}$, the projection of $\mathbf{x}$ onto $U$ is the sum of the projections of $\mathbf{x}$ onto each vector in the basis:
$$
\mathrm{proj}_U(\mathbf{x}) = \frac{\langle \mathbf{x} , \mathbf{u}_1 \rangle}{ \langle \mathbf{u}_1 , \mathbf{u}_1 \rangle } \mathbf{u}_1 + \cdots + \frac{\langle \mathbf{x} , \mathbf{u}_m \rangle}{ \langle \mathbf{u}_m , \mathbf{u}_m \rangle } \mathbf{u}_m
$$
:::

### Key Properties
:::danger
**Proposition**
1. **Orthogonal Decomposition (Projection Theorem):** The residual vector, $\mathbf{x} - \mathrm{proj}_U(\mathbf{x})$, is always orthogonal to the subspace $U$; that is, it lies in the orthogonal complement, $U^\perp$.
2. **Best Approximation Property:** The projection $\mathrm{proj}_{\mathbf{U}}(\mathbf{x})$ is the unique vector in U that minimizes the distance to $\mathbf{x}$:
$$
\|\mathbf{x}- \text{Proj}_U(\mathbf{x})\| \le \|\mathbf{x}-\mathbf{y}\| \quad \forall \mathbf{y} \in U
$$
3. **Projection Matrix for Subspace:** The projection matrix $P$ onto $U$ is the sum of the individual rank-one projection matrices corresponding to the orthogonal basis vectors: $$P = \sum_{k=1}^m \frac{1}{\| \mathbf{u}_k \|^2} \mathbf{u}_k \mathbf{u}_k^T$$ This matrix $P$ is also idempotent ($P^2=P$) and symmetric ($P^T=P$). Its range is $U$ ($\mathcal{R}(P) = U$), and its nullspace is $U^\perp$ ($\mathcal{N}(P) = U^\perp$).
4. **Complementary Projection:** The matrix $P^\perp :=I−P$ is the orthogonal projection matrix onto the orthogonal complement $U^\perp$.
:::

:::warning
**Example (Projection onto a 2D Subspace in $\mathbb{R}^2$**
Let $U$ Let U be the subspace spanned by the vectors
$$
\mathbf{u}_1 = \left[ \begin{array}{r} 1 \\ 0 \\ -1 \end{array} \right]
\hspace{5mm}
\mathbf{u}_2 = \left[ \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right]
$$

1. The Projection Matrix $P$ is:
* Compute $\langle \mathbf{u}_1 , \mathbf{u}_2 \rangle = 0$ therefore the vectors are orthogonal.
* Compute
\begin{align*}
P
&= \frac{1}{\| \mathbf{u}_1 \|^2} \mathbf{u}_1 \mathbf{u}_1^T + \frac{1}{\| \mathbf{u}_2 \|^2} \mathbf{u}_2 \mathbf{u}_2^T
\end{align*}

2. Orthogonal Projection Matrix $P^\perp$ onto $U^{\perp}$
*
$$
\begin{align*}
P_{\perp} = I - P &=
\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] -
\frac{1}{6} \left[ \begin{array}{rrr} 5 & \phantom{+}2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{array} \right] \\
&= \frac{1}{6} \left[ \begin{array}{rrr} 1 & -2 & 1 \\ -2 & 4 & -2 \\ 1 & -2 & 1 \end{array} \right]
\end{align*}
$$
* Alternative Method: Note that $$\mathbf{u}_3 = \left[ \begin{array}{r} 1 \\ -2 \\ 1 \end{array} \right]$$ is orthogonal to both $\mathbf{u}_1$ and $\mathbf{u}_2$ and is a basis of the orthogonal complement $U^{\perp}$. Therefore we could also compute
$$
\begin{align*}
P_{\perp} = \frac{1}{\| \mathbf{u}_3 \|^2} \mathbf{u}_3 \mathbf{u}_3^T
&= \frac{1}{6} \left[ \begin{array}{r} 1 \\ -2 \\ 1 \end{array} \right]
\left[ \begin{array}{ccc} 1 & -2 & 1 \end{array} \right] \\
&= \frac{1}{6} \left[ \begin{array}{rrr} 1 & -2 & 1 \\ -2 & 4 & -2 \\ 1 & -2 & 1 \end{array} \right]
\end{align*}
$$
:::

:::success
**Exercise**

1.
* (a) Let $U \subset \mathbb{R}^n$ be a subspace. If $P_1$ is the orthogonal projector onto $U$ and $P_2$ is the orthogonal projector onto the orthogonal complement $U^\perp$, then $$I = P_1 + P_2.$$
* (b) If $P_1$ is the orthogonal projector onto $U$ and $P_2$ is the orthogonal projector onto $U^\perp$, then
$$P_1P_2 = 0.$$
2. Let $U \subset \mathbb{R}^3$ be the subspace spanned by $$\mathbf{u}_1 = \begin{bmatrix}1\\1\\1\end{bmatrix}, \quad
\mathbf{u}_2 = \begin{bmatrix}-1\\1\\1\end{bmatrix}$$ Find the vector $\mathbf{x} \in U$ which is closest to $$\mathbf{b} = \begin{bmatrix}1\\2\\1\end{bmatrix}$$
:::