Least Squares #
Motivation #
- We want to find an approximate solution – one that satisfies all the given equations/information as closely as possible to…
- Minimize the impact of noise/errors
- Solve overdetermined systems – we’ll often be collecting abundant information, thus we have more equations than unknowns
- Applications: Least squares is the fundamental idea behind data fitting and machine learning
- In data (curve) fitting, we find lines or curves that best match the data
- In machine learning, we use a best-fit curve to make predictions about new, unseen data.
What #
The goal of least squares is to minimize the error vector’s magnitude (norm) – the square of each of it’s components:
$$\Vert \vec e \Vert = \sqrt{\sum_{i=1}^n e_i^2 }$$
- With $m$ measurements (equations) and $n$ unknowns; $m > n$
- $\text{col}(A)$ is an $n$-dimensional subspace within the larger $m$-dimensional space that $\vec b$ lies in
- That is, $\vec b$ cannot be exactly reached by $A\vec x$
- $\vec x$: Best-guess that minimizes $\Vert \vec e \Vert$
- $\vec x \in \mathbb{R}^{n}$
- $\vec e = \vec b - A\vec x = \vec b - \hat x$: Error vector
- $\vec e \in \mathbb{R}^{n}$
- We want to find $\vec x$ where $\vec e \perp \text{col}(A)$
- $\vec b$: Actual, observed values
- $\vec b \in \mathbb{R}^{m}$
- $\hat x = A \vec x = A (A^T A)^{-1} A^T \vec b$: Predicted values
- $A \in \mathbb{R}^{m \times n}; A\vec x, \hat x \in \mathbb{R}^{m}$
- Can be thought of a linear combination of the columns of $A$, with $\vec x$ acting as weights
Proof #
- We know from the last section that the projection of $\vec a$ onto $\vec b$ results in a vector within the span of $\vec b$ that is closest and orthogonal to $\vec a$
- So we’ll project $\vec b$ onto $\text{col}(A)$ to find the smallest possible $\vec e$
- That is, we know that $\vec e \perp \text{col}(A)$ $\Longrightarrow \vec e \perp \vec a_i $ for each column of $A$ so we can write: $$\langle \vec a_i, \vec e \rangle = 0$$ $$\langle \vec a_i, \vec b - A\vec x \rangle = 0$$ $$\vec a_i^T (\vec b - A\vec x) = 0$$ $$\therefore A^T (\vec b - A \vec x) = \vec 0$$
- Then solving for $\vec x$ in terms of the known $A$ and $\vec b$: $$A^T (\vec b - A \vec x) = \vec 0$$ $$A^T \vec b - A^T A \vec x = \vec 0$$ $$A^T \vec b = A^T A \vec x$$ $$ \therefore \vec x = (A^T A )^{-1} A^T \vec b$$
Theorems #
Theorem 23.1 #
Vector $\vec e$ is orthogonal to every vector in the column space of $A$ iff it is orthogonal to each of the columns $\vec a_i$ that form the basis of its column space
- If $\vec e$ is orthogonal to every vector in the column space of $A$, then it is orthogonal to each of the $\vec a_i$, as each of the $\vec a_i$ are in the column space of $A$ too
- Now, we will try to prove the converse: consider an arbitrary vector $\vec v \in \text{span}(A)$– by definition, we know that there exist coefficients $\alpha_i$ such that we can express $\vec v = \sum_{i=1}^m \alpha_i \vec a_i$
- We also know that $\vec e$ is orthogonal to each $\vec a_i$; that is $\langle \vec e, \vec a_i \rangle = 0$
- We wish to show that $\vec{e}$ is orthogonal to $\vec{v}$ too: $$\langle\vec{e},\vec{v}_i \rangle = \left\langle \vec{e}, \sum_{i=1}^m \alpha_i \vec a_i \right\rangle$$ $$\dots = \sum \left\langle \vec{e}, \alpha_i \vec a_i \right\rangle$$ $$\dots = \sum \alpha_i \left\langle \vec{e}, \vec a_i \right\rangle$$ $$\dots = 0$$
- That is, if $\vec e$ is orthogonal to all the basis vectors of a subspace, it is orthogonal to every vector in that subspace as well!
Theorem 23.2 #
$\text{Null}(A^TA) = \text{Null}(A)$ even when $A$ has a nontrivial nullspace
- Consider an arbitrary $\vec v \in \text{Null}(A^T A)$– by definition, we have $$A^T A \vec v = \vec 0$$ $$\vec v^T (A^T A \vec v) = \vec v^T (\vec 0)$$ $$(A \vec v)^T (A \vec v) = 0$$ $$\langle A \vec v, A \vec v \rangle = \Vert A\vec v \Vert ^2 = 0$$
- Thus, it is clear that $A \vec v = 0$, so $\vec v \in \text{Null}(A)$
- That is, $\text{Null}(A^T A) \subseteq \text{Null}(A)$
- Consider an arbitrary vector $\vec v’ \in \text{Null}(A)$– pre-multiplying by $A^T$ we have that… $$A \vec v’ = \vec 0$$ $$A^T A \vec v’ = \vec 0$$
- Therefore $\vec v’ \in \text{Null}(A^T A)$
- That is, $\text{Null}(A) \subseteq \text{Null}(A^T A)$
- Combining this with the prior statement, we find our desired $\text{Null}(A) = \text{Null}(A^T A)$