| The Least Squares Problem You will find two sections:
 | The unconstrained LSQ-Problem: |
min f(x), f(x) = sumk K ( F(tk) - Phi(x,tk))2
n=dim(x), K=number of data points The picture shows you the problem of fitting an ellipse through 40 scattered data points in the plane in the sense of minimizing the sum of squared orthogonal distances, a so called orthogonal regression problem.  If f is quadratic in the unknowns we have a linear least squares problem (Phi is linear in the unkowns). This can be reduced in different ways to the solution of a system of linear equations. Since quite often the solution is very sensitive to roundoff errors, much care must be taken in doing this. The singular value decomposition is the ultimate tool here. Often use of the QR-(Householder)-decomposition suffices. We provide you with several software solutions for this. | f quadratic, n medium |
 | netlib/lawson-hanson | solving the linear least squares problem using the singular value decomposition; this collection of routines and sample drivers includes in particular code for the solution of the nonnegative and the bound- constrained LS problems, of the problems arising in spline curve fitting, in least distance programming, as well as a demonstration of singular value analysis, f77&f90 | | lapack/DGELSS
C-version | solves the linear least squares problem with several right hand sides, using the singular value decomposition. Matrix may be rank deficient. | | toms/782 | Computing Rank-Revealing {QR} Factorizations of Dense Matrices | | UTV | Computing Rank-Revealing UTV decompositions of dense matrices | | QRUP | QR factorization with row and column and rank-1 updates, Gram-Schmidt method | | toms/686 | updating the QR factorization , Householder/Givens method |
Because of the bad fill in properties of orthogonal transformations the large scale linear least squares problem is much harder. | f quadratic, n large |
| SPARSE-QR | LS solution using a sparse QR decomposition, C/C++ | | ARPACK | large sparse eigenvalue package, includes templates for SVD | | PROPACK | large sparse eigenvalue/SVD package (Matlab, f77) | | netlib/svdpack | using different methods to compute leading singular pairs of sparse matrix, both f77 and C versions | | LSQR | an iterative solver for the large, sparse, possibly ill-conditioned linear least squares problem (f77, C, Matlab) | | Meschach | numerical linear algebra in C, original source |
The nonlinear least squares problem occurs frequently in practice. If the data can be fitted well, then this is not much harder than a linear problem and special methods are quite successful. | f general, optimal f-value small (a "good fit"-problem) |
| LMDER | The MINPACK Levenberg-Marquardt code, exact Jacobian, driver | | LMDIF | The MINPACK Levenberg-Marquardt code, Jacobian by finite differences, driver | | LMDIF_C | C-version of LMDIF (includes driver) | | lm_f90 | contains a f90-translation of LMDER/LMDIF above | | netlib/opt/varpro | separable problem, where Phi depends linearly on a part of the parameters (e.g. sum_i a_i*exp(b_i*t)). These can be treated in a special way, leaving a nonlinear problem of reduced dimension. | | dqed | self-contained version of Hanson&Krogh's netlib-code | | codelib/nlscon | Gauss-Newton method with damping, also for nonlinear equality constraints, Jacobian may be singular | | ELSUNC | Gauss-Newton method, analytic/numerical Jacobian, paper here | | ELSUNC_f90 | f90-version and driver |
If the optimal fit is "bad", then methods based on linearization of Phi are not successful. In this case either use a general minimizer or one of these (combination of Gauss-Newton with quasi-Newton for the second order derivatives of Phi): | f general, optimal f-value possibly large (bad fit) |
| f from orthogonal regression |
| Total Least Squares |
| f from autoregressive model |
| ARfit | parameter estimation, checking, analyzing eigenmodes (Matlab) |
| f from maximum-likelihood estimation, nonlinear model |
| The constrained LSQ-Problem: |
min f(x), f as above, subject to h(x)=0, g(x)>=0,
n=dim(x), m=dim(g), p=dim(h). | f is quadratic or general in x; bound constraints on x |
| netlib/lawson-hanson | f quadratic, nonnegativity and bound constraints, f77&f90 | | ELSUNC | f general, Gauss-Newton method, analytic/numerical Jacobian, paper here | | ELSUNC_f90 | f90-version and driver | | port/n2fb | f general needs other routines from port library, numerical gradients, use n2gb for exact gradients | | port/nsfb | explicit input of model functions, numerical gradients, use nsgb for exact gradients | | SLS | f quadratic. large, sparse problem; nonnegativity or bound constraints (multifrontal sparse QR, corrected seminormal equations, Matlab) |
| f is quadratic in x; g,h linear (the linearly constrained least squares problem) |
| dqed | self-contained version of Hanson&Krogh's netlib-code, general linear constraints. | | clsSolve | Two hybrid BFGS-Gauss-Newton methods, Gauss-Newton with subspace minimization, and Huschen's method. | | lapack/DGGLSE
C-version | linear equality constraints | | toms/587 | hard/soft equality and inequality constraints | | QHOPDM | large, sparse problem; linear constraints (QP solver whose objective function can easily be rewritten for LS problem, extended MPS input) | | lapack/DGGGLM
C-version | general linear model (solving f=||y||, h=Ax+By-d, weighted LS for nonsingular square B) |
| nonlinear constraints, optimal f-value small |
| codelib/nlscon | damped Gauss-Newton with use of restricted pseudo- inverse for singular cases; with the additional feature of nonlinear equality constraints only | | ENLSIP | Gauss-Newton method, analytic/numerical Jacobians, paper here | | gaussfit | own modeling language, documentation, testexamples, C |
| |
