Least Squares

The least squares line is the line among a set of data points that minimizes the sum of the squares of the vertical distances from each data point to the line.

Suppose we represent the problem of finding this least squares solution as a matrix system with some \(m \times n\) matrix \(A\) and \(\mathbf{b} \in \mathbb{R}^m\). Then, we want to solve:

\begin{align} A\mathbf{x} = \mathbf{b} \notag \end{align}

for some vector \(\mathbf{x}\). However, it is highly likely that this system is inconsistent (e.g. no lines exactly passes through all the data points). But is there a point in \(\text{Col }A\) that is closest to \(\mathbf{b}\)?

This is just the projection of \(\mathbf{b}\) on \(\text{Col }A\), denoted as \(\mathbf{\hat{b}}\). Then, we can find some \(\mathbf{\hat{x}}\) such that \(A\mathbf{\hat{x}} = \mathbf{\hat{b}}\).

In other words, we want to find \(\mathbf{\hat{x}}\) such that \(\left| \mathbf{b} - A\mathbf{\hat{x}} \right|\) is as small as possible. To do this, note that \(\mathbf{b} -A\mathbf{\hat{x}}\) is orthogonal to \(\text{Col }A\), so \(\mathbf{b} - A\mathbf{\hat{x}}\) is in \(\text{Nul }A^T\), so:

\begin{align} A^T\left(\mathbf{b} - A\mathbf{\hat{x}}\right) = 0 \notag \end{align}

Then, distributing, we have:

\begin{align} A^TA\mathbf{\hat{x}} = A^T\mathbf{b} \notag \end{align}

Since \(A^TA\) is a square matrix, then \(\mathbf{\hat{x}}\) has a solution if it is invertible:

\begin{align} \boxed{\mathbf{\hat{x}} = \left(A^TA\right)^{-1}A^T\mathbf{b}} \end{align}

We now want to find the least squares line of the form \(y = B_0 + B_1x\) for a set of data points \(\left(x_i,y_i\right)\). We can for each point solve the system as follows:

\begin{align} B_0 + B_1x_1 &= y_1 \notag \\ B_0 + B_1x_2 &= y_2 \notag \\ &\vdots \notag \\ B_0 + B_1x_n &= y_n \notag \end{align}

Writing this as a matrix equation, we have:

\begin{align} \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_n \end{bmatrix} \begin{bmatrix} B_0 \\ B_1 \end{bmatrix} &= \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} \notag \\ \notag \\ XB &= Y \end{align}

where \(X\) is known as the design matrix.

This system, however, is likely inconsistent. Therefore, we can use least squares to choose \(B\) such that \(XB\) is the best approximation for \(Y\). Using (1), then, we know that:

\begin{align} B = \left(X^TX\right)^{-1}X^TY \end{align}