Orthogonal Projection

Find the orthogonal projection of $b$ onto $M = \left\langle u\right\rangle$, and then determine the orthogonal projection of $b$ onto $M^{\perp }$, where $b = \begin{pmatrix} 4 & 8 \end{pmatrix}^{T}$ and $u = \begin{pmatrix} 3 & 1 \end{pmatrix}^{T}$.

Let $A = \begin{pmatrix} 1& 2& 0 \\ 2& 4& 1 \\ 1& 2& 0 \end{pmatrix}$ and $b = \begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}$.

For an orthogonal projector $P$, prove that $\left\| Px\right\|_{2} = \left\| x\right\|_{2}$ if and only if $x \in \mathcal{R}(P)$.

Explain why $A^{T}P_{\mathcal{R}(A)} = A^{T}$ for all $A \in \mathbb {R}^{m\times n}$.

Explain why $P_{M} = \sum_{i=1}^{r} u_{i}u_{i}^{T}$ whenever $B = \left\{ u_{1},u_{2},\ldots ,u_{r}\right\}$ is an orthonormal basis for $M \subseteq \mathbb {R}^{n\times 1}$.

Explain how to use orthogonal reduction techniques to compute the orthogonal projectors onto each of the four fundamental subspaces of a matrix $A \in \mathbb {R}^{m\times n}$.

The line $L$ in $\mathbb {R}^{n}$ passing through two distinct points $u$ and $v$ is $L = u + \left\langle u-v\right\rangle$. If $u \neq 0$ and $v \neq \alpha u$, then $L$ is a line not passing through the origin — i.e., $L$ is not a subspace. Explain how to project a vector $b$ orthogonally onto $L$.

Explain why $\hat{x}$ is a least squares solution for $Ax=b$ if and only if $\left\| A\hat{x}-b\right\|_{2} = \left\| P_{\mathcal{N}(A^{T})}b\right\|_{2}$.

Prove that if $\varepsilon = A\hat{x}-b$, where $\hat{x}$ is a least squares solution for $Ax=b$, then $\left\| \varepsilon \right\|_{2}^{2} = \left\| b\right\|_{2}^{2} - \left\| P_{\mathcal{R}(A)}b\right\|_{2}^{2}$.

Let $M$ be an $r$-dimensional subspace of $\mathbb {R}^{n}$. If $B = \left\{ u_{1},u_{2},\ldots ,u_{r}\right\}$ is an orthonormal basis for $M$, and if $x \in M$, then $x$ equals its Fourier expansion with respect to $B$: $x = \sum_{i=1}^{r}(u_{i}^{T}x)u_{i}$. Show that when $x \notin M$, this same sum $\sum_{i=1}^{r}(u_{i}^{T}x)u_{i}$ is the point in $M$ closest to $x$ — i.e., show $\sum_{i=1}^{r}(u_{i}^{T}x)u_{i} = P_{M}x$.

Determine the orthogonal projection of $b$ onto $M$, where

Let $M$ and $N$ be subspaces of a vector space $V$, and consider the associated orthogonal projectors $P_{M}$ and $P_{N}$.

Let $M$ and $N$ be subspaces of the same vector space, and let $P_{M}$ and $P_{N}$ be orthogonal projectors onto $M$ and $N$, respectively.

Prove that if $M$ and $N$ are subspaces of the same vector space, then the orthogonal projector onto $M\cap N$ is given by $P_{M\cap N} = 2P_{M}(P_{M}+P_{N})^{\dagger }P_{N}$.

Given a square matrix $X$, the matrix exponential is $e^{X} = I+X+\dfrac {X^{2}}{2!}+\dfrac {X^{3}}{3!}+\cdots = \sum_{n=0}^{\infty } \dfrac {X^{n}}{n!}$, and it is legitimate to differentiate/integrate it term by term, giving $de^{At}/dt = Ae^{At} = e^{At}A$ and $\int e^{At}A\, dt = e^{At}$.

An affine space $v+M \subseteq \mathbb {R}^{n}$ for which $\dim M = n-1$ is called a hyperplane.

For $u,w \in \mathbb {R}^{n}$ such that $u^{T}w \neq 0$, let $M = u^{\perp }$ and $W = \left\langle w\right\rangle$.

For a consistent system $A_{n\times r}x=b$ with $\operatorname {rk}\left(A\right)=r$, scale the rows so that $\left\| A_{i*}\right\|_{2}=1$ for each $i$, and let $H_{i} = \left\{ x \mid A_{i*}x=b_{i}\right\}$ be the hyperplane defined by the $i$th equation. Beginning with an arbitrary vector $p_{0}$, the Kaczmarz sequence is generated by the double loop For $k=0,1,2,3,\ldots$ For $i=1,2,\ldots ,n$ $p_{kn+i} = p_{kn+i-1} - (A_{i*}p_{kn+i-1}-b_{i})(A_{i*})^{T}$ Prove that the Kaczmarz sequence converges to the solution $x$ of $Ax=b$ by showing

Assume a nonsingular system $A_{n\times n}x=b$ has been row scaled so that $\left\| A_{i*}\right\|_{2}=1$ for each $i$, and let $H_{i} = \left\{ x \mid A_{i*}x=b_{i}\right\}$. In theory, the system can be solved by $n-1$ oblique projections (Exercise 5.13.18): an arbitrary point $p_{1}$ in $H_{1}$ is projected obliquely onto $H_{2}$ along $H_{1}$ to produce $p_{2} \in H_{1}\cap H_{2}$, then $p_{2}$ is projected onto $H_{3}$ along $H_{1}\cap H_{2}$ to produce $p_{3}$, and so on. Since $\bigcap_{i=1}^{k} H_{i}$ is generally unknown, the procedure is modified — use the following figure, showing the $n=3$ case, as a guide.

Successive oblique projections for n=3: p_1^{(1)} is projected through p_2^{(1)}, p_3^{(1)} onto \mathcal{H}_2, producing points in \mathcal{H}_1 \cap \mathcal{H}_2.

Step 0. Begin with any set $\left\{ p_{1}^{(1)}, p_{2}^{(1)}, \ldots , p_{n}^{(1)}\right\} \subset H_{1}$ such that $\left\{ p_{1}^{(1)}-p_{2}^{(1)}, \ldots , p_{1}^{(1)}-p_{n}^{(1)}\right\}$ is linearly independent and $A_{2*}(p_{1}^{(1)}-p_{k}^{(1)}) \neq 0$ for $k=2,\ldots ,n$. Step 1. In turn, project $p_{1}^{(1)}$ onto $H_{2}$ through $p_{2}^{(1)},\ldots ,p_{n}^{(1)}$ to produce $\left\{ p_{2}^{(2)},\ldots ,p_{n}^{(2)}\right\} \subset H_{1}\cap H_{2}$. Step 2. Project $p_{2}^{(2)}$ onto $H_{3}$ through $p_{3}^{(2)},\ldots ,p_{n}^{(2)}$ to produce $\left\{ p_{3}^{(3)},\ldots ,p_{n}^{(3)}\right\} \subset H_{1}\cap H_{2}\cap H_{3}$, and so on. Step $n-1$. Project $p_{n-1}^{(n-1)}$ through $p_{n}^{(n-1)}$ to produce $p_{n}^{(n)} \in \bigcap_{i=1}^{n} H_{i}$. Then $x = p_{n}^{(n)}$ is the solution. Explain why the following algorithm performs the computations of Steps $1,2,\ldots ,n-1$. For $i=2$ to $n$ For $j=i$ to $n$ $x_{j} \leftarrow x_{j} - (A_{i*}x_{i-1}-b_{i})\dfrac {x_{i-1}-x_{j}}{A_{i*}(x_{i-1}-x_{j})}$ $x \leftarrow x_{n}$ (the solution of the system)

Let $M$ be a subspace of $\mathbb {R}^{n}$, and let $R = I-2P_{M}$. Prove that the orthogonal distance between any point $x \in \mathbb {R}^{n}$ and $M^{\perp }$ is the same as the orthogonal distance between $Rx$ and $M^{\perp }$ (i.e., $R$ reflects everything about $M^{\perp }$).

In 1938 the Italian mathematician Gianfranco Cimmino used the following elementary observation to construct an iterative algorithm for solving linear systems. For a $2\times 2$ system $Ax=b$, let $H_{1}$ and $H_{2}$ be the two lines (hyperplanes) defined by the two equations. For an arbitrary guess $r_{0}$, let $r_{1}$ be the reflection of $r_{0}$ about the line $H_{1}$, and let $r_{2}$ be the reflection of $r_{0}$ about the line $H_{2}$. As illustrated below, the three points $r_{0}$, $r_{1}$, and $r_{2}$ lie on a circle whose center is $H_{1}\cap H_{2}$ (the solution of the system).

The reflections r_1, r_2 of an arbitrary point r_0 about lines \mathcal{H}_1, \mathcal{H}_2 lie, together with r_0, on a circle centered at \mathcal{H}_1 \cap \mathcal{H}_2.

The mean value $m = (r_{1}+r_{2})/2$ is strictly inside the circle, so $m$ is a better approximation to the solution than $r_{0}$. It's visually evident that iteration produces a sequence that converges to the solution of $Ax=b$. Prove this in general by using the following blueprint.