Projections and Least Squares

The projection of a vector \(\boldsymbol{b} \in \mathbb{R}^m\) onto a subspace \(S\) of \(\mathbb{R}^m\) is the point \(\boldsymbol{p} \in S\) that is closest to \(\boldsymbol{b}\). So we would define the projection as follows:

Let’s first look at where we have a vector in 2D space and we want to project it onto a line. So a subspace of dimension 1 which is spanned by a single basis vector \(\boldsymbol{a}\). So \(S = \{\lambda \boldsymbol{a} : \lambda \in \mathbb{R} \, \boldsymbol{a} \in \mathbb{R}^2\}\) = C(\(\boldsymbol{a}\)). If we visualize this, we can see that the projection of \(\boldsymbol{b}\) onto the line, i.e the point \(\boldsymbol{p}\) that is closest to \(\boldsymbol{b}\) is there where the error vector \(\boldsymbol{e} = \boldsymbol{b} - \boldsymbol{p}\) is orthogonal to the line.

So how do we find the point \(\boldsymbol{p}\) using this information. We can also observe that \(\boldsymbol{p}\) is a scalar multiple of \(\boldsymbol{a}\), i.e \(\boldsymbol{p} = \lambda \boldsymbol{a}\). So we can write the error vector \(\boldsymbol{e}\) as \(\boldsymbol{e} = \boldsymbol{b} - \lambda \boldsymbol{a}\). So we are looking for some \(\lambda\) that minimizes the error vector. In other words we want to minimize the following:

So we get some function \(g(\lambda)\) that we want to minimize, the values of \(||\boldsymbol{b}||^2\) and \(||\boldsymbol{a}||^2\) and \(\boldsymbol{b}^T\boldsymbol{a}\) are all constants. To minimize this function we can take the derivative with respect to \(\lambda\) and set it to 0. This leads to the following:

So we have found the formula for \(\lambda\) which is the scalar multiple of \(\boldsymbol{a}\) that gives us the projection of \(\boldsymbol{b}\) onto the line. Now we just need to put it back together to get the projection:

We prefer to have the \(\boldsymbol{b}\) term seperated and we can move around the multiplication of. So the nominator is then the outer product of \(\boldsymbol{a}\) with itself and the denominator is the inner product of \(\boldsymbol{a}\) with itself. This then gives us the final formula for the projection of \(\boldsymbol{b}\) onto the line spanned by \(\boldsymbol{a}\).

Let’s now check to see if our initial observation that the error vector \(\boldsymbol{e} = \boldsymbol{b} - \boldsymbol{p}\) is orthogonal to the line is correct:

Projections in Higher Dimensions

In the general case, we want to project a vector \(\boldsymbol{b} \in \mathbb{R}^m\) onto a subspace \(S \subseteq \mathbb{R}^m\) of dimension \(n\), where \(n \leq m\). This subspace \(S\) is spanned by \(n\) linearly independent vectors, which we organize as the columns of a matrix \(\boldsymbol{A} \in \mathbb{R}^{m \times n}\). The column space of \(\boldsymbol{A}\) is then the subspace \(S=C(\boldsymbol{A})\). Our goal is to then find \(\text{proj}_S(\boldsymbol{b}) = \boldsymbol{p}\), the projection of \(\boldsymbol{b}\) onto \(S\), such that \(\boldsymbol{p}\) is the closest point in \(S\) to \(\boldsymbol{b}\).

Any vector \(\boldsymbol{p}\) in the subspace \(S\) can be expressed as a linear combination of the columns of \(\boldsymbol{A}\). If we store the coefficients of this linear combination in a vector \(\hat{\boldsymbol{x}} \in \mathbb{R}^n\), we can write the projection as:

Just like in the 1D case, we want to minimize the error vector. This is then equivalent to finding \(\hat{\boldsymbol{x}}\) such that the error vector \(\boldsymbol{e} = \boldsymbol{b} - \boldsymbol{p}\) is minimized. Specifically, we minimize the squared norm of the error:

By taking the square norm, which is fine as the norm is always positive, we can simplify the expression to:

This gives us a function \(g(\hat{\boldsymbol{x}})\) very similar to the 1D case that we want to minimize. To minimize this function with respect to \(\hat{\boldsymbol{x}}\), we compute the gradient with respect to \(\hat{\boldsymbol{x}}\) and set it to zero:

After further simplifying the above we get the so called normal equations. The normal equations are a set of very important equations in linear algebra and computer science. We will be revisiting them in the context of solving the least squares problem further down the line.

In the case where we add \(n=1\) so a subspace of dimension 1 we could rewrite the formula to be:

So we can see that the two formulas match up.

Because we know that the columns of \(\boldsymbol{A}\) are linearly independent as they form a basis for the subspace \(S\), the matrix \(\boldsymbol{A}^T\boldsymbol{A}\) is square and invertible. The fact that is square is obvious, more specifically it is a square matrix of size \(n \times n\) where \(n\) is the dimension of the subspace \(S\). Because the rank of \(\boldsymbol{A}\) is \(n\), the rank of \(\boldsymbol{A}^T\boldsymbol{A}\) is also \(n\) and therefore it is now full rank and invertible. In the general case, the matrix \(\boldsymbol{A}\) is not square and therefore not invertible. So if left multiply the normal equation with the inverse we can solve for \(\hat{\boldsymbol{x}}\):

Substituting \(\hat{\boldsymbol{x}}\) back into \(\boldsymbol{p} = \boldsymbol{A}\hat{\boldsymbol{x}}\), we obtain the projection of \(\boldsymbol{b}\) onto \(S\):

This is the general formula for the projection of a vector onto a subspace. However, we would like to simplify the formula slightly in the general case. If we set the matrix \(\boldsymbol{P} = \boldsymbol{A}(\boldsymbol{A}^T\boldsymbol{A})^{-1}\boldsymbol{A}^T\) we get the so called projection matrix for the subspace \(S\). It allows us to write the projection concisely as:

We know that matrices define linear transformations. Therefore the projection matrix \(\boldsymbol{P}\) defines a linear transformation that projects any vector onto the subspace \(S\). Or more formally the transformation is defined as:

Where the vector \(\boldsymbol{b}\) is of dimension \(m\) and the subspace and therefore the projection is of dimension \(n\). The projection transformation also has some important properties. The first oen being that a projection of a projection shouldn’t change the vector. This is called the idempotent property:

So with the projection matrix we should have \(\boldsymbol{P}^2b = \boldsymbol{P}b\) which is the same as \(\boldsymbol{P}^2 = \boldsymbol{P}\).

The projection onto the orthogonal complement of \(S\) is defined as:

Orthogonal Matrices

An orthogonal matrix is a matrix whose columns \(\boldsymbol{q}_1, \boldsymbol{q}_2, \ldots, \boldsymbol{q}_n\) form an orthonormal set of vectors or basis. A set of vectors is orthonormal if the following two properties hold:

1. Each vector has unit length, meaning \(||\boldsymbol{q}_i|| = 1\).
2. They are all orthogonal to each other, meaning \(\boldsymbol{q}_i^T \boldsymbol{q}_j = 0\) for \(i \neq j\) the dot products where \(i = j\) are of course 1 as this is then the same as the length of the vector squared. This is also why they form a basis, as we have seen that if the vectors are orthogonal to each other they are linearly independent.

An orthogonal matrix \(\boldsymbol{Q} \in \mathbb{R}^{m \times n}\) has orthonormal columns then it has some very nice properties. The first one is that the transpose of the matrix times the matrix is the identity matrix:

The reason for this is quiet simple if you think of the matrix multiplication as taking the dot product of the columns of the matrix. If we have the orthogonal matrix \(\boldsymbol{Q} \in \mathbb{R}^{m \times n}\) with the orthonormal columns \(\boldsymbol{q}_1, \boldsymbol{q}_2, \ldots, \boldsymbol{q}_n\). When we compute \(\boldsymbol{Q}^T \boldsymbol{Q}\), the \((i, j)\)-entry of the resulting matrix is:

This gives us two cases:

• If \(i = j\), \(\boldsymbol{q}_i^T \boldsymbol{q}_j = ||\boldsymbol{q}_i||^2 = 1\). These values will be along the diagonal of the resulting matrix.
• If \(i \neq j\), \(\boldsymbol{q}_i^T \boldsymbol{q}_j = 0\), since the columns of \(\boldsymbol{Q}\) are orthogonal.

This is very easily visualized if we take the first standard basis vectors from \(\mathbb{R}^3\) and put them into a matrix:

Orthogonal matrices also have the nice property that if they are square so \(m = n\) then the following also holds:

Which then means that \(\boldsymbol{Q}\) is invertible, and its inverse is given by:

Orthogonal matrices also have the nice property of preserving the norm of a vector. So if we have an orthogonal matrix \(\boldsymbol{Q} \in \mathbb{R}^{n \times n}\) and let \(\boldsymbol{x} \in \mathbb{R}^n\) be any vector. So if we consider the transformed vector \(\boldsymbol{y} = \boldsymbol{Q} \boldsymbol{x}\). Then the norm of \(\boldsymbol{y}\) is:

Using the associative property of matrix multiplication and the fact that \(\boldsymbol{Q}^T \boldsymbol{Q} = \boldsymbol{I}\) (since \(\boldsymbol{Q}\) is orthogonal), we get:

Thus, the norm of a vector is preserved under multiplication by an orthogonal matrix. An orthogonal matrix also preserves the inner product of two vectors. The inner product of two vectors \(\boldsymbol{x}, \boldsymbol{z} \in \mathbb{R}^n\) is defined as:

Now consider the transformed vectors \(\boldsymbol{y} = \boldsymbol{Q} \boldsymbol{x}\) and \(\boldsymbol{w} = \boldsymbol{Q} \boldsymbol{z}\). The inner product of \(\boldsymbol{y}\) and \(\boldsymbol{w}\) is:

Using the associative property of matrix multiplication and the fact that \(\boldsymbol{Q}^T \boldsymbol{Q} = \boldsymbol{I}\), we have:

Thus, the inner product of two vectors is also preserved under multiplication by an orthogonal matrix. These two properties give us an important insight into linear transformations that are defined by orthogonal matrices. The geometric interpretation is that Orthogonal matrices represent rigid transformations of space, such as rotations and reflections. These transformations do not distort the lengths of vectors or the angles between them, which is why both the norm and the inner product remain unchanged.

Projections with Orthogonal Matrices

Suppose we are given \(\boldsymbol{Q} \in \mathbb{R}^{m \times n}\) that has orthonormal columns. We now want to project a vector \(\boldsymbol{b} \in \mathbb{R}^m\) onto subspace spanned by the columns of \(\boldsymbol{Q}\), so \(C(\boldsymbol{Q})\). We have already seen that the projection of \(\boldsymbol{b}\) onto \(C(\boldsymbol{Q})\) is given by:

Which becomes the normal equations. However, since \(\boldsymbol{Q}\) has orthonormal columns, we can simplify the normal equations and the projection matrix.

The projection matrix for \(C(\boldsymbol{Q})\) is then simply:

Least Squares

The least squares problem is a cornerstone of linear algebra and optimization, with significant applications in data science, machine learning, and statistics. In machine learning, it often appears as an introductory problem under the name linear regression. Its goal is to find the best approximation of a set of observations by minimizing the error between observed outcomes and predicted values. This technique is widely used in practical applications, such as predicting house prices based on so called features like size, age, or location.

Suppose we are tasked with predicting house prices based on the size of the house. We are given a set of data points \((t_1, b_1), (t_2, b_2), \ldots, (t_n, b_n)\), where:

• \(t_k\): Is the measured size of the house (independent variable, or feature) for the \(k\)-th data point.
• \(b_k\): the actual observed price of the house (dependent variable, or outcome) for the \(k\)-th data point.

If we then assume that there is a linear relationship between the size of the house and its price. So the price of house is dependent on the size of the house. The linear part means that the relationship can be expressed as a line. This is why the problem is also often referred to as “fitting a line to the data”.

So there is some linear function that given the size of the house can predict the price of the house. We aim to find this function. We know that a linear function is defined as follows:

Where \(x\) is our input feature, \(y\) is the output and \(a_0\) and \(a_1\) are the parameters of the function. In our case \(x\) is the size of the house and \(y\) is the price of the house. So we want to find the parameters \(a_0\) and \(a_1\) such that the predicted price \(\hat{b}_k\) is given by:

where the predicted price \(\hat{b}_k\) is as close as possible to the observed price \(b_k\). The difference between the observed price \(b_k\) and the predicted price \(\hat{b}_k\) is called the error for the \(k\)-th observation. To find the best-fitting line, we minimize the sum of squared errors across all observations:

This least squares formulation has numerous practical applications for modeling any linear relationship between variables. As we are doing linear algebra let us represent the data in terms of matrices and vectors. So we define the following:

• The vector containing the observed outcomes (house prices) is \(\boldsymbol{b} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}\).
• The vector of coefficients (parameters to be determined) is \(\boldsymbol{x} = \begin{bmatrix} a_0 \\ a_1 \end{bmatrix}\).
• The matrix containing the features is \(\boldsymbol{A} = \begin{bmatrix} 1 & t_1 \\ 1 & t_2 \\ \vdots & \vdots \\ 1 & t_n \end{bmatrix}\).

The reason for the column of ones is that when we multiply the matrix \(\boldsymbol{A}\) with the vector \(\boldsymbol{x}\) we want to just add the term \(a_0\) to the term \(a_1 t_k\). Our predicted outcomes for all inputs are then given by:

The error vector, representing the difference between observed outcomes and predicted outcomes can then be written as:

The least squares problem is then to find \(\boldsymbol{x}\) that minimizes the squared norm of the error vector:

This matrix formulation generalizes easily to cases with multiple features. For example, if we also have the age of the house as an additional feature, the matrix \(\boldsymbol{A}\) would include an additional column corresponding to this feature.

More generally, for a given matrix \(\boldsymbol{A} \in \mathbb{R}^{m \times n}\) (where \(m\) is the number of observations and \(n\) is the number of features plus one for the intercept) and a vector \(\boldsymbol{b} \in \mathbb{R}^m\), we aim to find the vector \(\boldsymbol{x} \in \mathbb{R}^n\) that minimizes:

From the above formulation we can see that the when we are trying to minimize the squared norm of the error we are actually looking for the projection of \(\boldsymbol{b}\) onto the column space of \(\boldsymbol{A}\):

This actually makes sense as we are given some vector and we are trying to create it is a linear combination of the columns of \(\boldsymbol{A}\).

Because we have now noticed that we are looking for the projection of \(\boldsymbol{b}\) onto the column space of \(\boldsymbol{A}\) we can use our knowledge of projections to solve the least squares problem. We know that the solution to the least squares problem is derived using the normal equations. By setting the gradient of the squared error to zero, we obtain:

If we then assume that the columns of \(\boldsymbol{A}\) are linearly independent, we know that \(\boldsymbol{A}^T\boldsymbol{A}\) is invertible and that we can solve for \(\boldsymbol{x}\):

To solve the least squares problem, the columns of \(\boldsymbol{A}\) must be linearly independent. Linear independence ensures that \(\boldsymbol{A}^T\boldsymbol{A}\) is invertible, which is crucial for deriving the solution. For example, if all the feature values \(t_k\) are identical (e.g., \(t_i = t_j\) for all \(i \neq j\)), then the column would be a multiple of the first column and the columns of \(\boldsymbol{A}\) would not span a sufficiently large space, making it impossible to uniquely determine the coefficients \(\boldsymbol{x}\). Linear independence of the columns of \(\boldsymbol{A}\) ensures that the data provides enough information to determine a unique solution.

Fitting a Parabola

add extra column where we have t^2