Finding The Closest Vector In A Subspace

Closest Points and Orthogonal Residuals

Suppose a vector \(\mathbf{x}\in\mathbb{R}^n\) does not lie in a subspace \(S\). A natural approximation is a vector in \(S\) that is as close as possible to \(\mathbf{x}\). The key is not to compare \(\mathbf{x}\) with every vector in \(S\). Instead, find a candidate whose error points perpendicular to the whole subspace. That perpendicular error is called the residual.

Throughout, \(\mathbb{R}^n\) has the standard dot product \(\mathbf{u}\cdot\mathbf{v}=\mathbf{u}^{\top}\mathbf{v}\) and norm \(\|\mathbf{u}\|=\sqrt{\mathbf{u}\cdot\mathbf{u}}\). A vector \(\mathbf{r}\) is orthogonal to a subspace \(S\) if \(\mathbf{r}\cdot\mathbf{s}=0\) for every \(\mathbf{s}\in S\). For a candidate \(\mathbf{p}\in S\), the residual for approximating \(\mathbf{x}\) by \(\mathbf{p}\) is \(\mathbf{x}-\mathbf{p}\).

The characterization below is the practical test for a proposed answer: check that it belongs to the target subspace, then check that the residual is perpendicular to that subspace. It also proves that a vector passing both checks really is the closest one.

Proof. First suppose \(\mathbf{p}\in S\) and \(\mathbf{r}=\mathbf{x}-\mathbf{p}\) is orthogonal to \(S\). For any \(\mathbf{y}\in S\), the difference \(\mathbf{p}-\mathbf{y}\) belongs to \(S\), so \(\mathbf{r}\cdot(\mathbf{p}-\mathbf{y})=0\). Since \(\mathbf{x}-\mathbf{y}=\mathbf{r}+(\mathbf{p}-\mathbf{y})\), expansion of the dot product gives \(\|\mathbf{x}-\mathbf{y}\|^2=\|\mathbf{r}\|^2+\|\mathbf{p}-\mathbf{y}\|^2\). The second term is nonnegative, and it is zero exactly when \(\mathbf{y}=\mathbf{p}\). Thus \(\mathbf{p}\) is the unique closest vector.

Conversely, suppose \(\mathbf{p}\in S\) is closest, and set \(\mathbf{r}=\mathbf{x}-\mathbf{p}\). Fix any \(\mathbf{w}\in S\). For every real \(t\), \(\mathbf{p}+t\mathbf{w}\in S\), so minimality at \(\mathbf{p}\) implies \(\|\mathbf{r}\|^2\leq\|\mathbf{r}-t\mathbf{w}\|^2 =\|\mathbf{r}\|^2-2t(\mathbf{r}\cdot\mathbf{w})+t^2\|\mathbf{w}\|^2\). If \(\mathbf{w}=\mathbf{0}\), then \(\mathbf{r}\cdot\mathbf{w}=0\). If \(\mathbf{w}\ne\mathbf{0}\) and \(\mathbf{r}\cdot\mathbf{w}\ne0\), choose \(t=(\mathbf{r}\cdot\mathbf{w})/\|\mathbf{w}\|^2\). Substitution makes the right side \(\|\mathbf{r}\|^2-(\mathbf{r}\cdot\mathbf{w})^2/\|\mathbf{w}\|^2\), which is strictly less than \(\|\mathbf{r}\|^2\), a contradiction. Therefore \(\mathbf{r}\cdot\mathbf{w}=0\) for every \(\mathbf{w}\in S\). This proves both directions and uniqueness. \(\square\)

A Reliable Method for Finding the Projection

The theorem turns a nearest-vector problem into a construction problem. Choose a convenient way to describe the subspace, find a vector in it, and impose orthogonality on the residual. For a line, this leads to a single scalar coefficient. For a plane in \(\mathbb{R}^3\), a normal vector often gives the shortest route. For a column space, an orthonormal basis or the full-column-rank projection formula is useful.

If \(\mathbf{q}_1,\dots,\mathbf{q}_r\) form an orthonormal basis of \(S\), meaning that each has norm \(1\) and distinct vectors have dot product \(0\), the projection has a particularly direct form.

Indeed, the formula produces a vector in \(S\). Its residual has dot product zero with each basis vector: the dot product with \(\mathbf{q}_k\) is \(\mathbf{x}\cdot\mathbf{q}_k-\sum_j(\mathbf{x}\cdot\mathbf{q}_j)(\mathbf{q}_j\cdot\mathbf{q}_k)=0\), since \(\mathbf{q}_j\cdot\mathbf{q}_k\) equals \(1\) when \(j=k\) and \(0\) otherwise. By the theorem, the formula gives the closest vector.

Projecting onto a Line

This calculation also explains the line projection formula. For a nonzero generator \(\mathbf{u}\), the candidate is \(c\mathbf{u}\), and the residual condition gives \(c=(\mathbf{x}\cdot\mathbf{u})/(\mathbf{u}\cdot\mathbf{u})\). The denominator is nonzero because \(\mathbf{u}\ne\mathbf{0}\). If the line is instead described by an orthonormal vector \(\mathbf{q}\), then \(\mathbf{q}\cdot\mathbf{q}=1\), so the coefficient reduces to \(\mathbf{x}\cdot\mathbf{q}\).

Projecting onto a Plane

A normal vector is especially convenient when a plane is described by a single equation. For example, if \(P=\{\mathbf{y}:\mathbf{n}\cdot\mathbf{y}=0\}\) with \(\mathbf{n}\ne\mathbf{0}\), then \(\mathbf{x}-\operatorname{proj}_P\mathbf{x}\) lies in the normal direction. In the example, this let us find the residual first, then obtain the projected vector by subtraction.

Projecting onto a Column Space

The column space \(\operatorname{Col}\mathbf{A}\) is the set of all linear combinations of the columns of \(\mathbf{A}\). If \(\mathbf{A}\in\mathbb{R}^{m\times n}\) has linearly independent columns, the projection matrix for this space is \(\mathbf{A}(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\). The independence condition matters: it ensures \(\mathbf{A}^{\top}\mathbf{A}\) is invertible. Equivalently, if \(\mathbf{A}\) has orthonormal columns, this expression simplifies to \(\mathbf{A}\mathbf{A}^{\top}\). If the given columns are dependent, choose an independent set of columns that spans the same column space, or use an orthonormal basis for that space; do not apply the inverse formula to a singular Gram matrix.

The projection formula can be checked through this same residual test. For a full-column-rank matrix, let \(\mathbf{c}=(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\mathbf{x}\) and \(\mathbf{p}=\mathbf{A}\mathbf{c}\). Then \(\mathbf{A}^{\top}(\mathbf{x}-\mathbf{p})=\mathbf{A}^{\top}\mathbf{x}-\mathbf{A}^{\top}\mathbf{A}\mathbf{c}=\mathbf{0}\). The entries of this product are the dot products of the residual with the columns of \(\mathbf{A}\). Consequently the residual is orthogonal to every column and every vector in their span. The orthogonal residual characterization then verifies the formula’s result.

A Common Mistake: Adding Projections onto Nonorthogonal Generators

In the plane example, the two spanning vectors are not orthogonal: their dot product is \(1\). A tempting calculation is to add the individual line projections of \(\mathbf{x}\) onto each generator. That method is valid for an orthogonal list, but not for this pair.

For these generators, the separate line projections are \(\frac{3}{2}(1,1,0)^{\top}=(3/2,3/2,0)^{\top}\) and \(\frac{5}{2}(1,0,1)^{\top}=(5/2,0,5/2)^{\top}\). Adding them gives the incorrect candidate \(\widetilde{\mathbf{p}}=(4,3/2,5/2)^{\top}\). Although this vector lies in the plane, its residual is \(\mathbf{x}-\widetilde{\mathbf{p}}=(-2,-1/2,1/2)^{\top}\), and \((1,1,0)\cdot(\mathbf{x}-\widetilde{\mathbf{p}})=-5/2\ne0\). So the residual is not perpendicular to the plane, and the candidate cannot be the closest vector. The correction is to use a normal vector, an orthonormal basis, or the appropriate column-space projection formula, then verify the residual.