Skip to main content

Least Squares Method

  • Understand the least squares method.
  • Learn how to solve overdetermined systems.
  • Derive the least squares solution mathematically.
  • Apply the method to regression and optimization problems.

Definition of Least Squares

The **least squares method** is a technique used to find the best approximation to an overdetermined system (more equations than unknowns).

For a system \( A\mathbf{x} = \mathbf{b} \), where \( A \) is \( m \times n \) with \( m > n \), an exact solution may not exist. The least squares method finds \( \mathbf{x} \) that minimizes:

\[ \| A\mathbf{x} - \mathbf{b} \| \]

Derivation of Least Squares Solution

To minimize \( \| A\mathbf{x} - \mathbf{b} \|^2 \), differentiate with respect to \( \mathbf{x} \) and set the derivative to zero:

\[ A^T A \mathbf{x} = A^T \mathbf{b} \]

This equation, called the **normal equation**, gives the least squares solution:

\[ \mathbf{x} = (A^T A)^{-1} A^T \mathbf{b} \]

Proof

We define the error function:

\[ E(\mathbf{x}) = \| A\mathbf{x} - \mathbf{b} \|^2 \]

Taking the derivative:

\[ \frac{d}{d\mathbf{x}} (A\mathbf{x} - \mathbf{b})^T (A\mathbf{x} - \mathbf{b}) = 2 A^T (A\mathbf{x} - \mathbf{b}) = 0 \]

Solving for \( \mathbf{x} \), we obtain:

\[ A^T A \mathbf{x} = A^T \mathbf{b} \]

Solving Overdetermined Systems

In an overdetermined system \( A\mathbf{x} = \mathbf{b} \), the least squares solution is the vector \( \mathbf{x} \) that minimizes the residual \( \mathbf{r} = A\mathbf{x} - \mathbf{b} \).

Applications of Least Squares

  • Linear Regression: Finding the best-fit line in data analysis.
  • Optimization: Approximating solutions when exact ones are infeasible.
  • Signal Processing: Noise reduction and signal reconstruction.

Examples

Example 1: Solve the overdetermined system using least squares:

\[ A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 2 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 4 \\ 2 \\ 6 \end{bmatrix} \]

Step 1: Compute \( A^T A \) and \( A^T \mathbf{b} \):

\[ A^T A = \begin{bmatrix} 3 & 2 \\ 2 & 6 \end{bmatrix} \] \[ A^T \mathbf{b} = \begin{bmatrix} 12 \\ 24 \end{bmatrix} \]

Step 2: Solve \( A^T A \mathbf{x} = A^T \mathbf{b} \):

\[ \begin{bmatrix} 3 & 2 \\ 2 & 6 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 12 \\ 24 \end{bmatrix} \] \[ x_1 = 2, \quad x_2 = 3 \]

Exercises

  • Question 1: Find the least squares solution for:
    • \[ A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \\ 1 & -1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} \]
  • Question 2: Explain why \( A^T A \) must be invertible for a unique least squares solution.
  • Question 3: Derive the normal equation for least squares.

  • Answer 1: \( x_1 = 1.2, x_2 = 0.8 \).
  • Answer 2: \( A^T A \) must be invertible to ensure a unique solution to \( A^T A \mathbf{x} = A^T \mathbf{b} \).
  • Answer 3: The normal equation is derived by minimizing \( \| A\mathbf{x} - \mathbf{b} \|^2 \).

This Week's Best Picks from Amazon

Please see more curated items that we picked from Amazon here .

Popular posts from this blog

LU Decomposition

LU Decomposition: A Step-by-Step Guide LU Decomposition, also known as LU Factorization, is a method of decomposing a square matrix into two triangular matrices: a lower triangular matrix L and an upper triangular matrix U . This is useful for solving linear equations, computing determinants, and inverting matrices efficiently. What is LU Decomposition? LU Decomposition expresses a matrix A as: \[ A = LU \] where: L is a lower triangular matrix with ones on the diagonal. U is an upper triangular matrix. Step-by-Step Process Consider the matrix: \[ A = \begin{bmatrix} 2 & 3 & 1 \\ 4 & 7 & 3 \\ 6 & 18 & 5 \end{bmatrix} \] Step 1: Initialize L as an Identity Matrix Start with an identity matrix for \( L \): \[ L = \begin{bmatrix} 1 & 0 & 0 \\ 0 ...
Read more

Gaussian Elimination: A Step-by-Step Guide

Gaussian Elimination: A Step-by-Step Guide Gaussian Elimination is a systematic method for solving systems of linear equations. It works by transforming a given system into an equivalent one in row echelon form using a sequence of row operations. Once in this form, the system can be solved efficiently using back-substitution . What is Gaussian Elimination? Gaussian elimination consists of two main stages: Forward Elimination: Convert the system into an upper triangular form. Back-Substitution: Solve for unknowns starting from the last equation. Definition of a Pivot A pivot is the first nonzero entry in a row when moving from left to right. Pivots are used to eliminate the elements below them, transforming the system into an upper triangular form. Step-by-Step Example Consider the system of equations: \[ \begin{aligned} 2x + 3y - z &= 5 \\ 4x + y...
Read more

Vector Spaces and Linear Transformation

Vector Spaces and Linear Transformations A vector space is a set of vectors that satisfies specific properties under vector addition and scalar multiplication. Definition of a Vector Space A set \( V \) is called a vector space over a field \( \mathbb{R} \) (real numbers) if it satisfies the following properties: Closure under addition: If \( \mathbf{u}, \mathbf{v} \in V \), then \( \mathbf{u} + \mathbf{v} \in V \). Closure under scalar multiplication: If \( \mathbf{v} \in V \) and \( c \in \mathbb{R} \), then \( c\mathbf{v} \in V \). Associativity: \( (\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w}) \). Commutativity: \( \mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u} \). Existence of a zero vector: There exists a vector \( \mathbf{0} \) such that \( \mathbf{v} + \mathbf{0} = \mathbf{v} \). Existence of additive inverses: For eac...
Read more