Least-squares solution: The solution that minimizes the sum of squared residuals between observed and predicted values
For system \(A\vec{x} = \vec{b}\), the least-squares solution satisfies \(A^TA\vec{x} = A^T\vec{b}\)
- Set up the system: \(A\vec{x} = \vec{b}\) where \(\vec{x} = \begin{pmatrix} a \\ b \end{pmatrix}\)
- Form the normal equations: \(A^TA\vec{x} = A^T\vec{b}\)
- Solve the resulting 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}\)
\(A^T = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix}\)
\(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}\)
\(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}\)
\(\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\)
The least-squares best fit line is \(y = 1.5x + \frac{1}{3}\) (approximately \(y = 1.5x + 0.33\))
• 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\)
\(\begin{cases} x_1 + x_2 = 1 \\ 2x_1 + x_2 = 2 \\ x_1 + 2x_2 = 3 \\ x_1 + x_2 = 4 \end{cases}\)
Overdetermined system: A system with more equations than unknowns, typically having no exact solution
\(\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}\)
\(A^T = \begin{bmatrix} 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \end{bmatrix}\)
\(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}\)
\(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}\)
\(\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\)
\(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}\)
The least-squares solution is \(x_1 = 1.25\) and \(x_2 = 1.25\)
• 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\)
Quadratic curve fitting: Finding coefficients that minimize the sum of squared deviations from a parabolic model
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}\)
\(A^T = \begin{bmatrix} 1 & 1 & 1 & 1 \\ -1 & 0 & 1 & 2 \\ 1 & 0 & 1 & 4 \end{bmatrix}\)
\(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}\)
\(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}\)
\(\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\)
The least-squares quadratic curve is: \(y = 0.25 + 0.25x + 0.75x^2\)
The least-squares quadratic curve is \(y = 0.25 + 0.25x + 0.75x^2\)
• 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
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\)
- Formulate the problem: Express as \(A\vec{x} = \vec{b}\) where the system may be inconsistent
- Derive normal equations: Multiply both sides by \(A^T\) to get \(A^TA\vec{x} = A^T\vec{b}\)
- Solve the system: Solve the resulting square system (always consistent if columns of A are linearly independent)
- Verify optimality: Check that the solution minimizes the objective function
• 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\)
\(\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\).
Weighted least squares: A variant where different observations are given different importance in the minimization
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
\(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}\)
\(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}\)
\(\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}\)
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}\)
The weighted least-squares solution is \(x_1 = \frac{27}{59} \approx 0.458\) and \(x_2 = \frac{108}{59} \approx 1.831\)
• 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
Recursive least squares: A method for updating least-squares estimates as new data arrives, commonly used in adaptive filtering and control systems
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\)
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
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)
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}\)
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\)
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
\(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\)
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\)
• 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
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
- Problem Setup: Express the problem as finding \(\vec{x}\) that minimizes \(\|A\vec{x} - \vec{b}\|^2\)
- Derivation: Take the gradient with respect to \(\vec{x}\) and set to zero
- Normal Equations: Obtain \(A^TA\vec{x} = A^T\vec{b}\) from the optimality condition
- Solution: Solve the normal equations to get \(\vec{x} = (A^TA)^{-1}A^T\vec{b}\)
• 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
- 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)