Least Squares Problem: Linear and Nonlinear Regression Methods
The least squares problem is a fundamental mathematical approach used to find the best-fitting curve for a given set of data points. The core objective is to minimize the sum of the squares of the residuals—the differences between the observed data and the values predicted by a model. By setting the gradient of this sum to zero, we can determine the parameters that provide the most accurate fit.
For a model with m parameters, the minimum is found by solving m gradient equations. If the residual is defined as ri = yi - f(xi, β), the gradient equations are expressed as -2 ∑ ri ∂f(xi, β) / ∂βj = 0 for j = 1, ..., m. While these equations apply to all least squares problems, the specific expressions for the model and its partial derivatives vary depending on the problem type.
ไม่มีภาพประกอบ
Linear Least Squares (LLSQ)
A regression model is considered linear when it consists of a linear combination of parameters. In this case, the model is expressed as f(x, β) = ∑ βj ϕj(x), where ϕj is a function of the independent variable x.
To solve for the parameters in a linear system, we use matrices. By letting Xij = ϕj(xi) and organizing the independent and dependent variables into matrices X and Y, the loss function L(D, β) is calculated as the squared norm of the difference: ‖Y - Xβ‖2. This expands to YTY - 2YTXβ + βTXTXβ.
The gradient of this loss is -2XTY + 2XTXβ. By setting this gradient to zero, we derive the solution for the parameter vector β:
- Normal Equation:
XTY = XTXβ - Closed-form Solution:
β̂ = (XTX)-1XTY = X+Y
Here, X+ represents the pseudoinverse of matrix X, allowing for a direct calculation of the optimal parameters.
Nonlinear Least Squares (NLLSQ)
Unlike linear models, nonlinear least squares problems generally lack a closed-form solution. Instead, they require numerical algorithms to iteratively refine parameter values. This process begins with initial parameter guesses, which are then updated using a shift vector (Δβ) in the formula βjk+1 = βjk + Δβj, where k denotes the iteration number.
Many algorithms linearize the model at each step using a first-order Taylor series expansion. This introduces the Jacobian (J), a matrix of partial derivatives that changes with each iteration. The residuals are then expressed as ri = Δyi - ∑ Jij Δβj.
To minimize the sum of squares, the gradient is set to zero, resulting in the normal equations: ∑ ∑ Jij Jik Δβk = ∑ Jij Δyi. In matrix notation, this is written as:
(JTJ) Δβ = JT Δy
These equations form the basis of the Gauss–Newton algorithm, a widely used method for solving nonlinear regression problems.
ไม่มีภาพประกอบ
Key Facts
- Linearity: A model is linear if its partial derivatives are constant or depend only on the independent variable.
- Solutions: LLSQ provides a unique, direct solution; NLLSQ typically requires iterative approximation.
- Initial Values: NLLSQ requires starting parameter values, whereas LLSQ does not.
- Convergence: LLSQ is globally concave and always converges; NLLSQ may suffer from non-convergence.
- Bias: LLSQ yields unbiased estimates (if errors are uncorrelated with predictors), while NLLSQ estimates are generally biased.
Comparison of Linear and Nonlinear Least Squares
| Feature | Linear Least Squares (LLSQ) | Nonlinear Least Squares (NLLSQ) |
|---|---|---|
| Parameter Form | Linear combination (e.g., Xβ) |
Functions (e.g., β2, eβx) |
| Solution Method | Direct (Closed-form) | Iterative (Numerical) |
| Initial Guesses | Not required | Required |
| Convergence | Guaranteed (Globally concave) | Possible non-convergence |
| Uniqueness | Unique solution | Potential for multiple minima |
| Estimation Bias | Unbiased (under specific conditions) | Generally biased |
Frequently Asked Questions
What is the main difference between LLSQ and NLLSQ?
The primary difference lies in how the parameters appear in the model. In LLSQ, the model is a linear combination of parameters. In NLLSQ, parameters appear within nonlinear functions, such as exponents or powers, meaning the partial derivatives depend on the parameters themselves.
Why does NLLSQ require initial values?
Because NLLSQ lacks a closed-form solution, it relies on iterative numerical algorithms. These algorithms need a starting point (initial values) to begin the process of successive approximation to find the minimum sum of squares.
What is the Jacobian in the context of nonlinear least squares?
The Jacobian is a matrix containing the first-order partial derivatives of the model function with respect to the parameters. It is used to linearize the model during each iteration of algorithms like Gauss-Newton.
Can NLLSQ fail to find a solution?
Yes. Non-convergence is a common phenomenon in NLLSQ, where the algorithm fails to find a minimum. This is in contrast to LLSQ, which is globally concave and does not face this issue.
What is the Gauss-Newton algorithm?
The Gauss-Newton algorithm is a numerical method used to solve NLLSQ problems. It iteratively solves the normal equations (JTJ) Δβ = JT Δy to refine the parameter estimates until a convergence criterion is met.