Skip to main content

This Week's Best Picks from Amazon

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

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 \).

Popular posts from this blog

Eigenvalues and Eigenvectors

Lesson Objectives ▼ Understand the definition of eigenvalues and eigenvectors. Learn how to compute eigenvalues and eigenvectors. Explore the characteristic equation. Interpret eigenvalues and eigenvectors in transformations. Understand diagonalization and its applications. Lesson Outline ▼ Definition of Eigenvalues and Eigenvectors Characteristic Equation Diagonalization Examples Definition of Eigenvalues and Eigenvectors In a linear transformation, an eigenvector is a nonzero vector that only changes by a scalar factor when the transformation is applied. For a square matrix \( A \), an eigenvector \( \mathbf{v} \) and its corresponding eigenvalue \( \lambda \) satisfy: \[ A\mathbf{v} = \lambda \mathbf{v} \] \( A \) is an \( n \times n \) matrix. \( \mathbf{v} \neq 0 \) is an eigenvector. \( \lambda \) is a scalar eigenvalue. Characteristic Equation ...
Read more

Sets and Binary Operations

Lesson Objectives ▼ Understand the concept of a set and its basic operations. Learn about binary operations and their properties. Explore examples of binary operations. Lesson Outline ▼ Introduction to Sets Basic Set Operations Binary Operations Introduction to Sets A set is a collection of distinct objects, considered as an object in its own right. For example, the set of natural numbers \( \{1, 2, 3, \ldots\} \). Sets can be represented using curly braces, e.g., \( \{a, b, c\} \). Basic Set Operations Union: The union of sets \(A\) and \(B\) is the set of elements that are in \(A\), \(B\), or both. Denoted as \(A \cup B\). Intersection: The intersection of sets \(A\) and \(B\) is the set of elements that are in both \(A\) and \(B\). Denoted as \(A \cap B\). Difference: The difference of sets \(A\) and \(B\) is the set of elements that are in \(A\) but not in \(B\). Denoted as \(A...
Read more

Inner Product Spaces

Lesson Objectives ▼ Understand the definition of inner product spaces. Compute norms, angles, and distances in inner product spaces. Explore the concept of orthogonality. Learn the Gram-Schmidt orthogonalization process. Use inner products for projections and least squares approximation. Lesson Outline ▼ Definition of Inner Product Spaces Norms, Angles, and Orthogonality Gram-Schmidt Orthogonalization Projections and Least Squares Examples Definition of Inner Product Spaces An inner product space is a vector space with an operation called the **inner product**, which measures similarity between vectors. For a real vector space, the inner product of two vectors \( \mathbf{u}, \mathbf{v} \) is: \[ \langle \mathbf{u}, \mathbf{v} \rangle = u_1 v_1 + u_2 v_2 + \dots + u_n v_n \] For a complex vector space, the inner product is: \[ \langle \mathbf{u}, \mathbf{v} \ran...
Read more