Solved Exercises on Least-Squares Solutions in Linear Algebra

Master least-squares solutions: overdetermined systems, normal equations, applications, and geometric interpretations through these 5 detailed exercises.

Solution: Exercises 1 to 3
1 Best Fit Line Through Points
Exercise 1
Find the least-squares solution for the line \(y = ax + b\) that best fits the points \((1,2)\), \((2,3)\), and \((3,5)\).
Definition:

Least-squares solution: The solution that minimizes the sum of squared residuals between observed and predicted values

Normal equations method:

For system \(A\vec{x} = \vec{b}\), the least-squares solution satisfies \(A^TA\vec{x} = A^T\vec{b}\)

  1. Set up the system: \(A\vec{x} = \vec{b}\) where \(\vec{x} = \begin{pmatrix} a \\ b \end{pmatrix}\)
  2. Form the normal equations: \(A^TA\vec{x} = A^T\vec{b}\)
  3. Solve the resulting system
Design Matrix
\(A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}\)
System
\(A^TA\vec{x} = A^T\vec{b}\)
Solution
\(\vec{x} = \begin{pmatrix} 1.5 \\ 0.33 \end{pmatrix}\)
Step 1: Set up the system

For line \(y = ax + b\), we have:

\(\begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} b \\ a \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ 5 \end{bmatrix}\)

So \(A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}\), \(\vec{x} = \begin{bmatrix} b \\ a \end{bmatrix}\), \(\vec{b} = \begin{bmatrix} 2 \\ 3 \\ 5 \end{bmatrix}\)

Step 2: Calculate \(A^T\)

\(A^T = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix}\)

Step 3: Calculate \(A^TA\)

\(A^TA = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}\)

Step 4: Calculate \(A^T\vec{b}\)

\(A^T\vec{b} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 5 \end{bmatrix} = \begin{bmatrix} 10 \\ 23 \end{bmatrix}\)

Step 5: Solve the normal equations

\(\begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix} \begin{bmatrix} b \\ a \end{bmatrix} = \begin{bmatrix} 10 \\ 23 \end{bmatrix}\)

From first equation: \(3b + 6a = 10\), so \(b = \frac{10 - 6a}{3}\)

Substituting into second: \(6(\frac{10 - 6a}{3}) + 14a = 23\)

\(2(10 - 6a) + 14a = 23\)

\(20 - 12a + 14a = 23\)

\(2a = 3\), so \(a = 1.5\)

Therefore: \(b = \frac{10 - 6(1.5)}{3} = \frac{1}{3} \approx 0.33\)

Best fit line: \(y = 1.5x + 0.33\)
Final answer:

The least-squares best fit line is \(y = 1.5x + \frac{1}{3}\) (approximately \(y = 1.5x + 0.33\))

Applied rules:

• Normal Equations: \(A^TA\vec{x} = A^T\vec{b}\) for least-squares solution

• Minimization: Minimizes \(\|A\vec{x} - \vec{b}\|^2\)

• Geometric Interpretation: Projection of \(\vec{b}\) onto column space of \(A\)

2 Overdetermined System Solution
Exercise 2
Find the least-squares solution to the overdetermined system:
\(\begin{cases} x_1 + x_2 = 1 \\ 2x_1 + x_2 = 2 \\ x_1 + 2x_2 = 3 \\ x_1 + x_2 = 4 \end{cases}\)
Definition:

Overdetermined system: A system with more equations than unknowns, typically having no exact solution

Matrix Form
\(A = \begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix}\)
System
\(A\vec{x} = \vec{b}\)
LS Solution
\(\vec{x} = \begin{pmatrix} 1.25 \\ 1.25 \end{pmatrix}\)
Step 1: Write in matrix form

\(\begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}\)

So \(A = \begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix}\), \(\vec{x} = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\), \(\vec{b} = \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}\)

Step 2: Calculate \(A^T\)

\(A^T = \begin{bmatrix} 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \end{bmatrix}\)

Step 3: Calculate \(A^TA\)

\(A^TA = \begin{bmatrix} 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 7 & 6 \\ 6 & 7 \end{bmatrix}\)

Step 4: Calculate \(A^T\vec{b}\)

\(A^T\vec{b} = \begin{bmatrix} 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 12 \\ 13 \end{bmatrix}\)

Step 5: Solve the normal equations

\(\begin{bmatrix} 7 & 6 \\ 6 & 7 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 12 \\ 13 \end{bmatrix}\)

Using elimination: From first equation: \(7x_1 + 6x_2 = 12\)

From second: \(6x_1 + 7x_2 = 13\)

Multiply first by 7 and second by 6: \(49x_1 + 42x_2 = 84\) and \(36x_1 + 42x_2 = 78\)

Subtract: \(13x_1 = 6\), so \(x_1 = \frac{6}{13} = 1.25\)

Substituting: \(7(1.25) + 6x_2 = 12\), so \(6x_2 = 12 - 8.75 = 3.25\), thus \(x_2 = 1.25\)

Step 6: Verify solution

\(A\vec{x} = \begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1.25 \\ 1.25 \end{bmatrix} = \begin{bmatrix} 2.5 \\ 3.75 \\ 3.75 \\ 2.5 \end{bmatrix}\)

Residual: \(\vec{b} - A\vec{x} = \begin{bmatrix} -1.5 \\ -1.75 \\ -0.75 \\ 1.5 \end{bmatrix}\)

\(\vec{x} = \begin{pmatrix} 1.25 \\ 1.25 \end{pmatrix}\)
Final answer:

The least-squares solution is \(x_1 = 1.25\) and \(x_2 = 1.25\)

Applied rules:

• Overdetermined Systems: No exact solution exists, use least squares

• Normal Equations: \(A^TA\vec{x} = A^T\vec{b}\) provides optimal solution

• Minimization: Minimizes \(\sum_{i=1}^{m} (a_{i1}x_1 + a_{i2}x_2 - b_i)^2\)

3 Quadratic Curve Fitting
Exercise 3
Find the least-squares quadratic curve \(y = a_0 + a_1x + a_2x^2\) that best fits the points \((-1,1)\), \((0,0)\), \((1,1)\), and \((2,4)\).
Definition:

Quadratic curve fitting: Finding coefficients that minimize the sum of squared deviations from a parabolic model

Design Matrix
\(A = \begin{bmatrix} 1 & -1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 4 \end{bmatrix}\)
System
\(A^TA\vec{a} = A^T\vec{y}\)
Coefficients
\(\vec{a} = \begin{pmatrix} 0.25 \\ 0.25 \\ 0.75 \end{pmatrix}\)
Step 1: Set up the system

For \(y = a_0 + a_1x + a_2x^2\), we have:

\(\begin{bmatrix} 1 & -1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 4 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 4 \end{bmatrix}\)

So \(A = \begin{bmatrix} 1 & -1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 4 \end{bmatrix}\), \(\vec{a} = \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix}\), \(\vec{y} = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 4 \end{bmatrix}\)

Step 2: Calculate \(A^T\)

\(A^T = \begin{bmatrix} 1 & 1 & 1 & 1 \\ -1 & 0 & 1 & 2 \\ 1 & 0 & 1 & 4 \end{bmatrix}\)

Step 3: Calculate \(A^TA\)

\(A^TA = \begin{bmatrix} 1 & 1 & 1 & 1 \\ -1 & 0 & 1 & 2 \\ 1 & 0 & 1 & 4 \end{bmatrix} \begin{bmatrix} 1 & -1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 4 \end{bmatrix} = \begin{bmatrix} 4 & 2 & 6 \\ 2 & 6 & 8 \\ 6 & 8 & 18 \end{bmatrix}\)

Step 4: Calculate \(A^T\vec{y}\)

\(A^T\vec{y} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ -1 & 0 & 1 & 2 \\ 1 & 0 & 1 & 4 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 4 \end{bmatrix} = \begin{bmatrix} 6 \\ 7 \\ 17 \end{bmatrix}\)

Step 5: Solve the normal equations

\(\begin{bmatrix} 4 & 2 & 6 \\ 2 & 6 & 8 \\ 6 & 8 & 18 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 6 \\ 7 \\ 17 \end{bmatrix}\)

Using Gaussian elimination (details omitted for brevity):

\(a_0 = 0.25\), \(a_1 = 0.25\), \(a_2 = 0.75\)

Step 6: Write the final equation

The least-squares quadratic curve is: \(y = 0.25 + 0.25x + 0.75x^2\)

\(y = 0.25 + 0.25x + 0.75x^2\)
Final answer:

The least-squares quadratic curve is \(y = 0.25 + 0.25x + 0.75x^2\)

Applied rules:

• Polynomial Fitting: Extend linear model to higher-order terms

• Design Matrix: Each column represents powers of x values

• Normal Equations: Still apply for higher-dimensional parameter spaces

Complete Theory: Least-Squares Solutions
\(A^TA\vec{x} = A^T\vec{b}\)
Normal Equations
Objective
\(\min \|A\vec{x} - \vec{b}\|^2\)
Minimize squared error
Solution
\(\vec{x} = (A^TA)^{-1}A^T\vec{b}\)
Matrix form
Properties
\(P = A(A^TA)^{-1}A^T\)
Projection matrix
Key definitions:

Least-Squares Solution: The vector \(\vec{x}\) that minimizes the sum of squared residuals \(\|A\vec{x} - \vec{b}\|^2\)

Normal Equations: The system \(A^TA\vec{x} = A^T\vec{b}\) whose solution gives the least-squares solution

Overdetermined System: A system with more equations than unknowns, typically inconsistent

Projection Matrix: The matrix \(P = A(A^TA)^{-1}A^T\) that projects \(\vec{b}\) onto the column space of \(A\)

Complete methodology:
  1. Formulate the problem: Express as \(A\vec{x} = \vec{b}\) where the system may be inconsistent
  2. Derive normal equations: Multiply both sides by \(A^T\) to get \(A^TA\vec{x} = A^T\vec{b}\)
  3. Solve the system: Solve the resulting square system (always consistent if columns of A are linearly independent)
  4. Verify optimality: Check that the solution minimizes the objective function
Tip 1: The least-squares solution always exists and is unique if columns of A are linearly independent.
Tip 2: The residual vector \(\vec{r} = A\vec{x} - \vec{b}\) is orthogonal to the column space of A.
Tip 3: The rank of \(A^TA\) equals the rank of A.
Tip 4: Always verify that \(A^TA\) is invertible before solving (columns of A must be linearly independent).

Applications: Linear regression, data fitting, signal processing, econometrics, machine learning.
Advanced Uses: Ridge regression, principal component analysis, singular value decomposition, Kalman filtering.
Formulas to know by heart:

• Normal equations: \(A^TA\vec{x} = A^T\vec{b}\)

• Solution: \(\vec{x} = (A^TA)^{-1}A^T\vec{b}\)

• Projection matrix: \(P = A(A^TA)^{-1}A^T\)

• Fitted values: \(\hat{\vec{y}} = A\vec{x} = P\vec{b}\)

• Residual sum of squares: \(\|\vec{b} - A\vec{x}\|^2\)

Solution: Exercises 4 to 5
4 Weighted Least Squares
Exercise 4
Find the weighted least-squares solution for the system
\(\begin{bmatrix} 1 & 2 \\ 1 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 4 \\ 2 \\ 3 \end{bmatrix}\)
with weights \(w_1 = 2\), \(w_2 = 1\), \(w_3 = 3\).
Definition:

Weighted least squares: A variant where different observations are given different importance in the minimization

Weight Matrix
\(W = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix}\)
WLS System
\(A^TWA\vec{x} = A^TW\vec{b}\)
Solution
\(\vec{x} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}\)
Step 1: Set up the weighted problem

We want to minimize \(\sum_{i=1}^{3} w_i(a_{i1}x_1 + a_{i2}x_2 - b_i)^2\)

This leads to the weighted normal equations: \(A^TWA\vec{x} = A^TW\vec{b}\)

Where \(W = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix}\) is the diagonal matrix of weights

Step 2: Calculate \(A^TWA\)

\(A^TWA = \begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix} \begin{bmatrix} 1 & 2 \\ 1 & 1 \\ 2 & 1 \end{bmatrix}\)

\(A^TWA = \begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 \\ 1 & 1 \\ 6 & 3 \end{bmatrix} = \begin{bmatrix} 15 & 11 \\ 11 & 12 \end{bmatrix}\)

Step 3: Calculate \(A^TW\vec{b}\)

\(A^TW\vec{b} = \begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix} \begin{bmatrix} 4 \\ 2 \\ 3 \end{bmatrix}\)

\(A^TW\vec{b} = \begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 1 \end{bmatrix} \begin{bmatrix} 8 \\ 2 \\ 9 \end{bmatrix} = \begin{bmatrix} 27 \\ 27 \end{bmatrix}\)

Step 4: Solve the weighted normal equations

\(\begin{bmatrix} 15 & 11 \\ 11 & 12 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 27 \\ 27 \end{bmatrix}\)

From first equation: \(15x_1 + 11x_2 = 27\)

From second: \(11x_1 + 12x_2 = 27\)

Multiply first by 12 and second by 11: \(180x_1 + 132x_2 = 324\) and \(121x_1 + 132x_2 = 297\)

Subtract: \(59x_1 = 27\), so \(x_1 = 27/59 \approx 0.458\)

Actually, let's recalculate: From \(15x_1 + 11x_2 = 27\) and \(11x_1 + 12x_2 = 27\)

Multiply first by 12: \(180x_1 + 132x_2 = 324\)

Multiply second by 11: \(121x_1 + 132x_2 = 297\)

Subtract: \(59x_1 = 27\), so \(x_1 = 27/59\)

From first: \(x_2 = \frac{27 - 15(27/59)}{11} = \frac{27(59 - 15)/59}{11} = \frac{27 \cdot 44}{59 \cdot 11} = \frac{108}{59}\)

Step 5: Final calculation

Actually, let's solve this more carefully:

\(15x_1 + 11x_2 = 27\) and \(11x_1 + 12x_2 = 27\)

Subtracting: \(4x_1 - x_2 = 0\), so \(x_2 = 4x_1\)

Substituting: \(15x_1 + 11(4x_1) = 27\)

\(15x_1 + 44x_1 = 27\)

\(59x_1 = 27\), so \(x_1 = \frac{27}{59}\)

And \(x_2 = \frac{108}{59}\)

\(\vec{x} = \begin{pmatrix} \frac{27}{59} \\ \frac{108}{59} \end{pmatrix}\)
Final answer:

The weighted least-squares solution is \(x_1 = \frac{27}{59} \approx 0.458\) and \(x_2 = \frac{108}{59} \approx 1.831\)

Applied rules:

• Weighted Normal Equations: \(A^TWA\vec{x} = A^TW\vec{b}\)

• Weight Matrix: Diagonal matrix with observation weights

• Importance: Higher weights give more influence to those observations

5 Recursive Least Squares
Exercise 5
Consider the recursive least-squares update for a system where at time \(k\), we have measurement \(\vec{a_k}\) and output \(y_k\). If \(\hat{\theta}_{k-1}\) is the estimate at time \(k-1\) and \(P_{k-1}\) is the covariance matrix, derive the update equations.
Definition:

Recursive least squares: A method for updating least-squares estimates as new data arrives, commonly used in adaptive filtering and control systems

Kalman Gain
\(K_k = P_{k-1}\vec{a_k}/(\vec{a_k}^TP_{k-1}\vec{a_k} + \lambda)\)
Parameter Update
\(\hat{\theta}_k = \hat{\theta}_{k-1} + K_k(y_k - \vec{a_k}^T\hat{\theta}_{k-1})\)
Covariance Update
\(P_k = (I - K_k\vec{a_k}^T)P_{k-1}/\lambda\)
Step 1: Understand the recursive formulation

Instead of storing all past data and solving the full normal equations, we update our estimate incrementally:

At time \(k\), we have: \(y_k = \vec{a_k}^T\theta + v_k\) where \(v_k\) is noise

We want to update our estimate \(\hat{\theta}_{k-1}\) using the new measurement \(y_k\)

Step 2: Derive the Kalman gain

The Kalman gain determines how much to adjust the estimate based on the new measurement:

\(K_k = P_{k-1}\vec{a_k}(\vec{a_k}^T P_{k-1}\vec{a_k} + \lambda)^{-1}\)

where \(\lambda\) is the forgetting factor (usually 1 for standard RLS)

\(K_k\) balances between trusting the old estimate and the new measurement

Step 3: Update the parameter estimate

The new estimate is the old estimate plus a correction term:

\(\hat{\theta}_k = \hat{\theta}_{k-1} + K_k(y_k - \vec{a_k}^T\hat{\theta}_{k-1})\)

The term \(y_k - \vec{a_k}^T\hat{\theta}_{k-1}\) is the prediction error (innovation)

Step 4: Update the covariance matrix

The covariance matrix is updated to reflect the reduced uncertainty:

\(P_k = (I - K_k\vec{a_k}^T)P_{k-1}/\lambda\)

This reflects how the new measurement reduces uncertainty in the direction of \(\vec{a_k}\)

Step 5: Verify the recursive property

The recursive formulation ensures that \(\hat{\theta}_k\) is the least-squares solution using all measurements up to time \(k\)

\(\hat{\theta}_k = \arg\min_{\theta} \sum_{i=1}^{k} (y_i - \vec{a_i}^T\theta)^2\)

Step 6: Practical considerations

In implementation, numerical stability is important:

• Use QR decomposition or square-root algorithms for better numerical properties

• Monitor the condition number of \(P_k\)

• Consider regularization for ill-conditioned problems

RLS equations:
\(K_k = P_{k-1}\vec{a_k}/(\vec{a_k}^TP_{k-1}\vec{a_k} + \lambda)\)
\(\hat{\theta}_k = \hat{\theta}_{k-1} + K_k(y_k - \vec{a_k}^T\hat{\theta}_{k-1})\)
\(P_k = (I - K_k\vec{a_k}^T)P_{k-1}/\lambda\)
Final answer:

The recursive least-squares update equations are:
Kalman gain: \(K_k = P_{k-1}\vec{a_k}/(\vec{a_k}^TP_{k-1}\vec{a_k} + \lambda)\)
Parameter update: \(\hat{\theta}_k = \hat{\theta}_{k-1} + K_k(y_k - \vec{a_k}^T\hat{\theta}_{k-1})\)
Covariance update: \(P_k = (I - K_k\vec{a_k}^T)P_{k-1}/\lambda\)

Applied rules:

• Recursive Estimation: Update estimates without storing all past data

• Kalman Filter Connection: RLS is a special case of Kalman filtering

• Computational Efficiency: O(n²) per update vs O(n³) for batch processing

Detailed Summary: Least-Squares Solutions
\(\min_{\vec{x}} \|A\vec{x} - \vec{b}\|^2\)
Least-Squares Optimization
Key definitions:

Least-Squares Solution: The vector \(\vec{x}\) that minimizes the Euclidean norm of the residual vector \(A\vec{x} - \vec{b}\)

Normal Equations: The system \(A^TA\vec{x} = A^T\vec{b}\) derived from setting the gradient of the objective function to zero

Projection Matrix: The matrix \(P = A(A^TA)^{-1}A^T\) that projects any vector onto the column space of \(A\)

Pseudo-inverse: The matrix \(A^+ = (A^TA)^{-1}A^T\) that provides the least-squares solution

Complete methodology:
  1. Problem Setup: Express the problem as finding \(\vec{x}\) that minimizes \(\|A\vec{x} - \vec{b}\|^2\)
  2. Derivation: Take the gradient with respect to \(\vec{x}\) and set to zero
  3. Normal Equations: Obtain \(A^TA\vec{x} = A^T\vec{b}\) from the optimality condition
  4. Solution: Solve the normal equations to get \(\vec{x} = (A^TA)^{-1}A^T\vec{b}\)
Tip 1: The least-squares solution is the orthogonal projection of \(\vec{b}\) onto the column space of \(A\).
Tip 2: If \(A\) has full column rank, the solution is unique and given by \(\vec{x} = (A^TA)^{-1}A^T\vec{b}\).
Tip 3: The residual vector \(\vec{r} = \vec{b} - A\vec{x}\) is orthogonal to every column of \(A\).
Tip 4: For large systems, iterative methods may be more efficient than direct matrix inversion.
Applications: Linear regression, curve fitting, signal processing, econometrics, machine learning, computer vision.
Advanced Uses: Ridge regression, LASSO, principal component analysis, Kalman filtering, system identification.
Core principles:

• Geometric Interpretation: The solution projects the observation vector onto the model space

• Optimality: Minimizes the sum of squared residuals, providing the best linear unbiased estimator (BLUE)

• Uniqueness: Unique solution exists when columns of A are linearly independent

• Stability: Solution depends continuously on the data, though conditioning matters

Visualization: Least-Squares Fitting
Exercise 6: Fitting Quality Assessment
Understanding how least-squares minimizes error:
- The fitted line passes through the "center" of the data
- Residuals sum to zero (for models with intercept)
- The sum of squared residuals is minimized

Analysis: The visualization shows how least-squares fitting balances the errors across all data points.

  • Blue dots: Original data points
  • Red line: Least-squares fit
  • Green lines: Vertical residuals (errors)

Questions & Answers

Question: Why do we use squares in least-squares? Why not absolute values or fourth powers?

Answer: The choice of squares in least-squares has several important advantages:

  • Differentiability: The squared error function is smooth everywhere, allowing us to use calculus for optimization.
  • Geometric interpretation: Squared errors correspond to Euclidean distance, which has nice geometric properties.
  • Statistical justification: Under Gaussian noise assumptions, least-squares gives the maximum likelihood estimate.
  • Algebraic simplicity: Leads to linear normal equations that are straightforward to solve.

While absolute values (L1 norm) are sometimes used for robustness against outliers, they create non-smooth optimization problems that are harder to solve. Higher powers would overemphasize large errors and complicate the mathematics without significant benefits.

The squared error penalizes larger deviations more heavily than smaller ones, which often makes sense in practical applications.

Question: What happens when the matrix \(A^TA\) is not invertible? When does this occur?

Answer: The matrix \(A^TA\) fails to be invertible precisely when the columns of \(A\) are linearly dependent:

  • Rank deficiency: The columns of \(A\) do not form a linearly independent set.
  • Geometric interpretation: The column space of \(A\) has lower dimension than the number of columns.
  • Practical causes: Redundant features, exact linear relationships between variables, or too few observations relative to parameters.

When \(A^TA\) is not invertible, the normal equations still have solutions, but they are not unique. In this case, we can use the pseudo-inverse (via SVD) to find the minimum-norm solution among all possible least-squares solutions.

To detect this issue, check if \(\det(A^TA) = 0\) or if the rank of \(A\) is less than the number of columns. Regularization techniques can help address this problem in practice.

Question: How do least-squares solutions relate to statistical concepts like confidence intervals?

Answer: Least-squares solutions form the foundation for many statistical inference procedures:

  • Variance estimation: The covariance matrix of the parameter estimates is \(\sigma^2(A^TA)^{-1}\), where \(\sigma^2\) is the error variance.
  • Confidence intervals: Built using the estimated parameter variances and the t-distribution.
  • Hypothesis testing: Tests for parameter significance use the standard errors derived from the covariance matrix.

Under the assumption that errors are normally distributed with mean 0 and variance \(\sigma^2\), the least-squares estimates are normally distributed with mean equal to the true parameters and covariance \(\sigma^2(A^TA)^{-1}\).

The residual sum of squares \(\|A\vec{x} - \vec{b}\|^2\) is used to estimate \(\sigma^2\), which is crucial for constructing confidence intervals and performing hypothesis tests about the parameters.

This connection between linear algebra and statistics is fundamental to regression analysis and experimental design.