Norm Minimization

Norm Minimization

Recall from the Orthogonal Projection Operators page that if $V$ is an inner product space and $U$ is a subspace of $V$ such that $V = U \oplus U^{\perp}$ then any $v \in V$ can be written as the sum $v = u + w$ where $u \in U$ and $w \in U^{\perp}$ and the orthogonal projection operator of $V$ onto $U$ is $P_U \in \mathcal L(V)$ defined as $P_U(v) = u$ for all $v \in V$.

We will now look at one application of such orthogonal projection operators - that being in minimization problems. Suppose that we have an inner product space $V$ and $U$ is a subspace of $V$. Further suppose that $v \in V$ and that we want to find the vector $u^* \in U$ such that the norm of $v$ and $u^*$ is a minimum, that is $\| v - u^* \| ≤ \| v - u \|$ for all $u \in U$.

If $v \in U$, then $u^* = v$ since $\| v - u^* \| = \| v - v \| = 0$. Instead consider the case where $v \not \in U$. It's not hard to see that in this case, $u^* = P_U(v)$.

We will formally prove this with the following theorem that will lay this foundation for solving various minimization problems.

 Theorem 1: Let $V$ be an inner product space and $U$ be a finite-dimensional subspace of $V$ so that $V = U \oplus U^{\perp}$. Let $v \in V$. Then for every vector $u \in U$ we have that $\| v - P_U(v) \| ≤ \| v - u \|$.
• Proof: Let $u \in U$. Note the vectors $v - P_U(v)$ and $P_u(v) - u$ are orthogonal since $(v - P_U(v)) \in U^{\perp}$ and $(P_U(v) - u) \in U$ and so in applying the Pythagorean Theorem we have that:
(1)
\begin{align} \quad \| v - P_U(v) \|^2 ≤ \| v - P_U(v) \|^2 + \| P_U(v) - u \|^2 = \| v - P_U(v) + P_U(v) - u \|^2 = \| v - u \|^2 \end{align}
• If we take the square root of both sides of the inequality above, we get that $\| v - P_U(v) \| ≤ \| v - u \|$ for every $u \in U$. $\blacksquare$