Linear Least Squares Problems

Definition

Given a linear system of equations

\[ \mathbf{Ax = b}, \]

where \(\mathbf{A}\in \mathbb{R}^{m \times n}, \ \text{where } \ m > n\), \(\mathbf{x}\in \mathbb{R}^{n \times 1}\) and \(\mathbf{b} \in \mathbb{R}^{m \times 1}\).

Given that \(m > n\), we are not expected to be able to reproduce the \(m\)-vector \(\mathbf{b}\) with only \(n\) parameters in \(\mathbf{x}\). This is an Overdetermined System (numerical analysis).

Instead, we minimize the distance between the left and right sides of the equation, ie. we minimize some norm of the residual vector \(\mathbf{r = b - Ax}\) as a function of \(\mathbf{x}\). Any norm can be used, but it is strongly preferred that we use the Euclidean or 2-norm.

Use of the 2-norm gives the method of least squares its name: the solution is the vector \(\mathbf{x}\) that minimizes the sum of squares of differences between the components of the left and right sides of the linear system. To reflect this inexactedness, we write a linear least squares problem as

\[ \mathbf{Ax} \cong \mathbf{b}. \]

A solution to a linear least squares problem is unique if, and only if, \(\mathbf{A}\) has full column rank. ie. \(\text{rank}(\mathbf{A}) = n\). If \(\text{rank}(\mathbf{A}) < n\), then \(\mathbf{A}\) is considered to be rank-deficient, and although the solution must exist, the solution is not unique.

---

Solving Least Squares with Normal Equations

We wish to minimize the squared Euclidean norm of the residual vector \(\mathbf{r = b-Ax}\). Denoting this objective function \(\phi:\mathbb{R}^{n} \to \mathbb{R}\), we have

\[ \phi(\mathbf{x}) = ||\mathbf{r}||_{2}^{2} = \mathbf{r}^{\top}\mathbf{r} = (\mathbf{b-Ax})^{\top}(\mathbf{b - Ax}) = \mathbf{b^{\top}b} - 2\mathbf{x}^{\top}\mathbf{A}^{\top}\mathbf{b} + \mathbf{x}^{\top}\mathbf{A}^{\top}\mathbf{Ax}. \]

A necessary condition for a minimum is that \(\mathbf{x}\) be a critical point of \(\phi\), where the gradient vector \(\nabla \phi(\mathbf{x}) = 0\). Thus,

\[ \mathbf{o} = \nabla \phi(\mathbf{x}) = 2\mathbf{A}^{\top}\mathbf{Ax} - 2\mathbf{A^{\top}b}, \]

so any minimizer \(\mathbf{x}\) for \(\phi\) must satisfy the following linear equation:

\[ \mathbf{A}^{\top}\mathbf{Ax} = \mathbf{A}^{\top}\mathbf{b}. \]

This linear system is often called the system of normal equations.

---

Solving Least Squares with Orthogonality

Recall that for two vectors \(\mathbf{v}_{1}, \mathbf{v}_{2} \in \mathbb{R}^{m}\),

\[ \mathbf{v}_{1}^{\top}\mathbf{v}_{2} = ||\mathbf{v}_{1}||_{2} \ ||\mathbf{v}_{2}||_{2} \ \cos(\theta) \]

where \(\theta\) is the angle between \(\mathbf{v}_{1}\) and \(\mathbf{v}_{2}\). Thus, \(\mathbf{v}_{1}\) and \(\mathbf{v}_{2}\) are said to be orthogonal if \(\mathbf{v}_{1}^{\top}\mathbf{v}_{2} = 0\).

For a least squares problem \(\mathbf{Ax \cong b}\), with \(m > n\), the \(m\)-vector \(\mathbf{b}\) generally doesn't lie in \(\text{span}(\mathbf{A})\), a subspace of at most dimension \(n\). The vector \(\mathbf{y=Ax} \in \text{span}(\mathbf{A})\) closest to \(\mathbf{b}\) in the Euclidean norm occurs when the residual vector \(\mathbf{r = b -Ax}\) is orthogonal to \(\text{span}(\mathbf{A})\).

Thus, for the least squares solution \(\mathbf{x}\), the residual vector \(\mathbf{r = b-Ax}\) must be orthogonal to all column vectors in \(\mathbf{A}\),

\[ \mathbf{o}= \mathbf{A}^{\top}\mathbf{r} = \mathbf{A}^{\top}(\mathbf{b-Ax}), \]

or

\[ \mathbf{A}^{\top}\mathbf{Ax} = \mathbf{A}^{\top}\mathbf{b}, \]

which is the same system of normal equations derived from the calculus way.