Exercises — Lesson 6: Orthogonal Projections and Least Squares
Exercise 6.1. [Hand] Run Gram–Schmidt on \(v_1 = (1,1,0)\), \(v_2 = (1,0,1)\) to produce an orthonormal basis \(e_1, e_2\) of their span \(U\). Then compute \(P_U x\) for \(x = (0,0,3)\) and verify \(x - P_U x\) is orthogonal to both \(e_1\) and \(e_2\).
Solution. With \(v_1 = (1,1,0)\) and \(v_2 = (1,0,1)\), take \(f_1 = v_1\):
\[ e_1 = \frac{f_1}{\lVert f_1 \rVert} = \left( \frac{1}{\sqrt{2}},\, \frac{1}{\sqrt{2}},\, 0 \right) \]
\[ \begin{aligned} f_2 &= v_2 - \langle v_2, e_1 \rangle e_1 = (1,0,1) - \frac{1}{\sqrt{2}} \left( \frac{1}{\sqrt{2}},\, \frac{1}{\sqrt{2}},\, 0 \right) = \left( \tfrac{1}{2},\, -\tfrac{1}{2},\, 1 \right) \\[6pt] \lVert f_2 \rVert &= \sqrt{\tfrac{3}{2}}, \qquad \frac{1}{\lVert f_2 \rVert} = \sqrt{\tfrac{2}{3}} \end{aligned} \]
\[ e_2 = \frac{f_2}{\lVert f_2 \rVert} = \left( \frac{\sqrt{2}}{2\sqrt{3}},\, \frac{-\sqrt{2}}{2\sqrt{3}},\, \frac{\sqrt{2}}{\sqrt{3}} \right) \]
Projecting \(x = (0,0,3)\):
\[ \begin{aligned} P_U x &= \langle x, e_1 \rangle e_1 + \langle x, e_2 \rangle e_2 \\ &= 0 \cdot e_1 + \sqrt{6}\, e_2 = \left( \frac{\sqrt{12}}{2\sqrt{3}},\, \frac{-\sqrt{12}}{2\sqrt{3}},\, \frac{\sqrt{12}}{\sqrt{3}} \right) = (1, -1, 2) \\[6pt] x - P_U x &= \left( \frac{-\sqrt{12}}{2\sqrt{3}},\, 1,\, 1 \right) \end{aligned} \]
Exercise 6.2. [Hand] Fit the least-squares line to \((0,0), (1,1), (2,1), (3,2)\) via the normal equations. Verify the residual is orthogonal to both columns of your \(A\).
Solution. With the data as \((t_i, y_i)\) and model \(y \approx c + dt\):
\[ \underbrace{\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix}}_{A} \underbrace{\begin{pmatrix} c \\ d \end{pmatrix}}_{x} \approx \underbrace{\begin{pmatrix} 0 \\ 1 \\ 1 \\ 2 \end{pmatrix}}_{b} \qquad \begin{aligned} 0 &= 1c + 0d \\ 1 &= 1c + 1d \\ 1 &= 1c + 2d \\ 2 &= 1c + 3d \end{aligned} \]
Forming the normal equations:
\[ \begin{aligned} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix} &= \begin{pmatrix} 4 & 6 \\ 6 & 14 \end{pmatrix} && \text{[$A^\mathsf{T} A$]} \\[8pt] \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 2 \end{pmatrix} &= \begin{pmatrix} 4 \\ 9 \end{pmatrix} && \text{[$A^\mathsf{T} b$]} \end{aligned} \]
\[ \underbrace{\begin{pmatrix} 4 & 6 \\ 6 & 14 \end{pmatrix}}_{A^\mathsf{T} A} \underbrace{\begin{pmatrix} c \\ d \end{pmatrix}}_{\hat{x}} = \underbrace{\begin{pmatrix} 4 \\ 9 \end{pmatrix}}_{A^\mathsf{T} b} \qquad \Longrightarrow \qquad c = \frac{1}{10}, \quad d = \frac{3}{5} \]
\[ \boxed{\; y \approx \frac{1}{10} + \frac{3}{5}\,t \;} \]
Exercise 6.3. [Proof, \(\star\)] Prove that \(\mathbb{R}^n = U \oplus U^\perp\) for every subspace \(U\); that is, every \(x\) is uniquely a sum of a vector in \(U\) and a vector in \(U^\perp\). (Existence: Theorem 6.3(a). Uniqueness: show \(U \cap U^\perp = \{0\}\) — what is \(\langle v, v \rangle\) for \(v\) in both?)
Proof. Prove \(V = U \oplus U^\perp\) for every subspace \(U\).
(Existence). Let \(e_1, \dots, e_k\) be an orthonormal basis of \(U\). Let \(v \in V\). Note
\[ v = P_U v + (v - P_U v), \]
where \(P_U v \in U\) and \((v - P_U v) \in U^\perp\), which we proved in Theorem 6.3.
(Uniqueness). \(\langle P_U v,\, v - P_U v \rangle = 0\) for all \(v \in V\). Suppose \(x \in U \cap U^\perp\). Since \(x \in U^\perp\), \(\langle x, u \rangle = 0\) for all \(u \in U\). But \(x \in U\), so
\[ \langle x, x \rangle = 0 \implies x = 0 \implies U \cap U^\perp = \{0\}. \]
Thus \(V = U \oplus U^\perp\). \(\square\)
Exercise 6.4. [Proof] Show \(\langle P_U x, y \rangle = \langle x, P_U y \rangle\) for all \(x, y\) (projections are self-adjoint), and \(P_U(P_U x) = P_U x\) (idempotent), directly from the formula in Theorem 6.3.
Proof. Let \(e_1, \dots, e_k\) be an orthonormal basis for a subspace \(U\) in a vector space \(V\). Let \(x, y \in V\). Then
\[ P_U x = \sum_{i=1}^{k} \langle x, e_i \rangle e_i \qquad \text{and} \qquad P_U y = \sum_{i=1}^{k} \langle y, e_i \rangle e_i . \]
Self-adjointness.
\[ \begin{aligned} \langle P_U x, y \rangle &= \left\langle \sum_{i=1}^{k} \langle x, e_i \rangle e_i,\; y \right\rangle = \sum_{i=1}^{k} \langle x, e_i \rangle \langle e_i, y \rangle \\[6pt] \langle x, P_U y \rangle &= \left\langle x,\; \sum_{i=1}^{k} \langle y, e_i \rangle e_i \right\rangle = \sum_{i=1}^{k} \langle y, e_i \rangle \langle e_i, x \rangle \end{aligned} \]
\(\Longrightarrow\) equal, since inner products are symmetric and field multiplication commutes.
Idempotence.
\[ \begin{aligned} P_U(P_U x) &= \sum_{i=1}^{k} \langle P_U x, e_i \rangle e_i = \sum_{i=1}^{k} \left\langle \left( \sum_{j=1}^{k} \langle x, e_j \rangle e_j \right),\; e_i \right\rangle e_i \\[6pt] &= \sum_{i=1}^{k} \left( \sum_{j=1}^{k} \langle x, e_j \rangle \langle e_j, e_i \rangle \right) e_i && \text{(Note $\langle e_j, e_i \rangle = 0$ when $j \neq i$)} \\[6pt] &= \sum_{i=1}^{k} \langle x, e_i \rangle e_i = P_U x \end{aligned} \]
Thus \(\langle P_U x, y \rangle = \langle x, P_U y \rangle\) and \(P_U(P_U x) = P_U x\). \(\square\)