How To Find The Least Squares Solution

How to Find the Least Squares Solution: A Comprehensive Guide

Finding the least squares solution is a fundamental problem in numerous fields, from statistics and machine learning to engineering and physics. It arises whenever we try to fit a model to data that isn't perfectly described by the model. This guide provides a comprehensive walkthrough of how to find the least squares solution, covering both the mathematical underpinnings and practical implementation.

Understanding the Problem: Overdetermined Systems

The core issue lies in overdetermined systems. These are systems of equations where we have more equations than unknowns. Consider a simple example: fitting a straight line to a set of data points. Each data point provides an equation, and if we have more than two points, we have an overdetermined system. It's unlikely that a single straight line will pass perfectly through all the points.

The least squares solution finds the line (or more generally, the model) that minimizes the sum of the squared differences between the predicted values and the actual values. These squared differences are often called residuals. Minimizing the sum of squared residuals gives us the "best fit" in a statistically meaningful way.

The Mathematical Foundation: Normal Equations

The most common method for solving the least squares problem involves solving the normal equations. Let's represent our system of equations in matrix form:

Ax = b

Where:

• A is an m x n matrix (m equations, n unknowns), often called the design matrix. Each row represents an equation, and each column represents a variable.
• x is an n x 1 column vector representing the unknowns we want to solve for (e.g., the slope and intercept of the line).
• b is an m x 1 column vector representing the observed values (e.g., the y-coordinates of the data points).

In an overdetermined system (m > n), there's usually no exact solution to Ax = b. The least squares solution aims to find x that minimizes the Euclidean norm of the residual vector:

||Ax - b||²

This minimization problem can be solved using calculus by taking the derivative with respect to x, setting it to zero, and solving the resulting equation. This leads to the normal equations:

AᵀAx = Aᵀb

Where Aᵀ is the transpose of matrix A. If AᵀA is invertible (which it typically is if the columns of A are linearly independent), then the least squares solution is:

x = (AᵀA)⁻¹Aᵀb

This equation provides a direct method for calculating the least squares solution.

A Step-by-Step Example: Linear Regression

Let's illustrate this with a linear regression example. Suppose we have the following data points: (1, 2), (2, 3), (3, 5), (4, 4). We want to fit a line of the form y = mx + c. Our system of equations is:

• m(1) + c = 2
• m(2) + c = 3
• m(3) + c = 5
• m(4) + c = 4

In matrix form:

A =  [[1, 1],
      [2, 1],
      [3, 1],
      [4, 1]]

x = [[m],
     [c]]

b = [[2],
     [3],
     [5],
     [4]]

1. Calculate AᵀA:

AᵀA = [[30, 10],
       [10,  4]]

2. Calculate Aᵀb:

Aᵀb = [[28],
       [14]]

3. Calculate (AᵀA)⁻¹:

Using a matrix inverse calculator (easily found online), we get:

(AᵀA)⁻¹ = [[ 0.2, -0.5],
          [-0.5,  1.5]]

4. Calculate x:

x = (AᵀA)⁻¹Aᵀb = [[ 0.2, -0.5],
                  [-0.5,  1.5]] * [[28],
                                    [14]] = [[0.6],
                                            [7.6]]

Therefore, the least squares solution is m = 0.6 and c = 1.4. Our best-fit line is y = 0.6x + 1.4.

Dealing with Non-Invertible AᵀA

The normal equations method requires that AᵀA is invertible. This isn't always the case. If the columns of A are linearly dependent (meaning one column can be expressed as a linear combination of others), then AᵀA will be singular, and its inverse won't exist. This often indicates redundancy in your model.

In such scenarios, alternative methods are needed, such as:

• Singular Value Decomposition (SVD): SVD provides a robust way to solve the least squares problem even when AᵀA is singular or ill-conditioned (nearly singular). It decomposes A into three matrices: A = UΣVᵀ. The least squares solution can then be obtained using the singular values and vectors. SVD is a computationally more intensive method but offers greater numerical stability.

• QR Decomposition: This method decomposes A into an orthogonal matrix Q and an upper triangular matrix R. Solving the least squares problem with QR decomposition is generally more numerically stable than using the normal equations, especially when dealing with ill-conditioned matrices.

Least Squares in Practice: Software Libraries

Manually calculating the least squares solution, especially for large datasets, is impractical. Fortunately, most programming languages offer powerful linear algebra libraries that handle this efficiently.

• Python (NumPy and SciPy): NumPy provides efficient array operations, and SciPy's linalg module contains functions like lstsq for directly solving the least squares problem using SVD or QR decomposition. This method handles singular matrices gracefully.

• R: R, a statistical computing language, has built-in functions like lm (linear model) that perform linear regression (a type of least squares problem) efficiently.

• MATLAB: MATLAB's \ operator (backslash operator) solves linear systems and efficiently handles least squares problems, automatically selecting appropriate methods based on the matrix properties.

Beyond Linear Regression: Nonlinear Least Squares

The least squares method isn't limited to linear models. It can be extended to nonlinear models using iterative methods like:

• Gauss-Newton method: This iterative method linearizes the nonlinear model at each iteration, applying the linear least squares solution to refine the parameter estimates.

• Levenberg-Marquardt algorithm: A refinement of the Gauss-Newton method, it incorporates a damping parameter that helps to ensure convergence even when the initial parameter estimates are far from the solution.

These iterative methods require initial guesses for the model parameters and iterate until a convergence criterion is met.

Assessing the Goodness of Fit

After finding the least squares solution, it's crucial to assess how well the model fits the data. Common metrics include:

• R-squared (R²): A measure of the proportion of variance in the dependent variable explained by the model. Higher R² values (closer to 1) indicate a better fit.

• Adjusted R-squared: A modified version of R² that adjusts for the number of predictors in the model. It penalizes the inclusion of irrelevant predictors.

• Residual analysis: Examining the residuals (the differences between observed and predicted values) can reveal potential issues with the model, such as non-constant variance or non-normality.

Conclusion

The least squares method is a powerful tool for fitting models to data. Understanding the underlying mathematics and utilizing appropriate software libraries enables efficient and accurate estimation of model parameters. Remember to choose the best method based on the properties of your data and the complexity of your model. Always assess the goodness of fit to ensure your model adequately represents the underlying data and doesn't overfit or underfit. By combining mathematical understanding with practical implementation, you can leverage the least squares method for a wide range of data analysis tasks.