10. Projection Theorem

Projection Theorem

For any vector $\vec{x}\in {\mathbb{R}}^n$ and a subspace $\mathcal{S}\subset {\mathbb{R}}^n$, the projection of $\vec{x}$ onto $\mathcal{S}$ is the unique linear operator in $\mathcal{S}$ that minimizes the distance between $\vec{x}$ and $\mathcal{S}$, defined as
${\Pi }_{\mathcal{S}}(\vec{x})=\arg \underset{\vec{y}\in \mathcal{S}}{\min }||\vec{x}-\vec{y}||,$
such that ${\Pi }_{\mathcal{S}}(\vec{x})\in \mathcal{S}$ and the residual vector $\vec{x}-{\Pi }_S(\vec{x})\perp \mathcal{S}$.

Then, the general solution of ${\Pi }_{\mathcal{S}}(\vec{x})$, given a matrix $S\in {\mathcal{S}}^n$, such that $\mathrm{rank}(S)=n$ (i.e., $S$ is full-rank),
${\Pi }_{\mathcal{S}}(\vec{x})=S(S^{T}S{)}^{-1}{S}^T\vec{x},$
where $P=S(S^{T}S{)}^{-1}{S}^T\in {\mathbb{R}}^{n\times n}$ is called the projection matrix.

If $S$ is not full rank (i.e., $\mathrm{rank}(S)<n$), given an orthonormal basis matrix $B_S$ of $\mathcal{S}$, the orthonormal projection of $\vec{x}$ onto $\mathcal{S}$ can be expressed as
${\Pi }_{\mathcal{S}}(\vec{x})=B_S^T{B}_S\vec{x}={\sum }_{i=1}^n⟨{\overrightarrow{(B_S)}}_i,\vec{x}⟩{\overrightarrow{(B_S)}}_i,$
which can be equivalently written as ${\Pi }_{\mathcal{S}}(\vec{x})={\sum }_{i=1}^n\frac{⟨{\vec{s}}_i,\vec{x}⟩}{\Vert {\vec{s}}_i{\Vert }^2}{\vec{s}}_i$ if the basis vectors $s_i$ are orthogonal rather than orthonormal.

Proof

Properties

(Linearity)

(Orthogonal Decomp.) If $S^{\perp }=\{x\in \mathcal{X}:⟨x,s⟩=0\forall s\in S\}$, then $\mathcal{X}=S\oplus S^{\perp }$.

Examples

Projection Onto a Hyperplane

Conditions: Let $y=\left[\begin{array}{c}0\\ 2\end{array}\right]$, and let $\mathcal{H}=\{x\in {\mathbb{R}}^2:c^{T}x=0\}$ be a hyperplane^3.4c in ${\mathbb{R}}^2$, such that $c=\left[\begin{array}{c}1\\ 1\end{array}\right]$.

Task: Compute the minimum distance from $y$ to $\mathcal{H}$.

Solution: Since $c$ is the normal direction of the hyperplane, it follows that $y-p^{\ast }\parallel c$ (since the error term of a projection is always perpendicular to the space of the projection). This, in turn, implies that the error term is some scaling of $c$, such that
$y-p^{\ast }=\alpha c.$

Since $p^{\ast }\in \mathcal{H}\perp c$, it also follows that $c^T{p}^{\ast }=0$. As such,
$c^T(y-p^{\ast })=⟨c,y⟩-0=\alpha \Vert c{\Vert }_2^2⟺\alpha =\frac{⟨c,y⟩}{\Vert c{\Vert }_2^2}.$

Therefore, $\alpha =\frac{2}{2}=1$, meaning that the distance $\Vert y-p^{\ast }{\Vert }_2=\Vert c{\Vert }_2=\sqrt{2}$.