ARLS Automatically Regularized Least Squares

ARLS is intended for solving ill-conditioned linear systems of any shape or size. It is an alternative to the MATLAB A\b.

Usage

x=arls(A,b)

where A is a matrix of size m by n, where m can be less than,

or equal to, or more than n, and b is of length m.

Resulting x is of length n.

ARLS is intended for solving ill-conditioned linear

systems of any shape or size.

By ill-conditioned, we mean that the solution is

unacceptably affected by insignificant changes in b.

Such systems often arise, for example, in inverse problems

in which the analyst is trying to reverse the effects of

natural smoothing processes such as heat dissipation

or the effects of indirect sensing.

ARLS generally tolerates singularity (zero or near zero

singular values) and other intrinsic difficulties

such as linear dependencies between rows.

If for any reason ARLS' algorithm fails a default

regularized solution is still returned.

There are no error exits in ARLS.

Method

ARLS is a new regularized solution method based on the

notion popularized by P C Hansen as the "Picard Condition"

which suggests that when the solution is represented as an

orthogonal expansion, then the coefficients of the

expansion should decline if a well-behaved solution is to

be expected.

Using the Singular Value Decomposition, A=USV', then

Ax=b becomes:

USV'x=b

which gives x=V*inv(S)*U'*b

or x=V*P

where P is a set of coefficients of an orthogonal

expansion of x in terms of the columns of V.

ARLS works by finding the smallest Tikhonov regularization

parameter, lambda, that makes P decline.

Due to erratic behavior that generally shows up in P

we use a low-degree polynomial fit to P instead of using

P directly. And we work with the logarithm of P rather

than P tself in order to better see the behavior of the

smallest elements of P.

We also offer two constrained solvers which build on ARLS:

-- arlsnn(A,b) constrains the solution to be non-negative.

-- arlsrise(A,b) constrains the solution to be non-decreasing.

Note: Version 1.0 of ARLS was published as a contributed file to Python's math library. This Version 2.0 is a major redo.

Contact: [e-mail]