naginterfaces.library.fit.glin_​l1sol

naginterfaces.library.fit.glin_l1sol(a, b, toler=0.0)

glin_l1sol calculates an $l_1$ solution to an overdetermined system of linear equations.

For full information please refer to the NAG Library document for e02ga

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/e02/e02gaf.html

Parameters

afloat, array-like, shape $(m+2,\text{nplus2})$

$a[\text{i}-1,\text{j}-1]$ must contain $a_{\text{i}\text{j}}$, the element in the $\text{i}$th row and $\text{j}$th column of the matrix $A$, for $\text{j}=1,2,\dots ,n$, for $\text{i}=1,2,\dots ,m$. The remaining elements need not be set.

bfloat, array-like, shape $\left(m\right)$

$b[\text{i}-1]$ must contain $b_{\text{i}}$, the $\text{i}$th element of the vector $b$, for $\text{i}=1,2,\dots ,m$.

tolerfloat, optional

A non-negative value. In general $toler$ specifies a threshold below which numbers are regarded as zero. The recommended threshold value is ${ϵ}^{2/3}$ where $ϵ$ is the machine precision. The recommended value can be computed within the function by setting $toler$ to zero. If premature termination occurs a larger value for $toler$ may result in a valid solution.

Returns

afloat, ndarray, shape $(m+2,\text{nplus2})$

Contains the last simplex tableau generated by the simplex method.

bfloat, ndarray, shape $\left(m\right)$

The $\text{i}$th residual $r_{\text{i}}$ corresponding to the solution vector $x$, for $\text{i}=1,2,\dots ,m$.

xfloat, ndarray, shape $\left(\text{nplus2}\right)$

$x[\text{j}-1]$ contains the $\text{j}$th element of the solution vector $x$, for $\text{j}=1,2,\dots ,n$. The elements $x\left[n\right]$ and $x[n+1]$ are unused.

residfloat

The sum of the absolute values of the residuals for the solution vector $x$.

irankint

The computed rank of the matrix $A$.

iteraint

The number of iterations taken by the simplex method.

Raises

NagValueError

(errno $2$)

Premature termination due to rounding errors. Try using larger value of $toler$: $toler=⟨value⟩$.

(errno $3$)

On entry, $\text{nplus2}=⟨value⟩$ and $m=⟨value⟩$.

Constraint: $3\le \text{nplus2}\le m+2$.

(errno $3$)

On entry, $\text{nplus2}=⟨value⟩$.

Constraint: $\text{nplus2}\ge 3$.

Warns

NagAlgorithmicWarning

(errno $1$)

An optimal solution has been obtained, but may not be unique.

(errno $4$)

More than $1000\ast n$ iterations were performed. glin_l1sol has terminated without calculating a solution. The output data from the function is as computed on the last good iteration. Consider increasing the value of $toler$. Alternatively, $A$ may be ill conditioned—try scaling its columns.

Notes

Given a matrix $A$ with $m$ rows and $n$ columns $(m\ge n)$ and a vector $b$ with $m$ elements, the function calculates an $l_1$ solution to the overdetermined system of equations

$$Ax=b\text{.}$$

That is to say, it calculates a vector $x$, with $n$ elements, which minimizes the $l_1$ norm (the sum of the absolute values) of the residuals

$$r\left(x\right)=\sum _{i=1}^m\left|r_i\right|\text{,}$$

where the residuals $r_i$ are given by

$$r_i=b_i-\sum _{j=1}^n{a}_{ij}{x}_j\text{,}i=1,2,\dots ,m\text{.}$$

Here $a_{ij}$ is the element in row $i$ and column $j$ of $A$, $b_i$ is the $i$th element of $b$ and $x_j$ the $j$th element of $x$. The matrix $A$ need not be of full rank.

Typically in applications to data fitting, data consisting of $m$ points with coordinates $(t_i,y_i)$ are to be approximated in the $l_1$ norm by a linear combination of known functions ${\varphi }_j\left(t\right)$,

$${\alpha }_1{\varphi }_1\left(t\right)+{\alpha }_2{\varphi }_2\left(t\right)+\cdots +{\alpha }_n{\varphi }_n\left(t\right)\text{.}$$

This is equivalent to fitting an $l_1$ solution to the overdetermined system of equations

$$\sum _{j=1}^n{\varphi }_j\left(t_i\right){\alpha }_j=y_i\text{,}i=1,2,\dots ,m\text{.}$$

Thus if, for each value of $i$ and $j$, the element $a_{ij}$ of the matrix $A$ in the previous paragraph is set equal to the value of ${\varphi }_j\left(t_i\right)$ and $b_i$ is set equal to $y_i$, the solution vector $x$ will contain the required values of the ${\alpha }_j$. Note that the independent variable $t$ above can, instead, be a vector of several independent variables (this includes the case where each ${\varphi }_i$ is a function of a different variable, or set of variables).

The algorithm is a modification of the simplex method of linear programming applied to the primal formulation of the $l_1$ problem (see Barrodale and Roberts (1973) and Barrodale and Roberts (1974)). The modification allows several neighbouring simplex vertices to be passed through in a single iteration, providing a substantial improvement in efficiency.

References

Barrodale, I and Roberts, F D K, 1973, An improved algorithm for discrete $l_1$ linear approximation, SIAM J. Numer. Anal. (10), 839–848

Barrodale, I and Roberts, F D K, 1974, Solution of an overdetermined system of equations in the $l_1$ -norm, Comm. ACM (17(6)), 319–320