Least Squares

Least squares is a mathematical optimization technique that seeks to find the best fit to a set of data by minimizing the sum of the squared differences between observed values and predicted values. It is one of the most widely used approaches in data fitting and parameter estimation.

Mathematical Formulation

Basic Formulation

Given a set of $m$ observations $(x_i,y_i)$ for $i=1,2,\dots ,m$ and a model function $f(x;\theta )$ parameterized by a vector $\theta \in {\mathbb{R}}^n$, the least squares problem is:

${\min }_{\theta }{\sum }_{i=1}^m[y_i-f(x_i;\theta ){]}^2$

This can be rewritten in vector form by defining the residual vector $\mathbf{r}(\theta )\in {\mathbb{R}}^m$ with components $r_i(\theta )=y_i-f(x_i;\theta )$:

${\min }_{\theta }|\mathbf{r}(\theta ){|}^2={\min }_{\theta }\mathbf{r}(\theta {)}^T\mathbf{r}(\theta )$

Weighted Least Squares

When observations have different uncertainties, a weighted least squares approach is used:

${\min }_{\theta }{\sum }_{i=1}^m{w}_i[y_i-f(x_i;\theta ){]}^2$

where $w_i>0$ are weights, typically chosen as $w_i=1/{\sigma }_i^2$ where ${\sigma }_i$ is the standard deviation of the $i$-th observation.

Regularized Least Squares

To prevent overfitting or handle ill-posed problems, regularization terms can be added:

${\min }_{\theta }|\mathbf{r}(\theta ){|}^2+\lambda |\theta {|}^2$

This is known as Tikhonov regularization or ridge regression when using the $L_2$ norm of $\theta$.

Linear Least Squares

Formulation

In linear least squares, the model function is a linear combination of parameters:

$f(x_i;\theta )={\sum }_{j=1}^n{\theta }_j{\varphi }_j(x_i)$

where ${\varphi }_j$ are basis functions. This can be written in matrix form as:

$\mathbf{y}=\mathbf{X}\theta +\mathbf{e}$

where:

• $\mathbf{y}\in {\mathbb{R}}^m$ is the vector of observations
• $\mathbf{X}\in {\mathbb{R}}^{m\times n}$ is the design matrix with elements $X_{ij}={\varphi }_j(x_i)$
• $\mathbf{e}\in {\mathbb{R}}^m$ is the error vector

The objective function becomes:

${\min }_{\theta }|\mathbf{y}-\mathbf{X}\theta {|}^2$

Normal Equations

The optimal solution to the linear least squares problem satisfies the normal equations:

${\mathbf{X}}^T\mathbf{X}\theta ={\mathbf{X}}^T\mathbf{y}$

If ${\mathbf{X}}^T\mathbf{X}$ is invertible, the solution is:

${\theta }^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$

This is the closed-form solution to the linear least squares problem.

Numerical Methods for Linear Least Squares

Several numerical methods can be used to solve linear least squares problems, especially for large-scale or ill-conditioned problems:

1. QR Decomposition:

   • Decompose $\mathbf{X}=\mathbf{QR}$ where $\mathbf{Q}$ is orthogonal and $\mathbf{R}$ is upper triangular
   • Solution: ${\theta }^{\ast }={\mathbf{R}}^{-1}{\mathbf{Q}}^T\mathbf{y}$
   • More stable than direct solution of normal equations

2. Singular Value Decomposition (SVD):

   • Decompose $\mathbf{X}=\mathbf{U\Sigma }{\mathbf{V}}^T$
   • Solution: ${\theta }^{\ast }=\mathbf{V}{\mathbf{\Sigma }}^{+}{\mathbf{U}}^T\mathbf{y}$ where ${\mathbf{\Sigma }}^{+}$ is the pseudoinverse of $\mathbf{\Sigma }$
   • Most stable but computationally expensive
   • Handles rank-deficient problems

3. Cholesky Decomposition:

   • Decompose ${\mathbf{X}}^T\mathbf{X}=\mathbf{L}{\mathbf{L}}^T$ where $\mathbf{L}$ is lower triangular
   • Solution via forward and backward substitution
   • Efficient for positive definite normal equations

4. Iterative Methods:

   • Conjugate Gradient (CG)
   • LSQR (for sparse problems)
   • Suitable for very large-scale problems

Nonlinear Least Squares

Formulation

When the model function is nonlinear in the parameters, we have a nonlinear least squares problem:

${\min }_{\theta }|\mathbf{r}(\theta ){|}^2$

where $r_i(\theta )=y_i-f(x_i;\theta )$ and $f$ is nonlinear in $\theta$.

Gauss-Newton Method

The Gauss-Newton method is a specialized algorithm for nonlinear least squares problems:

1. Start with an initial guess ${\theta }_0$
2. At each iteration $k$:
   • Compute the Jacobian matrix ${\mathbf{J}}_k$ with elements $J_{ij}=\frac{\partial r_i}{\partial {\theta }_j}({\theta }_k)$
   • Solve the linear system: ${\mathbf{J}}_k^T{\mathbf{J}}_k\Delta \theta =-{\mathbf{J}}_k^T\mathbf{r}({\theta }_k)$
   • Update: ${\theta }_{k+1}={\theta }_k+\Delta \theta$
3. Repeat until convergence

This can be viewed as applying Newton’s method to the normal equations, but approximating the Hessian as $\mathbf{H}\approx {\mathbf{J}}^T\mathbf{J}$.

Levenberg-Marquardt Algorithm

The Levenberg-Marquardt algorithm adds damping to the Gauss-Newton method to improve stability:

$({\mathbf{J}}_k^T{\mathbf{J}}_k+{\lambda }_k\mathbf{I})\Delta \theta =-{\mathbf{J}}_k^T\mathbf{r}({\theta }_k)$

where ${\lambda }_k>0$ is a damping parameter that adjusts dynamically:

• If the step reduces the error, decrease $\lambda$ (more like Gauss-Newton)
• If the step increases the error, increase $\lambda$ (more like gradient descent)

This can be viewed as a trust region method where the damping parameter controls the size of the trust region.

Applications of Least Squares

Regression Analysis

Least squares is the foundation of regression analysis, used to model relationships between variables:

• Linear regression
• Polynomial regression
• Multiple regression
• Generalized linear models

Curve Fitting

Fitting mathematical functions to data points:

• Interpolation
• Approximation of complex functions
• Smoothing noisy data

Parameter Estimation

Estimating parameters in physical models:

• System identification in control theory
• Estimating chemical reaction rates
• Determining material properties

Signal Processing

Processing and analyzing signals:

• Filter design
• System identification
• Spectrum analysis

Geodesy and Surveying

Determining positions and distances:

• GPS position estimation
• Surveying measurements
• Geodetic network adjustments

Statistical Interpretation

Least squares estimation has important statistical interpretations:

1. Maximum Likelihood Estimation: Under the assumption of independent, identically distributed Gaussian errors, the least squares estimate is equivalent to the maximum likelihood estimate.

2. Best Linear Unbiased Estimator (BLUE): Under the Gauss-Markov assumptions, the least squares estimator is the best linear unbiased estimator.

3. Minimum Variance Unbiased Estimator: If the errors are normally distributed, the least squares estimator is the minimum variance unbiased estimator.

Error Analysis and Diagnostics

Several metrics help evaluate the quality of least squares fits:

1. Residual Analysis:

   • Plot residuals to check for patterns
   • Test for normality of residuals
   • Check for autocorrelation

2. Goodness of Fit Measures:

   • Coefficient of determination ($R^2$)
   • Adjusted $R^2$
   • Root mean squared error (RMSE)

3. Leverage and Influence:

   • Hat matrix diagonal elements (leverage)
   • Cook’s distance (influence)
   • DFFITS and DFBETAS

Implementation Considerations

Numerical Stability

Linear least squares problems can become ill-conditioned when:

• The columns of $\mathbf{X}$ are nearly linearly dependent
• There are large differences in scale among variables
• The number of parameters is large compared to the number of data points

Solutions include:

• Regularization
• Using stable decomposition methods (SVD)
• Data preprocessing (centering, scaling)

Computational Efficiency

For large-scale problems, considerations include:

• Memory requirements for storing matrices
• Computational complexity of matrix operations
• Specialized algorithms for sparse systems
• Iterative methods for very large systems

Related Pages

• Linear Regression
• Nonlinear Least Squares
• Gauss-Newton Method
• Levenberg-Marquardt Method
• Regularization Methods
• Numerical Methods
• Model Fitting and Regression