Least squares approximation (deriving the Pseudo Inverse)

Video

#Math #Linear_Algebra

Table of Contents:

Derivation of the Pseudo Inverse using the Least Squares Approximation

Introduction to the Problem

• We have a matrix equation $\text{Ax}=\text{b}$, where $\text{A}$ is an $n\times k$ matrix, $\text{x}$ is a vector in ${\mathbb{R}}^k$, and $\text{b}$ is a vector in ${\mathbb{R}}^n$.

• The problem arises when there is no solution for $\text{Ax}=\text{b}$, which happens when $\text{b}$ is not a linear combination of the column vectors of $\text{A}$, i.e., $\text{b}$ is not in the column space of $\text{A}$.

Step 1: Introducing Least Squares Approximation (Minimizing the Distance)

To find an approximate solution, we introduce the concept of the least squares approximation:

• The goal is to find a vector ${\text{x}}^{\ast }$ such that ${\text{Ax}}^{\ast }$ is as close as possible to $\text{b}$.
• This closeness is quantified by minimizing the length of the vector $\text{b}-{\text{Ax}}^{\ast }$.
• The minimization process involves finding the vector ${\text{x}}^{\ast }$ that minimizes the squared length of $\text{b}-{\text{Ax}}^{\ast }$.
• Mathematically, this is expressed as minimizing $\parallel \text{b}-{\text{Ax}}^{\ast }{\parallel }^2$, which is the sum of the squared differences of the elements in the vectors $\text{b}$ and ${\text{Ax}}^{\ast }$.

Step 2: Projection onto Column Space

• The closest vector to $\text{b}$ in the column space of $\text{A}$ is the projection of $\text{b}$ onto this space.
• We seek ${\text{x}}^{\ast }$ such that ${\text{Ax}}^{\ast }$ is this projection, which will minimize the distance between ${\text{Ax}}^{\ast }$ and $\text{b}$.

Question: Is there an easier way to find ${\text{x}}^{\ast }$ without using the ${\text{proj}}_{\text{Col}(A)}(\mathbf{b})$?
Answer: Yes, there is! We can use the Orthogonal Complement and Null Space

Step 3: Orthogonal Complement and Null Space

• It is shown that ${\text{Ax}}^{\ast }-\text{b}$ is orthogonal to the column space of $\text{A}$.

• Therefore, ${\text{Ax}}^{\ast }-\text{b}$ is a member of the orthogonal complement of the column space of $\text{A}$, which is also the null space of ${\text{A}}^T$.

Step 4: Deriving the Least Squares Solution

• Multiplying both sides of the equation ${\text{Ax}}^{\ast }-\text{b}=0$ by ${\text{A}}^T$ gives ${\text{A}}^T\text{A}{\text{x}}^{\ast }-{\text{A}}^T\text{b}=0$.
• Solving this for ${\text{x}}^{\ast }$ gives the least squares solution. The equation ${\text{A}}^T\text{A}{\text{x}}^{\ast }={\text{A}}^T\text{b}$ always has a solution, which is the best approximation for the original problem.

Conclusion

• The least squares solution ${\text{x}}^{\ast }$ is the best possible approximation in the least squares sense for the equation $\text{Ax}=\text{b}$ when there is no exact solution.
• This approach minimizes the error in the approximation, making ${\text{Ax}}^{\ast }$ as close as possible to $\text{b}$.

↩️ Go Back