# Linear Algebra - Closest point in higher dimension than a plane

Solving closest point in the span of many vectors

Goal:

• An algorithm that, given a vector b and vectors v1, . . . , vn, finds the vector in Span {v1, . . . , vn} that is closest to b.

Special case: We can use the algorithm to determine whether b lies in Span {v1, . . . , vn}: If the vector in Span {v1, . . . , vn} closest to b is b itself then clearly b is in the span; if not, then b is not in the span.

More generally: Even if Ax = b has no solution, we can use the algorithm to find the point in $\{Ax : x \in \mathbb{R}\}$ closest to b.

## 2 - Computation Problem

Goal: find the coefficients x1, . . . , xn so that x1 v1 + · · · + xn vn is the vector in Span {v1, . . . , vn} closest to b.

Two methods:

### 2.1 - Norm Minimization

Equivalent: Find the vector x that minimizes:

1. $\| b - A.x \|$
2. ${\| b - A.x \|}^2$

Given a matrix equation Ax = b that might have no solution, find the best solution available in the sense that the norm of the error b - Ax is as small as possible.

Two algo:

### 2.2 - Least square

Find the vector x that minimizes:

1. $\| b - A.x \|$
2. ${\| b - A.x \|}^2$
3. ${\| \begin{bmatrix}b\end{bmatrix} - \begin{bmatrix} \begin{array}{r|r|r} && \\ v_1 & \dots & v_n \\ && \end{array} \end{bmatrix}. \begin{bmatrix}x\end{bmatrix} ||}^2$
4. ${|| \begin{bmatrix}b\end{bmatrix} - \begin{bmatrix} \begin{array}{r} a_1 \\ \hline \\ \dots \\ \hline \\ a_m \\ \end{array} \end{bmatrix}.\begin{bmatrix}x\end{bmatrix} \|}^2$
5. $(b-a_1.x)^2 + \dots + (b[m]-a_m.x)^2$

This problem is called least squares (”methode des moindres carres”, due to Adrien-Marie Legendre but often attributed to Gauss).

## 3 - Projection

High-dimensional projection onto/orthogonal to

For a vector b and a vector space V, we define the projection of b onto V (written $b^{||V}$) and the projection of b orthogonal to V (written $b^{\perp V}$) so that $$b = b^{||V} + b^{\perp V}$$ where:

• the projection onto V: $b^{||V}$ is in V, and
• the projection orthogonal to V: $b^{\perp V}$ is orthogonal to every vector in V.

### 3.1 - Lemma

High-Dimensional Lemma: The point in vector space V closest to b is $b^{||V}$ and the distance is the norm $\|b^{\perp V}\|$.

### 3.2 - Computation

#### 3.2.1 - Projection orthogonal

The below function will find the projection of b orthogonal to the space spanned by mutually orthogonal vectors.

# input: a vector b, and a list vlist of mutually orthogonal vectors
# output: the projection orthogonal of b (\perp) to the vectors in vlist
def project_orthogonal(b, vlist):
for v in vlist:
b = b - project_along(b, v)
return b

where:

The projection of a vector b orthogonal to a vector space is unique, so in principle the order of vectors in vlist doesn’t affect the output of project orthogonal(b, vlist).

The below function will return the $\sigma$ of all generators.

def aug_project_orthogonal(b, vlist):
for i in range(len(vlist)):
v = vlist[i]
sigma = (b*v)/(v*v) if v*v > 0 else 0
return (b, alphadict)
• Apply orthogonalize to ${v_1} , \dots , {v_n}$ and obtain a span of mutually orthogonal vector $v_1^* , \dots , v_n^*$. Then $V = Span\{v_1^* , \dots , v_n^*\}$
• Call project_orthogonal(b, [$v_1^* , \dots , v_n^*$ ]) and obtain $b^{\perp}$ as the result.
Exactly the same computations take place when orthogonalize is applied. Ie applying orthogonalize to the list of vector $[{v_1} , \dots , {v_n}, b]$ will return $[v_1^* , \dots , v_n^*, b^{\perp}]$