[Linear Algebra] Projection

Projection

Definition and Properties

$\mathbf{Def.}$ Projector $P$
If a square matrix $P$ is idempotent, i.e., $P^2 = P$, it is called projector.

$\mathbf{Properties.}$
1. $v \in \text{range}(P) \Rightarrow Pv = v$.

2. $v - Pv \in \text{ker}(P)$.

3. $I - P$ is also projector. And it is called complementary projector of $P$ since it projects the vector to $\text{ker}(P)$, i.e., $\text{range}(I - P) = \text{null}(P)$:

\[\begin{align*} &v \in \text{range}(I - P) \Rightarrow \exists x \; x - Px = v \Rightarrow Pv = 0 \\ &v \in \text{ker}(P) \Rightarrow Pv = 0 \Rightarrow (I - P)v = v \end{align*}\]

4. \(\text{range}(P) \cup \text{range}(I - P) = \text{range}(P) \cup \text{null}(P) = \{ \mathbf{0} \}\)

The last property is saying that the projector $P$ separates $\mathbb{C}^n$ into two spaces:

$\mathbf{Thm\ 1.}$ Projection Theorem
If $W$ is a subspace of $\mathbb{C}^n$, then $\forall x \in \mathbb{C}^n$ can be expressed uniquely as

\[\begin{align*} \mathbf{x} = \mathbf{x}_1 + \mathbf{x}_2 \text{ where } x_1 \in W, x_2 \in W^\perp \end{align*}\]

$\mathbf{Proof.}$

It is obvious when \(W = \{ \mathbf{0} \}\). For \(W \neq \{ \mathbf{0} \}\), let \(\{ \mathbf{w}_1, \cdots, \mathbf{w}_k \}\) be a basis for $W$.

Define a $n \times k$ matrix $M$ where $i$-th column of $M$ is \(\mathbf{w}_i\).

\[\begin{align*} M=\left[\mathbf{w}_1 \cdots \mathbf{w}_k\right] \end{align*}\]

Then, $W = \text{col}(M)$ and $W^\perp = \text{null}(M^\top)$ clearly.

\[\begin{aligned} & \mathbf{x}_1 \in W \leftrightarrow \mathbf{x}_1=M \mathbf{v} \text { for some } \mathbf{v} \in \mathbb{R}^k \\ & \mathbf{x}_2 \in W^{\perp} \leftrightarrow M^{\top} \mathbf{x}_2=0 \leftrightarrow M^{\top}\left(\mathbf{x}-\mathbf{x}_1\right)=0 \leftrightarrow M^{\top}(\mathbf{x}-M 0)=0 & M^\top \mathbf{x} = M^\top (\mathbf{x}_1 + \mathbf{x}_2) = M^\top \mathbf{x}_1 = M^\top M \mathbf{v} \end{aligned}\]

Note that $M$ has a full column rank, and it results to invertibility of $M^\top M$:

\[\begin{align*} &M \mathbf{x} = 0 \text{ iff } \mathbf{x} = \mathbf{0} \\ &M^\top M \mathbf{x} = \mathbf{0} \Rightarrow \left\langle M\mathbf{x}, M\mathbf{x}\right\rangle = 0 \Rightarrow \| M \mathbf{x} \|_2^2 = 0 \end{align*}\]

Thus, $\mathbf{x}$ must be zero vector. Now, from the fact that $M^\top M$ is invertible, we can find an explicit formula for $\mathbf{v}$.

\[\begin{align*} &\mathbf{v} = (M^\top M)^{-1} M^\top \mathbf{x} \\ &\mathbf{x}_1 = M \mathbf{v} \\ &\mathbf{x}_2 = \mathbf{x} - \mathbf{x}_1 \end{align*}\]

For uniqueness, let \(\mathbf{x} = \mathbf{x}_1 + \mathbf{x}_2 = \mathbf{x}_1^\prime + \mathbf{x}_2^\prime\). Then, \(\mathbf{x}_1 - \mathbf{x}_1^\prime \in W, \mathbf{x}_2^\prime - \mathbf{x}_2 \in W^\perp\).

So, \(\mathbf{x}_1 - \mathbf{x}_1^\prime = \mathbf{x}_2^\prime - \mathbf{x}_2 \in W \cap W^\perp = \{ \mathbf{0} \}._\blacksquare\)

Orthogonal Projector

Conversely, let $S_1$ and $S_2$ be two subspaces of $\mathbb{C}^n$ such that

\[\begin{align*} S_1 \cap S_2 = \{ \mathbf{0} \}, \; S_1 + S_2 = \mathbb{C}^n. \end{align*}\]

Then, we can derive a projector $P$ such that $\text{range}(P) = S_1$, $\text{null}(P) = S_2$ by defining

\[\begin{align*} P: \mathbf{v} = \mathbf{v}_1 + \mathbf{v}_2 \mapsto \mathbf{v}_1 \end{align*}\]

And this projector $P$ onto $S_1$ along $S_2$ is called an orthogonal projector.

$\mathbf{Def.}$ Orthogonal Projector $P$
An projector that projects onto $S_1$ along $S_2$ where $S_1$ and $S_2$ are orthogonal.

As an idempotency defines a oblique projector, there is an equivalent algebraic definition of orthogonal projector:

$\mathbf{Thm\ 2.}$ Algebraic Definition
A projector $P$ is orthogonal projector if and only if $P$ is self-adjoint.

$\mathbf{Proof.}$

Suppose $P$ is self-adjoint, i.e., $P = P^\star$. Then it is clear that $P$ is a projector by idempotency. Let any $\mathbf{v} \in S_1$, $\mathbf{w} \in S_2$ be given. Then, $\mathbf{v} = P \mathbf{x}, \mathbf{w} = (I - P) \mathbf{y}$ for some $\mathbf{x}$ and $\mathbf{y}$. Then, we have to show $\mathbf{v}$ and $\mathbf{w}$ are orthogonal. But it is obvious: $\mathbf{v} \cdot \mathbf{w} = \mathbf{x}^\star P^\star (I - P) \mathbf{y} = \mathbf{0}$.

Conversely, assume that $P$ is an orthogonal projector. Let \(\{ \mathbf{q}_1, \cdots, \mathbf{q}_n \}\) be orthonormal basis for $\mathbb{C}^n$ where \(\{ \mathbf{q}_1, \cdots, \mathbf{q}_m \}\) is an orthonormal basis for $S_1$, and \(\{ \mathbf{q}_{m+1}, \cdots, \mathbf{q}_n \}\) is that of $S_2$. Then,

\[\begin{align*} P \mathbf{q}_i = \begin{cases}\mathbf{q}_i & (1 \leq i \leq n) \\ \mathbf{0} & (n+1 \leq i \leq m)\end{cases} \end{align*}\]

Thus,

\[\begin{align*} P Q=\left[\mathbf{q}_1|\cdots| \mathbf{q}_n| \mathbf{0} | \cdots \mid \mathbf{0} \right] \leadsto Q^\star P Q=\left[\begin{array}{lll} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & 0 \\ \end{array}\right]=\Sigma \end{align*}\]

As a result, the SVD of $P$ becomes $P = Q \Sigma Q^\star$, which shows $P$ is self-adjoint.

Formulas

As we saw in the proof of $\mathbf{Thm\ 1.}$, an orthogonal projector can be constructed beginning with an arbitrary basis for any vector space $W$: $P = A(A^\star A)^{-1} A^\star$ if $A$ is a matrix of which columns form a basis for $W$.

\[\begin{align*} \text{proj}_W = A(A^\star A)^{-1} A^\star \end{align*}\]

For special case of orthogonal projection to one arbitrary vector $\mathbf{a}$, it becomes

\[\begin{align*} \text{proj}_\mathbf{a} = \frac{\mathbf{a}\mathbf{a}^\star}{(\mathbf{a}^\star \mathbf{a})} \end{align*}\]

Reference

[1] Numerical Linear Algebra, Trefethen and Bau, 1997.
[2] Contemporary Linear Algebra, Howard Anton, Robert C. Busby