Least squares

Statistics: Scientific method · Research methods · Experimental design · Undergraduate statistics courses · Statistical tests · Game theory · Decision theory

Least squares is a mathematical optimization technique which, when given a series of measured data, attempts to find a function which closely approximates the data (a "best fit"). It attempts to minimize the sum of the squares of the ordinate differences (called residuals) between points generated by the function and corresponding points in the data. Specifically, it is called least mean squares (LMS) when the number of measured data is 1 and the gradient descent method is used to minimize the squared residual. LMS is known to minimize the expectation of the squared residual, with the smallest operations (per iteration). But it requires a large number of iterations to converge.

An implicit requirement for the least squares method to work is that errors in each measurement be randomly distributed. The Gauss-Markov theorem proves that least square estimators are unbiased and that the sample data do not have to comply with, for instance, a normal distribution. It is also important that the collected data be well chosen, so as to allow visibility into the variables to be solved for (for giving more weight to particular data, refer to weighted least squares).

The least squares technique is commonly used in curve fitting. Many other optimization problems can also be expressed in a least squares form, by either minimizing energy or maximizing entropy.

History

On New Year's Day in 1801, the Italian astronomer Giuseppe Piazzi discovered the asteroid Ceres. He was able to track its path for 40 days. In the course of the year, many scientists tried to estimate the trajectory on the basis of Piazzi's observations (solving Kepler's nonlinear equations of motion is very difficult). Most evaluations were useless; the only calculation precise enough to allow Zach, a German astronomer, to recover Ceres at the end of the year, was that of 24-year-old Carl Friedrich Gauss (the fundamentals of his approach had already been accomplished by him in 1795, when he was still 18 years old). But his method of least squares was not published until 1809, when it appeared in volume two of his work on celestial mechanics, Theoria Motus Corporum Coelestium in sectionibus conicis solem ambientium. The French Adrien-Marie Legendre independently developed the same method in 1805.

In 1829 Gauss was able to state the reason for this procedure's outstanding success: The method of least squares is simply optimal in many respects. The precise argument is known as the Gauss-Markov theorem.

Formulation of the problem

Suppose that the data set consists of the points $(x_i, y_i)$ with $i = 1, 2, \dots, n$ . We want to find a function $f$ such that $f(x_i)\approx y_i.$

To attain this goal, we suppose that the function f is of a particular form containing some parameters which need to be determined. For instance, suppose that it is quadratic, meaning that $f(x)=ax^2+bx+c$ , where $a$ , $b$ and $c$ are not yet known. We now seek the values of $a$ , $b$ and $c$ that minimize the sum of the squares of the residuals ( $S$ ):

S = \sum_{i=1}^n (y_i - f(x_i))^2.

This explains the name least squares.

Solving the least squares problem

In the above example, f is linear in the parameters a, b and c. The problem simplifies considerably in this case and essentially reduces to a system of linear equations. This is explained in the article on linear least squares.

The problem is more difficult if f is not linear in the parameters to be determined. We then need to solve a general (unconstrained) optimization problem. Any algorithm for such problems, like Newton's method and gradient descent, can be used. Another possibility is to apply an algorithm that is developed especially to tackle least squares problems, for instance the Gauss-Newton algorithm or the Levenberg-Marquardt algorithm.

Least squares and regression analysis

In regression analysis, one replaces the relation

f(x_i)\approx y_i

by

f(x_i) = y_i + \varepsilon_i,

where the noise term ε is a random variable with mean zero. Note that we are assuming that the $x$ values are exact, and all the errors are in the $y$ values. Again, we distinguish between linear regression, in which case the function f is linear in the parameters to be determined (e.g., f(x) = ax² + bx + c), and nonlinear regression. As before, linear regression is much simpler than nonlinear regression. (It is tempting to think that the reason for the name linear regression is that the graph of the function f(x) = ax + b is a line. Fitting a curve f(x) = ax² + bx + c, estimating a, b, and c by least squares, is an instance of linear regression because the vector of least-square estimates of a, b, and c is a linear transformation of the vector whose components are f(x_i) + ε_i.)

One frequently estimates the parameters (a, b and c in the above example) by least squares: those values are taken that minimize the sum S. The Gauss–Markov theorem states that the least squares estimates are optimal in a certain sense, if we take f(x) = ax + b with a and b to be determined and the noise terms ε are independent and identically distributed (see the article for a more precise statement and less restrictive conditions on the noise terms).

Least squares estimation for linear models is notoriously non-robust to outliers. If the distribution of the outliers is skewed, the estimates can be biased. In the presence of any outliers, the least squares estimates are inefficient and can be extremely so. When outliers occur in the data, methods of robust regression are more appropriate.

References

Abdi, H. "[1] (2003). Least-squares. In M. Lewis-Beck, A. Bryman, T. Futing (Eds): Encyclopedia for research methods for the social sciences. Thousand Oaks (CA): Sage. pp. 792-795.]".

External links

http://www.physics.csbsju.edu/stats/least_squares.html
Zunzun.com - Online curve and surface fitting
http://www.orbitals.com/self/least/least.htm
Least squares on PlanetMath

cs:Metoda nejmenších čtverců de:Methode der kleinsten Quadrate fr:Méthode des moindres carrés gl:Mínimos cadrados nl:Kleinste-kwadratenmethode pt:Método dos mínimos quadrados ru:Метод наименьших квадратов su:Kuadrat leutik sv:Minstakvadratmetoden vi:Bình phương tối thiểu zh:最小二乘法

This page uses Creative Commons Licensed content from Wikipedia (view authors).