Orthogonal Projection and Best Approximation

Definition Let $V$ be a finite-dimensional inner product space over $\mathbb{F}$ and let $U$ be a subspace. Then $V$ is the orthogonal direct sum

So every $v \in V$ can be written in exactly one way as $v = u + w$ with $u \in U$ and $w \in U^{\perp}$, and then $\lVert v \rVert^2 = \lVert u \rVert^2 + \lVert w \rVert^2$. For existence, choose an orthonormal basis $q_1, \dots, q_r$ of $U$ and extend it to an orthonormal basis $q_1, \dots, q_n$ of $V$. Finite dimension makes this possible, by extending to a basis of $V$ and applying Gram-Schmidt. Then take

The orthonormal expansion of $v$ gives $v = u + w$. Here $u \in U$, and $w \in U^{\perp}$ because each $q_j$ with $j > r$ is orthogonal to $q_1, \dots, q_r$. For uniqueness, if $u + w = u' + w'$ with $u, u' \in U$ and $w, w' \in U^{\perp}$, then $u - u' = w' - w$ lies in $U \cap U^{\perp} = \{0\}$. The norm identity holds because $\langle u, w \rangle = 0$ removes both cross terms from $\lVert u + w \rVert^2$.

Definition Let $U$ be a subspace of a finite-dimensional inner product space $V$ over $\mathbb{F}$. The orthogonal projection onto $U$ is the map $P_U \colon V \to V$ that sends $v$ to its $U$ part in the decomposition $V = U \oplus U^{\perp}$. Equivalently, $P_U v$ is the unique vector with

If $q_1, \dots, q_r$ is an orthonormal basis of $U$, then

The basis vector sits in the conjugate-linear first slot of each coefficient, so the coefficient is linear in $v$. The map $P_U$ is linear, fixes every vector of $U$ and sends every vector of $U^{\perp}$ to $0$. Because the decomposition is unique, $P_U$ does not depend on which orthonormal basis of $U$ is used. For a basis $u_1, \dots, u_r$ of $U$ that is not orthonormal, $P_U v = \sum_j c_j u_j$, where the coefficients solve $Gc = h$ with the Gram matrix $G_{ij} = \langle u_i, u_j \rangle$ and $h_i = \langle u_i, v \rangle$. These equations say exactly that $\langle u_i, v - P_U v \rangle = 0$ for each $i$.

Definition Let $U$ be a subspace of an inner product space $V$ over $\mathbb{F}$ and let $v \in V$. A best approximation to $v$ from $U$ is a vector $u_0 \in U$ with

The tool for finding it is the squared-distance identity. If $p \in U$ and $v - p \in U^{\perp}$, then for every $u \in U$

To see it, write $v - u = (v - p) + (p - u)$. The second piece lies in $U$ and the first is orthogonal to $U$, so both cross terms $\langle v - p, p - u \rangle$ and $\langle p - u, v - p \rangle$ vanish when the squared norm is expanded. The term $\lVert p - u \rVert^2$ is positive unless $u = p$. So such a $p$ is a best approximation, and it is the only one.

Definition Let $V$ be a finite-dimensional inner product space over $\mathbb{F}$, let $U$ be a subspace and let $v \in V$. Then the following hold.

1. Exactly one best approximation to $v$ from $U$ exists, namely $P_U v$.

2. A vector $u_0 \in U$ is that best approximation exactly when $v - u_0 \in U^{\perp}$.

3. The squared distance from $v$ to $U$ is

   $$\lVert v - P_U v \rVert^2 = \lVert v \rVert^2 - \lVert P_U v \rVert^2.$$

Existence comes from the orthogonal decomposition, which used finite dimension to build an orthonormal basis. Uniqueness and the test in part 2 come from the squared-distance identity. A vector that passes the test is the unique best approximation, and conversely the unique best approximation is $P_U v$, which passes the test. Part 3 is the Pythagorean identity for $v = P_U v + (v - P_U v)$, and for an orthonormal basis $q_1, \dots, q_r$ of $U$ the subtracted term equals $\sum_j \lvert \langle q_j, v \rangle \rvert^2$. The theorem is about the point $u_0$, not about coordinates. If $U$ is described by a dependent spanning list, several coefficient lists give the same $u_0$. In infinite-dimensional spaces a subspace need not contain a nearest point at all.

Definition Let $V$ be a finite-dimensional inner product space over $\mathbb{F}$. A linear map $P \colon V \to V$ is an orthogonal projector if

Every orthogonal projection $P_U$ is one. It is idempotent because it fixes its own outputs, which lie in $U$. It is self-adjoint because $v - P_U v$ and $v' - P_U v'$ are orthogonal to $U$, so

Conversely, if $P^2 = P = P^{*}$, then $P = P_U$ for $U = \operatorname{im} P$. Indeed $Pv$ lies in $\operatorname{im} P$, and for every image vector $Pz$ the residual $v - Pv$ satisfies

If the columns of $Q \in \mathbb{F}^{n \times r}$ are the coordinates of an orthonormal basis of $U$ in an orthonormal basis of $V$, so that $Q^{*}Q = I_r$, then the matrix of $P_U$ in that basis of $V$ is $QQ^{*}$. In a basis with Gram matrix $G$, the condition $P^{*} = P$ reads $M^{*}G = GM$ for the coordinate matrix $M$ of $P$. Idempotence alone is not enough. A map with $P^2 = P$ is the projection onto its image along its kernel, and when the kernel is not $(\operatorname{im} P)^{\perp}$ the projection is oblique and misses the nearest point for some vectors.

Definition Let $t_1, \dots, t_N$ be distinct real numbers with $N \ge d + 1$. On $\mathcal{P}_d$, the space of polynomials of degree at most $d$ with coefficients in $\mathbb{F}$, the formula

defines an inner product. It is positive definite because $\langle p, p \rangle = \sum_k \lvert p(t_k) \rvert^2 = 0$ forces $p$ to vanish at $N \ge d + 1$ points, and a nonzero polynomial of degree at most $d$ has at most $d$ roots. Polynomial approximation in an inner product space asks for the polynomial in a subspace $U$, such as $\mathcal{P}_e$ with $e < d$, that is closest to a given $p$ in this or another inner product. By the projection theorem the answer is $P_U p$, found from the Gram equations for a basis of $U$. A different inner product, for example one with different sample points, generally gives a different best approximation.