Orthogonal projection

Section 4.2 Orthogonal projection

Subsection Orthogonal complements and projections

Definition 4.2.1. The orthogonal complement of a subspace.

If \(U\) is a subspace of \(\R^n\text{,}\) the orthogonal complement of \(U\) is the subset of \(\R^n\) given by

\begin{equation*} U^\perp = \{\mathbf{x} \text{ in } \R^n \mid \mathbf{x} \cdot \mathbf{y} = 0 \text{ for all } \mathbf{y} \text{ in } U\} \end{equation*}

🔗

Theorem 4.2.2.

The following properties of the orthogonal complement hold:

For any subspace \(U\) of \(\R^n\text{,}\) \(U^\perp\) is a subspace of \(\R^n\)

🔗
\(\{0\}^\perp = \R^n\) and \((\R^n)^\perp = \{0\}\)

🔗
If \(U = \spans \{\mathbf{x}_1,\ldots,\mathbf{x}_k\}\text{,}\) then
\begin{equation*} U^\perp = \{\mathbf{x} \text{ in } \R^n \mid \mathbf{x} \cdot \mathbf{x}_i = 0 \text{ for } i=1,2,\ldots,k\} \end{equation*}

🔗

🔗

Activity 4.2.1.

Find \(U^\perp\) if \(U = \spans \{(1,1,0), (0,1,1)\}\) in \(\R^3\text{.}\)

🔗

Solution.

The third property of Theorem 4.2.2 implies that a vector \(\mathbf{w} = (x,y,z)\) lies in \(U^\perp\) if and only if it is orthogonal to both \((1,1,0)\) and \((0,1,1)\text{.}\) The set \(U^\perp\) is then precisely the set of \(\mathbf{w}\) satisfying the system of linear equations \(x + y = 0\) and \(y + z = 0\text{.}\) This system has a single basic solution \((1,-1,1)\text{,}\) and so any vector in \(U^\perp\) is a multiple of this vector, i.e.,

\begin{equation*} U^\perp = \spans \left\{ \begin{bmatrix}1\\-1\\1\end{bmatrix} \right\} = \left\{ \begin{bmatrix}y\\-y\\y\end{bmatrix}: y \in \R \right\} \text{.} \end{equation*}

🔗

Lemma 4.2.3. Expanding an orthogonal set.

Let \(\{\mathbf{f}_1, \mathbf{f}_2, \ldots, \mathbf{f}_m\}\) be an orthogonal set in \(\R^n\text{.}\) Given \(\mathbf{x}\) in \(\R^n\text{,}\) write

\begin{equation*} \mathbf{f}_{m+1} = \mathbf{x} - \frac{\mathbf{x}\cdot\mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 - \frac{\mathbf{x}\cdot\mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2 - \cdots - \frac{\mathbf{x}\cdot\mathbf{f}_m}{\|\mathbf{f}_m\|^2}\mathbf{f}_m \end{equation*}

Then:

\(\mathbf{f}_{m+1} \cdot \mathbf{f}_k = 0\) for \(k = 1,2,\ldots,m\)

🔗
If \(\mathbf{x} \not \in \spans \{\mathbf{f}_1,\ldots,\mathbf{f}_m\}\text{,}\) then \(\mathbf{f}_{m+1} \neq \mathbf{0}\) and \(\{\mathbf{f}_1,\ldots,\mathbf{f}_m,\mathbf{f}_{m+1}\}\) is an orthogonal set.

🔗

🔗

Why is this true?.

For convenience, let \(t_i = \frac{\mathbf{x} \cdot \mathbf{f}_i}{\|\mathbf{f}_i\|^2}\) for each \(i\text{.}\) Given \(1 \leq k \leq m\text{,}\) we calculate that

\begin{align*} \mathbf{f}_{m+1} \cdot \mathbf{f}_k \amp = (\mathbf{x} - t_1\mathbf{f}_1 - t_2\mathbf{f}_2 - \cdots - t_m\mathbf{f}_m) \cdot \mathbf{f}_k\\ \amp = \mathbf{x} \cdot \mathbf{f}_k - t_1(\mathbf{f}_1 \cdot \mathbf{f}_k) - \cdots - t_k(\mathbf{f}_k \cdot \mathbf{f}_k) - \cdots - t_m(\mathbf{f}_m \cdot \mathbf{f}_k) \end{align*}

Since \(\{\mathbf{f}_1, \mathbf{f}_2, \ldots, \mathbf{f}_m\}\) is an orthogonal set, \(\mathbf{f}_i \cdot \mathbf{f}_k = 0\) for all \(i \neq k\text{.}\) So

\begin{align*} \mathbf{f}_{m+1} \cdot \mathbf{f}_k \amp = \mathbf{x} \cdot \mathbf{f}_k - t_k(\mathbf{f}_k \cdot \mathbf{f}_k)\\ \amp = \mathbf{x} \cdot \mathbf{f}_k - \frac{\mathbf{x} \cdot \mathbf{f}_k}{\|\mathbf{f}_k\|^2} \cdot \|\mathbf{f}_k\|^2\\ \amp = \mathbf{x} \cdot \mathbf{f}_k - \mathbf{x} \cdot \mathbf{f}_k = 0 \end{align*}

This proves the first property of the lemma. To prove the second, we note that if \(\mathbf{f}_{m+1}\) was zero, then \(\mathbf{x}\) would be in the span of the vectors \(\{\mathbf{f}_1,\ldots,\mathbf{f}_m\}\text{.}\) So if \(\mathbf{x}\) is not in the span, then \(\mathbf{f}_{m+1}\) can not be equal to zero. And we have proved \(\mathbf{f}_{m+1}\) is orthogonal to the vectors \(\mathbf{f}_1, \dots, \mathbf{f}_m\text{,}\) so that \(\{ \mathbf{f}_1, \dots, \mathbf{f}_{m+1} \}\) is an orthogonal set.

🔗

Activity 4.2.2.

Use Lemma 4.2.3 to extend the orthogonal set \(\{ \mathbf{f}_1, \mathbf{f}_2 \}\) in \(\R^3\) to an orthogonal basis \(\{ \mathbf{f}_1, \mathbf{f}_2, \mathbf{f}_3 \}\text{,}\) where

\begin{equation*} \mathbf{f}_1 = \begin{bmatrix}1\\1\\0\end{bmatrix} \quad\text{and}\quad \mathbf{f}_2 = \begin{bmatrix}1\\-1\\0\end{bmatrix}\text{,} \end{equation*}

using the vector \(\mathbf{x} = (1,1,2)\) as in that lemma.

🔗

Solution.

We calculate that

\begin{align*} \mathbf{x} \cdot \mathbf{f}_1 \amp = (1,1,2) \cdot (1,1,0) = 1 + 1 + 0 = 2\\ \|\mathbf{f}_1\|^2 \amp = 1^2 + 1^2 + 0^2 = 2\\ \mathbf{x} \cdot \mathbf{f}_2 \amp = (1,1,2) \cdot (1,-1,0) = 1 - 1 + 0 = 0\\ \|\mathbf{f}_2\|^2 \amp = 1^2 + (-1)^2 + 0^2 = 2 \end{align*}

Using Lemma 4.2.3, we define

\begin{align*} \mathbf{f}_3 \amp = \mathbf{x} - \frac{\mathbf{x} \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 - \frac{\mathbf{x} \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2\\ \amp = \begin{bmatrix}1\\1\\2\end{bmatrix} - \frac{2}{2}\begin{bmatrix}1\\1\\0\end{bmatrix} - \frac{0}{2}\begin{bmatrix}1\\-1\\0\end{bmatrix} = \begin{bmatrix}0\\0\\2\end{bmatrix}\text{.} \end{align*}

🔗

Definition 4.2.4. The orthogonal projection onto a subspace.

Let \(U\) be a subspace of \(\R^n\text{.}\) Then the orthogonal projection of the vector \(\mathbf{x} \in \R^n\) onto \(U\) is the vector \(\mathbf{y}=\proj_U(\mathbf{x}) \in U\) which is closest to \(\mathbf{x}\text{,}\) in the sense that for any \(\mathbf{z} \in U\) with \(\mathbf{z} \neq \mathbf{y}\text{,}\) \(\| \mathbf{x} - \mathbf{y} \| \lt \| \mathbf{x} - \mathbf{z} \|\text{.}\)

🔗

Remark 4.2.5.

The following theorem gives us a practical way to calculate orthogonal projections.

🔗

Theorem 4.2.6. Projection theorem.

Let \(U\) be a subspace of \(\R^n\) with orthogonal basis \(\{\mathbf{f}_1,\ldots,\mathbf{f}_m\}\text{.}\) For any vector \(\mathbf{x} \in \R^n\text{,}\) define

\begin{equation*} \mathbf{y} = \frac{\mathbf{x}\cdot\mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 + \frac{\mathbf{x}\cdot\mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2 + \cdots + \frac{\mathbf{x}\cdot\mathbf{f}_m}{\|\mathbf{f}_m\|^2}\mathbf{f}_m. \end{equation*}

Then \(\mathbf{y}=\proj_U(\mathbf{x})\text{,}\) and \(\mathbf{x} - \proj_U(\mathbf{x}) \in U^\perp\text{.}\) In particular, if \(\mathbf{x}\) is already in \(U\text{,}\) then \(\mathbf{x}\) equals the displayed sum.

🔗

Why is this true?.

If \(\{ \mathbf{f}_1, \dots, \mathbf{f}_m \}\) is an orthogonal basis for \(U\text{,}\) and we define

\begin{equation*} \mathbf{y} = \frac{\mathbf{x} \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 + \frac{\mathbf{x} \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2 + \cdots + \frac{\mathbf{x} \cdot \mathbf{f}_m}{\|\mathbf{f}_m\|^2}\mathbf{f}_m\text{,} \end{equation*}

then \(\mathbf{y}\) is evidently a linear combination of the basis \(\{ \mathbf{f}_1, \dots, \mathbf{f}_m \}\text{,}\) so \(\mathbf{y} \in U\text{.}\) And Lemma 4.2.3 states that \(\mathbf{x} - \mathbf{y} \in U^\perp\text{.}\) Thus if \(\mathbf{z} \in U\) and \(\mathbf{z} \neq \mathbf{y}\text{,}\) the Pythagorean theorem (Theorem 4.1.7) tells us that

\begin{align*} \| \mathbf{x} - \mathbf{z} \|^2 \amp = \| (\mathbf{x} - \mathbf{y}) + (\mathbf{y} - \mathbf{z}) \|^2\\ \amp = \| \mathbf{x} - \mathbf{y} \|^2 + \| \mathbf{y} - \mathbf{z} \|^2\text{.} \end{align*}

Since \(\mathbf{y} \neq \mathbf{z}\text{,}\) we find that

\begin{equation*} \| \mathbf{x} - \mathbf{z} \|^2 \gt \| \mathbf{x} - \mathbf{y} \|^2\text{,} \end{equation*}

and taking square roots gives that

\begin{equation*} \| \mathbf{x} - \mathbf{z} \| \gt \| \mathbf{x} - \mathbf{y} \|\text{.} \end{equation*}

Thus the vector \(\mathbf{y}\) we have defined is equal to \(\proj_U(\mathbf{x})\text{.}\) Since we have already verified that \(\mathbf{x} - \mathbf{y} = \mathbf{x} - \proj_U(\mathbf{x})\) is in \(U^\perp\text{,}\) the theorem follows.

🔗

Activity 4.2.3.

Find \(\proj_U \mathbf{x}\) where \(U = \spans \{(1,1,0), (1,-1,0)\}\) and \(\mathbf{x} = (2,0,1)\) in \(\R^3\text{.}\)

🔗

Solution.

The vectors \(\mathbf{f}_1 = (1,1,0)\) and \(\mathbf{f}_2 = (1,-1,0)\) are already orthogonal, as

\begin{equation*} \mathbf{f}_1 \cdot \mathbf{f}_2 = 1 \cdot 1 + 1 \cdot (-1) + 0 \cdot 0 = 0\text{.} \end{equation*}

They thus form an orthogonal basis for \(U\text{.}\) We calculate the following values:

\begin{align*} \mathbf{x} \cdot \mathbf{f}_1 \amp = (2,0,1) \cdot (1,1,0) = 2 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 = 2\\ \|\mathbf{f}_1\|^2 \amp = 1^2 + 1^2 + 0^2 = 2\\ \mathbf{x} \cdot \mathbf{f}_2 \amp = (2,0,1) \cdot (1,-1,0) = 2 \cdot 1 + 0 \cdot (-1) + 1 \cdot 0 = 2\\ \|\mathbf{f}_2\|^2 \amp = 1^2 + (-1)^2 + 0^2 = 2 \end{align*}

Using Theorem 4.2.6, we calculate that

\begin{align*} \proj_U \mathbf{x} \amp = \frac{\mathbf{x} \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 + \frac{\mathbf{x} \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2\\ \amp = \frac{2}{2}\begin{bmatrix}1\\1\\0\end{bmatrix} + \frac{2}{2}\begin{bmatrix}1\\-1\\0\end{bmatrix} = \begin{bmatrix}2\\0\\0\end{bmatrix}\text{.} \end{align*}

🔗

Activity 4.2.4. Projection onto a line.

Let

\begin{equation*} \mathbf{u}=\begin{bmatrix}3\\4\end{bmatrix},\qquad \mathbf{x}=\begin{bmatrix}2\\5\end{bmatrix},\qquad L=\operatorname{span}\{\mathbf{u}\}. \end{equation*}

🔗

Compute \(\operatorname{proj}_L(\mathbf{x})\text{.}\)
🔗

🔗
Compute the residual \(\mathbf{r}=\mathbf{x}-\operatorname{proj}_L(\mathbf{x})\text{.}\)
🔗

🔗
Check that \(\mathbf{r}\cdot\mathbf{u}=0\text{.}\)
🔗

🔗

Solution.

We have \(\mathbf{x}\cdot\mathbf{u}=26\) and \(\mathbf{u}\cdot\mathbf{u}=25\text{.}\) Therefore

\begin{equation*} \operatorname{proj}_L(\mathbf{x}) = \frac{\mathbf{x}\cdot\mathbf{u}}{\mathbf{u}\cdot\mathbf{u}}\mathbf{u} = \frac{26}{25}\begin{bmatrix}3\\4\end{bmatrix} = \begin{bmatrix}78/25\\104/25\end{bmatrix}. \end{equation*}

The residual is

\begin{equation*} \mathbf{r} = \begin{bmatrix}2\\5\end{bmatrix} - \begin{bmatrix}78/25\\104/25\end{bmatrix} = \begin{bmatrix}-28/25\\21/25\end{bmatrix}. \end{equation*}

Finally,

\begin{equation*} \mathbf{r}\cdot\mathbf{u} = \left(-\frac{28}{25}\right)3+\left(\frac{21}{25}\right)4 = 0. \end{equation*}

🔗

Activity 4.2.5. Projection onto a line in code.

The following code computes the same projection and residual as the previous activity.

🔗

u = np.array([3.0, 4.0])
x = np.array([2.0, 5.0])

y = (x @ u) / (u @ u) * u
r = x - y

y, r, r @ u

Which variable stores the projection?
🔗

🔗
Which variable stores the residual?
🔗

🔗
Why should r @ u be close to zero?
🔗

🔗
What formula is represented by (x @ u) / (u @ u) * u?
🔗

🔗

Solution.

The variable y stores the projection and r stores the residual. The value r @ u checks whether the residual is orthogonal to the direction of the line, so it should be close to zero. The expression (x @ u) / (u @ u) * u represents \(((\mathbf{x}\cdot\mathbf{u})/(\mathbf{u}\cdot\mathbf{u}))\mathbf{u}\text{.}\)

🔗

Connection: attention versus projection.

The Unit 1 attention activities, including Many-token attention output, used dot products to make scores and then used weights to mix value vectors. In the language of this unit, the output lies in the span of the value vectors. Thus attention uses the same two operations we have been studying: dot products and linear combinations.

🔗

Note 4.2.7. Attention is not orthogonal projection.

Attention and projection both use dot products, but they solve different problems. In a simple attention step, dot products produce scores, the scores are normalized into weights, and the output is a weighted average of value vectors.

🔗

In orthogonal projection, the goal is different: find the closest vector in a subspace. The residual is perpendicular to the subspace.

🔗

So both ideas use dot products, but they answer different questions. Attention asks which stored vectors should be mixed. Projection asks which vector in a subspace is closest. This distinction matters: not every dot-product method is a projection method.

🔗

Activity 4.2.6. Weighted average or projection?

For each description, decide whether it is closer to attention or orthogonal projection:

The output is a weighted average of stored value vectors.

🔗
The output is the closest point in a subspace.

🔗
The residual is orthogonal to every column of \(A\text{.}\)

🔗
The weights are obtained by normalizing relevance scores.

🔗

🔗

Solution.

The first and fourth descriptions are closer to attention. The second and third descriptions are projection.

🔗

Subsection Gram-Schmidt orthogonalization

Repeatedly applying Lemma 4.2.3 gives the following result:

🔗

Theorem 4.2.8. The Gram-Schmidt orthogonalization algorithm.

Let \(U\) be a subspace of \(\R^n\text{.}\) Then \(U\) has an orthogonal basis.

🔗

Given a basis \(\{ \mathbf{x}_1, \dots, \mathbf{x}_m \}\) of \(U\text{,}\) we can iteratively define an orthogonal basis \(\{ \mathbf{f}_1, \dots, \mathbf{f}_m \}\) of \(U\) by defining

\begin{align*} \mathbf{f}_1 \amp = \mathbf{x}_1\\ \mathbf{f}_2 \amp = \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1\\ \mathbf{f}_3 \amp = \mathbf{x}_3 - \frac{\mathbf{x}_3 \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 - \frac{\mathbf{x}_3 \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2 \end{align*}

and so on, i.e., for \(2 \leq k \leq m\) defining

\begin{equation*} \mathbf{f}_k = \mathbf{x}_k - \frac{\mathbf{x}_k \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 - \frac{\mathbf{x}_k \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2 - \cdots - \frac{\mathbf{x}_k \cdot \mathbf{f}_{k-1}}{\|\mathbf{f}_{k-1}\|^2}\mathbf{f}_{k-1}\text{.} \end{equation*}

Then

\(\{\mathbf{f}_1, \mathbf{f}_2, \ldots, \mathbf{f}_m\}\) is an orthogonal basis of \(U\text{.}\)

🔗
\(\spans \{\mathbf{f}_1, \mathbf{f}_2, \ldots, \mathbf{f}_k\} = \spans \{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k\}\) for each \(k = 1, 2, \ldots, m\text{.}\)

🔗

🔗

Activity 4.2.7.

Find an orthogonal basis of \(\row(A)\) (recall Definition 2.4.21), where

\begin{equation*} A = \begin{bmatrix} 1 \amp 1 \amp -1 \amp -1 \\ 3 \amp 2 \amp 0 \amp 1 \\ 1 \amp 0 \amp 1 \amp 0 \end{bmatrix}\text{.} \end{equation*}

🔗

Solution.

Let \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\) be the three rows of \(A\text{,}\) written in order from top to bottom, and apply the Gram-Schmidt algorithm. We start by writing

\begin{equation*} \mathbf{f}_1 = \mathbf{x}_1 = \begin{bmatrix} 1 \amp 1 \amp -1 \amp -1 \end{bmatrix}\text{.} \end{equation*}

We then write

\begin{align*} \mathbf{f}_2 \amp = \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1\\ \amp = (3,2,0,1) - \frac{4}{4}(1,1,-1,-1) = (2,1,1,2)\text{,} \end{align*}

and then write

\begin{align*} \mathbf{f}_3 \amp = \mathbf{x}_3 - \frac{\mathbf{x}_3 \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 - \frac{\mathbf{x}_3 \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2\\ \amp = (1,0,1,0) - \frac{0}{4}\mathbf{f}_1 - \frac{3}{10}\mathbf{f}_2\\ \amp = (1,0,1,0) - \frac{3}{10}(2,1,1,2)\\ \amp = \frac{1}{10}(10,0,10,0) - \frac{3}{10}(2,1,1,2) = \frac{1}{10}(4,-3,7,-6)\text{.} \end{align*}

The vectors \(\{ \mathbf{f}_1, \mathbf{f}_2, \mathbf{f}_3 \}\) are an orthogonal basis of \(\row(A)\text{.}\)

🔗

Subsection Closest-point activity

Activity 4.2.8.

Find the point in the plane defined by the equation \(2x + y - z = 0\text{,}\) which is closest to the point \((1,2,-1)\text{.}\)

🔗

Solution.

The plane has normal vector \(\mathbf{n}=(2,1,-1)\text{.}\) Since the plane passes through the origin, it is the subspace \(U=\mathbf{n}^\perp\text{.}\) The closest point in \(U\) is obtained by subtracting the component of \(\mathbf{x}\) in the normal direction:

\begin{align*} \proj_U(\mathbf{x}) \amp = \mathbf{x}-\proj_{\spans\{\mathbf{n}\}}(\mathbf{x})\\ \amp = \mathbf{x}-\frac{\mathbf{x}\cdot\mathbf{n}}{\mathbf{n}\cdot\mathbf{n}}\mathbf{n}. \end{align*}

For \(\mathbf{x}=(1,2,-1)\text{,}\) we have \(\mathbf{x}\cdot\mathbf{n}=5\) and \(\mathbf{n}\cdot\mathbf{n}=6\text{.}\) Therefore

\begin{align*} \proj_U(\mathbf{x}) \amp = \begin{bmatrix}1\\2\\-1\end{bmatrix}-\frac{5}{6}\begin{bmatrix}2\\1\\-1\end{bmatrix}\\ \amp = \begin{bmatrix}-2/3\\7/6\\-1/6\end{bmatrix}. \end{align*}

This point satisfies \(2x+y-z=0\text{.}\)

🔗

Prev Top Next