Least Squares Problems

• categories: Linear algebra, Real Analysis, Method

Definition
The least squares problem seeks to minimize the residual error $\Vert Ax-b{\Vert }_2$, where:

• $A\in {\mathbb{R}}^{m\times n}$ is a matrix with $m\ge n$,
• $b\in {\mathbb{R}}^m$ is a given vector,
• $x\in {\mathbb{R}}^n$ is the unknown vector to solve for.

This arises when the system $Ax=b$ is overdetermined (more equations than unknowns), and no exact solution exists. The solution is:
$x^{\ast }={\text{argmin}}_{x\in {\mathbb{R}}^n}\Vert Ax-b{\Vert }_2.$ Intuition
The least squares solution minimizes the Euclidean distance between $b$ and the column space of $A$. It projects $b$ onto the subspace spanned by the columns of $A$, yielding the best approximation of $b$ that lies in the range of $A$.

Key Properties

1. Normal Equations:
   The least squares solution satisfies:
   $A^{T}Ax=A^{T}b.$

2. Existence and Uniqueness:

   • A unique solution exists if $A^{T}A$ is invertible (i.e., $A$ has full column rank).
   • If $A$ is not full rank, the solution is not unique, and the pseudoinverse is used.

3. Orthogonality Condition:
   The residual $r=b-A{x}^{\ast }$ is orthogonal to the column space of $A$:
   $A^{T}r=0.$
   Methods to Solve

4. QR factorization:

   • Compute $A=QR$, where $Q$ is orthogonal and $R$ is upper triangular. Solve:
     $Rx=Q^{T}b.$

5. Normal Equations:

   • Solve $A^{T}Ax=A^{T}b$ directly.
   • This method is computationally less stable compared to QR or SVD.

6. Singular Value Decomposition (SVD):

   • Decompose $A=U\Sigma V^T$, where $\Sigma$ is diagonal. Solve using:
     $x=V{\Sigma }^{+}{U}^{T}b,$
     where ${\Sigma }^{+}$ is the pseudoinverse of $\Sigma$.

7. Iterative Methods:

   • For large systems, iterative solvers like Stochastic Gradient Descent (SGD) or conjugate gradient are used.

8. Nearly Singular Matrix:

   • Use Regularization to improve the stability

Applications

1. Data Fitting:

   • Fit a model to data points by minimizing the sum of squared errors (e.g., linear regression).

2. Signal processing:

   • Denoise signals or approximate functions using least squares.

3. Control Systems:

   • Estimate system parameters in system identification.

4. Computer Vision:

   • Solve problems like camera calibration and 3D reconstruction.

5. Optimization:

   • Forms the basis for solving constrained optimization problems (e.g., quadratic programming).

Examples

1. Simple Linear Regression:
   Fit a line $y=mx+c$ to data points $(x_i,y_i)$ by solving the least squares problem:
   $A=\left[\begin{array}{cc}{x}_1& 1\\ x_2& 1\\ ⋮& ⋮\\ x_n& 1\end{array}\right],b=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right].$
   Solve for $x=\left[\begin{array}{c}m\\ c\end{array}\right]$.

2. Overdetermined System:
   Solve $Ax=b$ where:
   $A=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right],b=\left[\begin{array}{c}6\\ 0\\ 0\end{array}\right].$
   Using the normal equations:
   $A^{T}A=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right],A^{T}b=\left[\begin{array}{c}6\\ 6\end{array}\right].$
   Solve $A^{T}Ax=A^{T}b$ to find $x$.