Least Squares for Overdetermined Systems

Hello! Welcome to the first lesson of our new module, "Applications in Data Analysis."

In our previous modules, especially the one on Singular Value Decomposition, we developed a powerful toolkit for understanding matrices. We saw how to find "best" solutions to systems using the pseudoinverse and how to find the "best" low-rank approximations of data. The common theme was finding optimal answers when perfect ones are not available.

Today, we will apply this thinking to one of the most fundamental problems in data science and machine learning. Our learning outcome is to formulate the least squares problem for overdetermined linear systems. This is the mathematical engine behind linear regression, a technique used to model relationships in data.

1. The Problem: Fitting a Line to Data

Imagine you are running an experiment and you collect a set of data points. You plot them and they seem to follow a linear trend, but they don't fall perfectly on a single line due to measurement noise or other real-world factors. How do you find the single "best" line that represents the underlying trend in your data?

This is the classic data-fitting problem. We want to find the parameters of a line (e.g., slope and intercept) that minimize the total error between the line and the actual data points.

The following video provides an excellent introduction to this idea, showing how a simple data-fitting scenario naturally leads to a problem in linear algebra.

Least squares using matrices | Lecture 26 | Matrix Algebra for Engineers

In this video, 'Least squares using matrices' by Jeffrey Chasnov, you'll see how the simple goal of drawing a best-fit line through noisy data is translated into a system of linear equations.

Please watch from the beginning to 6:21. Pay close attention to how the data points (x_i, y_i) and the line equation y = eta_0 + eta_1 x are used to build a matrix equation.

2. Formulating the Overdetermined System

As the video explained, if we assume our data points $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})$ should ideally satisfy the line equation $y = β_{0} + β_{1} x$ , we can write a separate equation for each point:

β_{0} + β_{1} x_{1} β_{0} + β_{1} x_{2} β_{0} + β_{1} x_{n} = y_{1} = y_{2} ⋮ = y_{n}

This is a system of $n$ linear equations with only two unknowns, $β_{0}$ and $β_{1}$ . If we have more than two data points ( $n > 2$ ), which is almost always the case, this system is overdetermined.

We can express this system in the familiar matrix form $A x = b$ :

11 ⋮ 1 x_{1} x_{2} ⋮ x_{n} [β_{0} β_{1}] = y_{1} y_{2} ⋮ y_{n}

Here:

$A$ is the $n \times 2$ matrix containing a column of ones (for the intercept) and a column of the $x$ values. In machine learning, this is often called the design matrix.
$x$ is the $2 \times 1$ vector of the unknown parameters we want to find (here, $β_{0}$ and $β_{1}$ ).
$b$ is the $n \times 1$ vector of the observed output values $y_{i}$ .

Because the data points aren't perfectly collinear, there is no single vector $x$ that can exactly satisfy this equation. In the language of linear algebra, the vector of observations $b$ is not in the column space of the matrix $A$ .

3. The Least Squares Criterion: Defining the "Best" Fit

If we can't find an $x$ that makes $A x - b$ equal to the zero vector, our goal becomes to find an $x^$ (the "hat" denotes an estimate) that makes the error vector $e = b - A x$ as small as possible.

How do we measure the "size" of the error vector? We use its norm (length). The least squares criterion states that the best solution $x^$ is the one that minimizes the squared Euclidean norm of the error vector:

Minimize ∥ b - A x ∥^{2}

The squared norm is used for both statistical reasons and because it avoids square roots, making the math much cleaner. It is simply the sum of the squared errors for each data point:

∥ b - A x ∥^{2} = i = 1 \sum n (y_{i} - (β_{0} + β_{1} x_{i}))^{2}

This is the core formulation of the least squares problem. This framework is central to your goal of studying deep learning, where it's known as minimizing a loss function through empirical risk minimization.

Ordinary Least Squares Linear Regression

This document from Princeton on 'Ordinary Least Squares Linear Regression' formalizes this concept from a machine learning perspective. It's a great way to see how the linear algebra you're learning is expressed in a data science context.

Read the first two pages and the beginning of the third, ending at the formula for L(w) (Eq. 12). Notice the different notation: 'w' (weights) instead of \mathbf{x}, and 'X' instead of A. This is standard in machine learning literature. Focus on how the problem is framed as minimizing a sum-of-squares loss function.

4. The Geometric Viewpoint: Projection

We can also visualize this problem geometrically. The set of all possible vectors $A x$ forms the column space of $A$ , which is a subspace (in our line-fitting example, a plane in $R^{n}$ ). The observation vector $b$ lies outside this subspace.

The problem of finding the $x^$ that minimizes $∥ b - A x ∥$ is equivalent to finding the vector $A x^$ in the column space of $A$ that is closest to $b$ . As we learned in a previous module, this closest vector is the orthogonal projection of $b$ onto the column space of $A$ .

Let $p = A x^$ be this projection. The error vector, $e = b - p = b - A x^$ , must be orthogonal to the entire column space of $A$ .

16. Projection Matrices and Least Squares

The legendary Gilbert Strang from MIT provides one of the clearest geometric explanations of this concept.

Watch the segment from 13:25 to 20:07. Professor Strang masterfully explains the two pictures of the least squares problem: the data plot with vertical errors, and the vector space plot showing the projection of \mathbf{b} onto the column space.

5. Deriving the Normal Equations

This geometric insight gives us everything we need to formulate a solvable system.
Since the error vector $b - A x^$ is orthogonal to the column space of $A$ , it must be orthogonal to every column of $A$ .

We can state this condition compactly using the transpose. The columns of $A$ are the rows of $A^{T}$ . For the error vector to be orthogonal to every column of $A$ , its dot product with each must be zero. This is equivalent to:

A^{T} (b - A x^) = 0

Distributing $A^{T}$ , we get:

A^{T} b - A^{T} A x^= 0

Rearranging gives us the celebrated normal equations:

A^{T} A x^= A^{T} b

This is the final formulation of the least squares problem. We started with an inconsistent system $A x = b$ and, by applying the least squares criterion, we derived a new, consistent system for the best-fit parameters $x^$ .

Notice that $A^{T} A$ is a square matrix (in our example, $2 \times 2$ ). If its columns are linearly independent, this matrix is invertible, and we can solve for $x^$ .

Least Squares Problem Formulation Example — This image provides a perfect summary. It starts with an overdetermined system that has no solution and shows the step-by-step formulation of the normal equations to find the least squares solution $\hat{\mathbf{x}}$.

Test your understanding!

You want to fit the model $y = c \cdot t$ (a line through the origin) to the data points $(t = 1, y = 3)$ and $(t = 2, y = 5)$ .

Write down the overdetermined system of equations for the unknown parameter $c$ .
Formulate this as a matrix equation $A x = b$ . What are $A$ , $x$ , and $b$ ?
Write down the normal equations $A^{T} A x^= A^{T} b$ for this specific problem (you don't need to solve it).

Show answer

Plugging the points into the model gives:
- $c \cdot 1 = 3$
- $c \cdot 2 = 5$
The matrix equation is: $[12] [c] = [35]$ So, $A = [12]$ , $x = [c]$ , and $b = [35]$ .
First, compute $A^{T} A$ and $A^{T} b$ :
- $A^{T} A = [12] [12] = [1 \cdot 1 + 2 \cdot 2] = [5]$
- $A^{T} b = [12] [35] = [1 \cdot 3 + 2 \cdot 5] = [13]$
  The normal equation is $A^{T} A x^= A^{T} b$ , which becomes:
  $[5] [c^] = [13]$
  This gives the least squares estimate $c^= 13/5 = 2.6$ .

Conclusion

In this lesson, we have laid the complete groundwork for one of the most practical tools in linear algebra. We saw how a simple, intuitive problem of data fitting leads to an inconsistent system of equations, and we established a clear criterion for finding the "best" possible solution.

Key Takeaways:

Data-fitting problems often lead to overdetermined linear systems $A x = b$ that have no exact solution.
The least squares problem is to find the vector $x^$ that minimizes the squared norm of the error vector, $∥ b - A x ∥^{2}$ .
Geometrically, the solution $A x^$ is the orthogonal projection of $b$ onto the column space of $A$ .
The orthogonality condition leads directly to the normal equations: $A^{T} A x^= A^{T} b$ . This is a new, solvable system for the best-fit parameters $x^$ .

Preview of the Next Lesson:

We have successfully formulated the problem. The next logical step is to solve it. In the next lesson, we will focus on methods to solve the least squares problem, starting with the normal equations we just derived. We will also explore an alternative, more numerically stable method using QR decomposition.

Recommended resources