A tree for site navigation will open here if you enable JavaScript in your
browser.
The Least Squares Problem
You will find two sections:The unconstrained LSQ-Problem The constrained LSQ-Problem
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
toms/853
Modification of LAPACK's xGELSY; more efficient for low-rank 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, parallel versions
(f77,
C++)
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
lm_java
Levenberg-Marquardt in Java (needs JAMA)
minpack_java
Another Java translation of LMDER/LMDIF
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
dqed_f90
f90 version of Hanson&Krogh's netlib-code, related programs
NLSQ_ERR
Gauss-Newton method with adaptive trust region strategy and error oriented
convergence criterion
(Matlab)
NLSQ_RES
Gauss-Newton method with adaptive trust region strategy and residual oriented
convergence
criterion (Matlab)
LMFnlsq
Fletcher's modification of Levenberg-Mar
quardt (Matlab)
nlscon
Gauss-Newton method with damping, also for nonlinear equality constraints, Jacobian may be singular, f77/Matlab
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)
toms/573 single precision, double precision
NL2SOL by Dennis, Gay, Welsch
port/n2f
newer version, needs other routines from port library,
numerical gradients; n2g for exact gradients
port/nsf
explicit input of model functions, numerical gradients; nsg for exact gradients
f90-translations
of the above software
LEVM
for complex functions, Windows executable, documentation
HBN's software
Marquardt's and a hybrid method (Matlab)
LEVMAR
Unconstrained and linearly constrained Levenberg-Marquardt implementations
(GPL,
C/C++)
Expfit
HBN's multiexponential fitting package (Matlab)
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
netlib/opt/nlr
nonlinear regression code by Bunch, Gay, and Welsch
toms version
Fastfit
efficient maximum-likelihood estimation of various distribution, Matlab
MILES
efficient maximum-likelihood estimation of various distributions, Matlab
Pattern Research software
Matlab toolboxes for Hidden Markov Modelling and more
S-est
computes S-estimate, Matlab, uses ASA
CMregr
computes constrained M-estimate, Matlab
Regularization of discrete ill-posed problems
MOOReTools
Modular Object Oriented Regularization Tools (Matlab)
Regularization
Tools
Matlab package for analysis and solution of discrete ill-posed
problems
Restore
Tools
Object Oriented Matlab Package for Image Restoration
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
NNLS_C
C-version of Lawson&Hanson nonnegative LS
NNLS_JAVA
Java-version of Lawson&Hanson nonnegative LS
TSNNLS
Sparse nonnegative least squares, uses LAPACK, BLAS, TAUCS, LSQR (C)
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
BVLS
linear L1, L2, or Linf problems, active set method
BVLS.f90
f90 version of BVLS by Alan Miller
SLS
f quadratic. large, sparse problem; nonnegativity or bound constraints
(multifrontal sparse QR, corrected seminormal equations, Matlab)
BCLS
f quadratic. bound constraints, regularization term, only matrix multiplies needed, speedup with fast BLAS (C)
lsNTF
Computing nonnegative tensor factorizations; needs Matlab tensor toolbox (Matlab)
f is quadratic in x; g,h linear
(the linearly constrained least squares problem)
LEVMAR
Unconstrained and linearly constrained Levenberg-Marquardt implementations (GPL,
C/C++)
dqed
self-contained version of Hanson&Krogh's netlib-code, general linear
constraints.
LSE
Computes LS solution of Ax~=b subject to Cx=d, C may be rank-deficient, Matlab
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)
UNIMOD
Unimodal, monotonic LS regression (Matlab)
L2WPMA
Weighted monotonic least squares
nonlinear constraints, optimal f-value small
SDLS
a Matlab package for solving conic least-squares problems
nlscon
damped Gauss-Newton with use of restricted pseudo-
inverse for singular cases; with the additional feature
of nonlinear equality constraints only.
f77/Matlab
ENLSIP
Gauss-Newton method, analytic/numerical Jacobians, paper
here
gaussfit
own modeling language, documentation, testexamples, C
