Least Squares & Projections: Theory, Methods & Applications

Key Concepts & Definitions

1. Least Squares Problem

• Definition: Given an overdetermined system $Ax=b$ (where $A\in {\mathbb{R}}^{m\times n}$, $m>n$), the least squares solution minimizes the sum of squared errors (residuals): $$\Vert Ax-b{\Vert }^2=\sum _{i=1}^m(Ax-b{)}_i^2$$
• Interpretation: When $Ax=b$ has no exact solution (inconsistent system), we find the best approximate solution $x^{\ast }$ that minimizes the error.

2. Normal Equations

• The least squares solution $x^{\ast }$ satisfies the normal equations: $$A^{T}Ax=A^{T}b$$
• Derivation: Using calculus (minimizing $\Vert Ax-b{\Vert }^2$) or projection theory.
• Conditions for Solution:
  • If $A^{T}A$ is invertible, then $x^{\ast }=(A^{T}A{)}^{-1}{A}^{T}b$.
  • If $A^{T}A$ is singular, the solution is not unique (infinite solutions exist).

3. Projection onto a Subspace

• Orthogonal Projection: Given a vector $x\in {\mathbb{R}}^n$ and a subspace $W=\text{span}\{A\}$, the projection of $x$ onto $W$ is: $${\text{proj}}_{W}x=A{x}^{\ast }$$ where $x^{\ast }$ is the least squares solution of $Ax=b$ (with $b=x$).
• Projection Matrix: The matrix $P=A(A^{T}A{)}^{-1}{A}^T$ projects any vector $b$ onto the column space of $A$.

4. Least Squares Error

• The minimum error (residual norm) is: $$\Vert A{x}^{\ast }-b\Vert =\sqrt{b^T(I-A(A^{T}A{)}^{-1}{A}^T)b}$$
• Geometric Interpretation: The error vector $b-A{x}^{\ast }$ is orthogonal to the column space of $A$.

---

Methods for Solving Least Squares Problems

1. Direct Method (Normal Equations)

• Steps:
  1. Compute $A^{T}A$ and $A^{T}b$.
  2. Solve $(A^{T}A)x=A^{T}b$ for $x$.
• Advantages:
  • Simple to implement for small systems.
• Disadvantages:
  • Ill-conditioned when $A^{T}A$ is nearly singular.
  • Computationally expensive for large $m$.

2. QR Factorization Method

• Steps:
  1. Factorize $A=QR$, where $Q$ is orthogonal ($Q^{T}Q=I$) and $R$ is upper triangular.
  2. Solve $Rx=Q^{T}b$ (using back substitution).
• Advantages:
  • Numerically stable (avoids squaring condition number).
  • Efficient for large systems.
• Disadvantages:
  • Requires QR decomposition (extra computation).

3. Singular Value Decomposition (SVD) Method

• Steps:
  1. Factorize $A=U\Sigma V^T$, where $U,V$ are orthogonal, $\Sigma$ is diagonal.
  2. The least squares solution is: $$x^{\ast }=V{\Sigma }^{+}{U}^{T}b$$ where ${\Sigma }^{+}$ is the pseudoinverse of $\Sigma$.
• Advantages:
  • Most numerically stable.
  • Handles rank-deficient matrices well.
• Disadvantages:
  • Computationally intensive.

---

Worked Examples

Example 1: Least Squares Solution Using Normal Equations

Problem: Find the least squares solution of $Ax=b$, where $$A=\left[\begin{array}{cc}1& -6\\ 1& -2\\ 1& 1\\ 1& 7\end{array}\right],b=\left[\begin{array}{c}-1\\ 2\\ 1\\ 6\end{array}\right]$$

Solution:

1. Compute $A^{T}A$ and $A^{T}b$: $$A^{T}A=\left[\begin{array}{cccc}1& 1& 1& 1\\ -6& -2& 1& 7\end{array}\right]\left[\begin{array}{cc}1& -6\\ 1& -2\\ 1& 1\\ 1& 7\end{array}\right]=\left[\begin{array}{cc}4& 0\\ 0& 90\end{array}\right]$$ $$A^{T}b=\left[\begin{array}{cccc}1& 1& 1& 1\\ -6& -2& 1& 7\end{array}\right]\left[\begin{array}{c}-1\\ 2\\ 1\\ 6\end{array}\right]=\left[\begin{array}{c}8\\ 15\end{array}\right]$$
2. Solve $(A^{T}A)x=A^{T}b$: $$\left[\begin{array}{cc}4& 0\\ 0& 90\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}8\\ 15\end{array}\right]$$ $$x_1=2,x_2=\frac{15}{90}=\frac{1}{6}$$
3. Least squares solution: $$x^{\ast }=\left[\begin{array}{c}2\\ \frac{1}{6}\end{array}\right]$$
4. Least squares error: $$\Vert A{x}^{\ast }-b\Vert =\sqrt{(-1-2+2+6{)}^2+(2-2+\frac{1}{3}-\frac{7}{6}{)}^2+\dots }\approx 1.414$$ (Full computation omitted for brevity.)

---

Example 2: Orthogonal Projection

Problem: Find the orthogonal projection of $x=\left[\begin{array}{c}7\\ 6\end{array}\right]$ onto $u=\left[\begin{array}{c}4\\ 2\end{array}\right]$.

Solution: The projection formula is: $${\text{proj}}_{u}x=\left(\frac{x\cdot u}{u\cdot u}\right)u$$

1. Compute dot products: $$x\cdot u=7\times 4+6\times 2=28+12=40$$ $$u\cdot u=4^2+2^2=16+4=20$$
2. Projection: $${\text{proj}}_{u}x=\left(\frac{40}{20}\right)\left[\begin{array}{c}4\\ 2\end{array}\right]=2\left[\begin{array}{c}4\\ 2\end{array}\right]=\left[\begin{array}{c}8\\ 4\end{array}\right]$$
3. Orthogonal decomposition: $$x={\text{proj}}_{u}x+\text{orthogonal part}=\left[\begin{array}{c}8\\ 4\end{array}\right]+\left[\begin{array}{c}-1\\ 2\end{array}\right]$$ (Verify: $(-1,2)\cdot (4,2)=0$.)

---

Applications of Least Squares

1. Data Fitting (Regression):

   • Fitting a line $y=a_0+a_{1}x$ to data points $(x_i,y_i)$.
   • Example: Given points $(2,1),(5,2),(7,3),(8,3)$, solve: $$A=\left[\begin{array}{cc}1& 2\\ 1& 5\\ 1& 7\\ 1& 8\end{array}\right],b=\left[\begin{array}{c}1\\ 2\\ 3\\ 3\end{array}\right]$$ The least squares solution gives the best-fit line coefficients $a_0,a_1$.

2. Computer Graphics:

   • Curve fitting, surface reconstruction.

3. Signal Processing:

   • Noise reduction, filtering.

4. Machine Learning:

   • Linear regression, support vector machines (SVM).

---

Exam Tip

1. Understand the Geometry:

   • The least squares solution $x^{\ast }$ minimizes the distance between $b$ and the column space of $A$.
   • The error $b-A{x}^{\ast }$ is orthogonal to $\text{col}(A)$.

2. Normal Equations vs. QR/SVD:

   • For small problems, normal equations are acceptable.
   • For large or ill-conditioned problems, always prefer QR or SVD in exams.

3. Projection Formula:

   • Memorize: $${\text{proj}}_{W}x=A(A^{T}A{)}^{-1}{A}^{T}x$$
   • For a single vector $u$, use: $${\text{proj}}_{u}x=\left(\frac{x\cdot u}{u\cdot u}\right)u$$

4. Error Calculation:

   • The least squares error is $\Vert b-A{x}^{\ast }\Vert$. Compute it using: $$\Vert b-A{x}^{\ast }{\Vert }^2=b^{T}b-(A{x}^{\ast }{)}^T(A{x}^{\ast })$$
   • Alternatively, use the residual formula: $$\Vert A{x}^{\ast }-b\Vert =\sqrt{b^T(I-A(A^{T}A{)}^{-1}{A}^T)b}$$

5. Common Pitfalls:

   • Non-invertible $A^{T}A$: If $A^{T}A$ is singular, the system has infinitely many solutions. Use SVD or QR.
   • Overfitting: In regression, too many parameters can lead to poor generalization. Least squares alone does not prevent this.

6. Past Exam Patterns:

   • Direct computation: Solve for $x^{\ast }$ given $A$ and $b$ (30-40% of questions).
   • Projection problems: Given $x$ and $u$, find ${\text{proj}}_{u}x$ (20%).
   • Error calculation: Compute $\Vert A{x}^{\ast }-b\Vert$ (20%).
   • Theoretical questions: Explain why least squares works (10-20%).

---

Summary Table for Quick Revision