Linear least squares (mathematics)

Linear least squares, also known as linear regression, is the form of least squares analysis which is used to find an optimal solution for an overdetermined system of linear equations. The idea behind linear least squares is that in order to obtain good estimates for the parameters of a given linear model one should use more observations than there are parameters to be determined.

Using linear least squares to fit a line through a large number of observations usually gives better results than picking just two points through which to draw the line.

Problem statement and solution

The objective consists of finding the minimum value of a sum of m squared residuals,r_i, with respect to a set of n parameters of a model,

$S=\sum _{i=1}^{i=m}r_{i}^{2}.$

Each residual

$r_{i}=y_{i}-f(x_{i},{\boldsymbol {\beta }})$

is defined as the difference between the values of a dependent variable, y_i and of the model function,$f(x_{i},{\boldsymbol {\beta }})$, where x_i is an independent variable and ${\boldsymbol {\beta }}$ is a vector of n parameters. The values of the dependent variable are obtained from experimental measurements.

In linear least squares, if is assumed that the model function depends linearly on the parameters ${\boldsymbol {\beta }}$,

$f(x_{i},{\boldsymbol {\beta }})=\sum _{j=1}^{j=n}X_{ij}\beta _{j}$,

with some constants $X_{ij}$. Note that the value of the constants $X_{ij}$ depends on f and the values x_i of the independent variable x. The linearity here means only that the model function $f(x,{\boldsymbol {\beta }})$ is linearly dependent on the parameters ${\boldsymbol {\beta }}$; f may well be a nonlinear function of x.

The minimum value of S occurs when the gradient is zero. Since the model contains n parameters there are n gradient equations.

${\frac {\partial S}{\partial \beta _{j}}}=2\sum _{i}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}=0\ (j=1,n)$

We have

$r_{i}=y_{i}-\sum _{j=1}^{j=n}X_{ij}\beta _{j}$

and

${\frac {\partial r_{i}}{\partial \beta _{j}}}=-X_{ij}$.

Substitution of these expressions into the gradient equations gives

${\frac {\partial S}{\partial \beta _{j}}}=-2\sum _{i=1}^{i=m}X_{ij}\left(y_{i}-\sum _{j=1}^{j=n}X_{ij}\beta _{j}\right)$

Setting each gradient equation equal to zero and rearranging, the n simultaneous linear equations, the normal equations are obtained.

$\sum _{i=1}^{i=m}\sum _{k=1}^{k=n}X_{ij}X_{ik}{\hat {\beta }}_{k}=\sum _{i=1}^{i=m}X_{ij}y_{i}\ (j=1,n)\,$

The normal equations are written in matrix notation as

$\mathbf {\left(X^{T}X\right){\hat {\boldsymbol {\beta }}}=X^{T}y}$

Solution of the normal equations yields the least squares estimators,${\hat {\boldsymbol {\beta }}}$, of the parameter values. See example of linear regression for a worked-out numerical example with three parameters.

When the observations are not equally reliable, a weighted sum of squares may be minimized.

$S=\sum _{i=1}^{i=m}W_{ii}r_{i}^{2}$

Each element of the diagonal weight matrix, W should,ideally, be equal to the reciprocal of the variance of the measurement. The normal equations are then

$\mathbf {\left(X^{T}WX\right){\hat {\boldsymbol {\beta }}}=X^{T}Wy}$

Straight line fitting

For straight line fitting there are only two normal equations. This means that a complete algebraic solution may be worked out with relative ease. For the model

$f(x_{i},{\boldsymbol {\beta }})=\alpha +\beta x_{i}$

$X_{i1}=1,X_{i2}=x_{i}\,$

With unit weights the normal equations are therefore

$\left(\sum 1^{2}\right)\alpha +\left(\sum x_{i}\right)\beta =\sum y_{i}$

$\left(\sum x_{i}\right)\alpha +\left(\sum x_{i}^{2}\right)\beta =\sum x_{i}y_{i}$

All the summations go from i=1 to i=m. Each summation can be represented by a single symbol

$\sum 1^{2}=m$

$\sum x_{i}=S_{x}$

$\sum y_{i}=S_{y}$

$\sum x_{i}^{2}=S_{x^{2}}$

$\sum x_{i}y_{i}=S_{xy}$

In terms of these symbols the normal equations become

$m\alpha +S_{x}\beta =S_{y}\,$

$S_{x}\alpha +S_{x^{2}}\beta =S_{xy}\,$

and the solution, by Cramer's rule is

${\hat {\alpha }}={\frac {S_{x^{2}}S_{y}-S_{x}S_{xy}}{D}}\,$

${\hat {\beta }}={\frac {mS_{xy}-S_{x}S_{y}}{D}}\,$

$D=mS_{x^{2}}-(S_{x})^{2}$

These expressions have been used in hand calculators because each time a data point is added or removed, the five sums are adjusted and the parameters are recalculated, only seven operations in all. The standard deviations of the parameter estimates (often called their standard errors) are

$\sigma (\alpha )={\sqrt {{\frac {S}{m-2}}{\frac {S_{x^{2}}}{D}}}}$

$\sigma (\beta )={\sqrt {{\frac {S}{m-2}}{\frac {m}{D}}}}$

The correlation coefficient between the parameter estimates is

$\rho _{12}={\frac {-S_{x}}{\sqrt {mS_{x^{2}}}}}$

Example

With a set of observed data points y=2,3,3,4 obtained with the independent variable, x at values -1,0,2,4.

Plot of points and solution.

$m=4\!$

$\sum x=5\!$

$\sum y=12\!$

$\sum x^{2}=21\!$

$\sum xy=20\!$

$D=59\!$

$\alpha ={\frac {21\times 12-5\times 20}{59}}={\frac {152}{59}}$

$\beta ={\frac {4\times 20-5\times 12}{59}}={\frac {20}{59}}$

Now, the residuals are calculated

${\begin{matrix}r_{1}=&0.42\\r_{2}=&-0.25\\r_{3}=&0.07\\r_{4}=&-0.24\\\end{matrix}}$

and S=0.305. After calculating the standard deviations the final result is obtained.

$\alpha =2.6\pm 0.2$

$\beta =0.3\pm 0.1$

Note that the error is only quoted to one significant digit.

Computation

Although the algebraic solution of the normal equations can be written as

$\mathbf {{\hat {\boldsymbol {\beta }}}=\left(X^{T}X\right)^{-1}X^{T}y}$

it is not good practice to invert the normal equations matrix. An exception occurs in numerical smoothing and differentiation where an analytical expression is required.

If the matrix $\mathbf {X^{T}X}$ is well-conditioned and positive definite, that is, it has full rank, the normal equations can be solved directly by using the Cholesky decomposition $\mathbf {X^{T}X=R^{T}R}$, where R is an upper triangular matrix, giving

$\mathbf {R^{T}R{\hat {\boldsymbol {\beta }}}=X^{T}y}$

The solution is obtained in two stages, a forward substitution, $\mathbf {R^{T}z=X^{T}y}$, followed by a backward substitution $\mathbf {R{\hat {\boldsymbol {\beta }}}=z}$. Both subtitutions are facilitated by the triangular nature of R.

A slower but more numerically stable method, which still works if X is not full rank, can be obtained by computing the QR decomposition

$\mathbf {X=QR}$.

where Q is an orthogonal matrix and R is an upper triangular matrix.One can then solve

$\mathbf {R{\hat {\boldsymbol {\beta }}}=Q^{T}y}$

A third alternative is to use the singular value decomposition (SVD)

$\mathbf {X=S\Sigma V^{*}}$

This is effectively another kind of orthogonal decomposition as both U and V are orthogonal. This method is the most computationally intensive, but is particularly useful if the normal equations matrix is very ill-conditioned (i.e. if its condition number multiplied by the machine's relative round-off error is appreciably large). In that case, including the smallest singular values in the inversion merely adds numerical noise to the solution. This can be cured using the truncated SVD approach, giving a more stable and exact answer, by explicitly setting to zero all singular values below a certain threshold and so ignoring them, a process closely related to factor analysis.

Properties of the least-squares estimator

If the experimental errors, $\epsilon \,$, are uncorrelated, have a mean of zero and a constant variance, $\sigma$, the Gauss-Markov theorem states that the least-squares estimator, ${\hat {\beta }}$, has the minimum variance of all estimators that are linear combinations of the observations. In this sense it is the best, or optimal, estimator of the parameters. Note particularly that this property is independent of the statistical distribution function of the errors. In other words, the distribution function of the errors need not be a Normal distribution.

For example, it is easy to show that the arithmetic mean of a set of measurements of a quantity is the least-squares estimator of the value of that quantity. If the conditions of the Gauss-Markov theorem apply, the arithmetic mean is optimal, whatever the distribution of errors of the measurements might be.

However, in the case that the experimental errors do belong to a Normal distribuition, the least-squares estimator is also a maximum likelihood estimator.

These two properties underpin the use of the method of least squares for all types of data fitting, even when the assumptions are not strictly valid.

Limitations

An assumption underlying the treatment given above is that the independent variable, x, is free of error. In practice, the errors on the measurements of the independent variable are usually much smaller than the errors on the dependent variable and can therefore be ignored. When this is not the case, total least squares also known as Errors-in-variables model, or Rigorous least squares, should be used. This can be done by adjusting the weighting scheme to take into account errors on both the dependant and independent variables and then following the standard procedure.

In some cases the (weighted) normal equations matrix $\mathbf {X^{T}X}$ is ill-conditioned; this occurs when the measurements have only a marginal effect on one or more of the estimated parameters. In these cases, the least squares estimate amplifies the measurement noise and may be grossly inaccurate. Various regularization techniques can be applied in such cases, the most common of which is called Tikhonov regularization. If further information about the parameters is known, for example, a range of possible values of x, then minimax techniques can also be used to increase the stability of the solution.

Another drawback of the least squares estimator is the fact that the norm of the residuals, $\|\mathbf {y-X{\boldsymbol {\beta }}} \|$ is minimized, whereas in some cases one is truly interested in obtaining small error in the parameter $\mathbf {\boldsymbol {\beta }}$, e.g., a small value of $\|{\boldsymbol {\beta }}-{\hat {\boldsymbol {\beta }}}\|$. However, since ${\boldsymbol {\beta }}$ is unknown, this quantity cannot be directly minimized. If a prior probability on ${\boldsymbol {\beta }}$ is known, then a Bayes estimator can be used to minimize the mean squared error, $E\left\{\|{\boldsymbol {\beta }}-{\hat {\boldsymbol {\beta }}}\|^{2}\right\}$. The least squares method is often applied when no prior is known. Surprisingly, however, better estimators can be constructed, an effect known as Stein's phenomenon. For example, if the measurement error is Gaussian, several estimators are known which dominate, or outperform, the least squares technique; the best known of these is the James-Stein estimator.

Parameter errors, correlation and confidence limits

The parameter values are linear combinations of the observed values

$\mathbf {{\hat {\beta }}=(X^{T}WX)^{-1}X^{T}Wy}$

Therefore an expression for the errors on the parameter can be obtained by error propagation from the errors on the observations. Let the variance-covariance matrix for the observations be denoted by M and that of the parameters by M^$\beta$. Then,

$\mathbf {M^{\beta }=(X^{T}WX)^{-1}X^{T}WMW^{T}X(X^{T}WX)^{-1}}$

When $\mathbf {W=M^{-1}}$, this simplifies to

$\mathbf {M^{\beta }=(X^{T}WX)^{-1}}$

When unit weights are used ($\mathbf {W=I,{\hat {\beta }}=(X^{T}X)^{-1}X^{T}y}$) it is implied that the experimental errors are uncorrelated and all equal: $\mathbf {M} =\sigma ^{2}\mathbf {I}$, where $\sigma ^{2}\,$ is known as the variance of an observation of unit weight, and $\mathbf {I}$ is an identity matrix. In this case $\sigma ^{2}\,$ is approximated by ${\frac {S}{m-n}}$, where S is the minimum value of the objective function.

$\mathbf {M^{\beta }=} {\frac {S}{m-n}}\mathbf {(X^{T}X)^{-1}}$

In all cases, the variance of the parameter $\beta _{i}$ is given by $M_{ii}^{\beta }$ and the covariance between parameters $\beta _{i}$ and $\beta _{j}$ is given by $M_{ij}^{\beta }$. Standard deviation is the square root of variance and the correlation coefficient is given by $\rho _{ij}=M_{ij}^{\beta }/\sigma _{i}/\sigma _{j}$. These error estimates reflect only random errors in the measurements. The true uncertainty in the parameters is larger due to the presence of systematic errors which, by definition, cannot be quantified. Note that even though the observations may be un-correlated, the parameters are always correlated.

It is often assumed, for want of any concrete evidence, that the error on a parameter belongs to a Normal distribution with a mean of zero and standard deviation $\sigma$. Under that assumption the following confidence limits can be derived.

68% confidence limits, ${\hat {\beta }}\pm \sigma$

95% confidence limits, ${\hat {\beta }}\pm 2\sigma$

99% confidence limits, ${\hat {\beta }}\pm 2.5\sigma$

The assumption is not unreasonable when m>>n. If the experimental errors are normally distributed the parameters will belong to a Student's t-distribution with m-n degrees of freedom. When m>>n Student's t-distribution approximates to a Normal distribution. Note, however, that these confidence limits cannot take systematic error into account. Also, parameter errors should be quoted to one significant figure only, as they are subject to sampling error.

When the number of observations is relatively small, Chebychev's inequality can be used for an upper bound on probabilities, regardless of any assumptions about the distribution of experimental errors: the maximum probabilities that a parameter will be more than 1, 2 or 3 standard deviations away from its expectation value are 100%, 25% and 11% respectively.

Residual values and correlation

The residuals are related to the observations by

$\mathbf {{\hat {r}}=y-X{\hat {\beta }}=y-X\left(X^{T}WX\right)^{-1}X^{T}y}$

The symmetric, idempotent matrix $\mathbf {X\left(X^{T}WX\right)^{-1}X^{T}}$ is known in the statistics literature as the hat matrix, $\mathbf {H}$. Thus,

$\mathbf {{\hat {r}}=\left(I-H\right)y}$

where I is an identity matrix. The variance-covariance matrice of the residuals, M^r is given by

$\mathbf {M^{r}=\left(I-H\right)M\left(I-H\right)}$

This shows that even though the observations may be un-correlated, the residuals are always correlated.

If experimental error follows a normal distribution, then, because of the linear relationship between residuals and observations, so should residuals, but since the observations are only a sample of the population of all possible observations, the residuals should belong to a Student's t-distribution. Studentized residuals are useful in making a statistical test for an outlier when a particular residual appears to be excessively large.

Objective function

The objective function can be written as

$S=\mathbf {y^{T}(I-H)^{T}(I-H)y=y^{T}(I-H)y}$

since $\mathbf {(I-H)}$ is also symmetric and idempotent. It can be shown from this, that the expected value of S is m-n. Note, however, that this is true only if the weights have been assigned correctly. If unit weights are assumed, the expected value of S is $(m-n)\sigma ^{2}$, where $\sigma ^{2}$ is the variance of an observation.

If it is assumed that the residuals belong to a Normal distribution, the objective function, being a sum of weighted squared residuals, will belong to a Chi-square ($\chi ^{2}$) distribution with m-n degrees of freedom. Some illustrative percentile values of $\chi ^{2}$ are given in the following table.

m-n	$\chi _{0.50}^{2}$	$\chi _{0.95}^{2}$	$\chi _{0.99}^{2}$
10	9.34	18.3	23.2
25	24.3	37.7	44.3
100	99.3	124	136

These values can be used for a statistical criterion as to the goodness-of-fit. When unit weights are used, the numbers should be divided by the variance of an observation.

Applications

• Polynomials in an independent variable, x
  • Straight line: $f(x_{i},{\boldsymbol {\beta }})=\alpha +\beta x$.
  • Quadratic: $f(x_{i},{\boldsymbol {\beta }})=\alpha +\beta x+\gamma x^{2}$.
  • Cubic, quartic and higher polynomials. For high-order polynomials the use of orthogonal polynomials is recommended.
• Numerical smoothing and differentiation This is an application of polynomial fitting.
• Multinomials in more than one independent variable, including surface fitting
• Curve fitting with B-splines
• Chemometrics, Calibration curve, Standard addition

External links

• Least Squares Fitting – From MathWorld
• Least Squares Fitting-Polynomial – From MathWorld