Forgotten Password?

Or login with:

  • Facebook
  • Google
  • Yahoo

Least Squares

Curve fitting, least squares, optimization


Consider a series of \inline N given data points in \inline (d + 1)-dimensional space, \inline (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N), where \inline x_i := (x_i^1, x_i^2, \ldots, x_i^d) is a vector, for all \inline i = 1, 2, \ldots, N. Define a function \inline f : \mathbb{R}^{k + d} \to \mathbb{R} through

where \inline \psi_j : \mathbb{R} \to \mathbb{R} and \inline \theta_j : \mathbb{R}^d \to \mathbb{R} are given functions, for all \inline j = 1, 2, \ldots, k. Also, define the function \inline S_f : \mathbb{R}^k \to \mathbb{R} as the sum of squared residuals:

The method of least squares fitting refers to finding the parameters \inline (\alpha_1^*, \alpha_2^*, \ldots, \alpha_k^*) which are the solution to the following unconstrained optimization problem:

After solving this problem, the function \inline f^* : \mathbb{R}^d \to \mathbb{R} which provides the best fit, in the least-squares sense, is given by:

This general framework allows us to classify the different types of regression, as follows:

  • When \inline d = 1 the method is known as univariate regression, while if \inline d > 1 we have multivariate regression.
  • Provided that all the functions \inline \psi_1, \psi_2, \ldots, \psi_k are linear, the method is called linear regression, otherwise it is known as nonlinear regression.
  • Also, based on the type of the functions \inline \phi_1, \phi_2, \ldots, \phi_k we may have polynomial regression, regression by orthogonal polynomials, and so on.

Solving The Problem

Since the sum of residuals function \inline S_f is convex on its entire domain, a necessary and sufficient condition for a tuple of parameters \inline (\alpha_1^*, \alpha_2^*, \ldots, \alpha_k^*) to be a solution to the above optimization problem is that

which can also be written as the system of (possibly nonlinear) equations:

Let us fix some value of \inline j \in \{1, 2, \ldots, k\} and calculate \inline \displaystyle \frac{\partial S_f}{\partial \alpha_j}. We have:

Therefore, the system of equations whose solution is the tuple of optimal parameters \inline (\alpha_1^*, \alpha_2^*, \ldots, \alpha_k^*) can explicitly be written as:

In the case of linear regression in small dimensions, it is possible to solve this system directly, using algebra. Generally, however, we should use numerical root-finding techniques to find the optimal parameters.
Lucian Bentea (September 2008)


Last Modified: 23 Sep 08 @ 14:55     Page Rendered: 2022-03-14 15:50:24