Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 L1Solve

Source Notebook

Solve the linear least absolute value problem

Contributed by: Jan Mangaldan

ResourceFunction["L1Solve"][m,b]

finds an x that solves the linear least absolute value problem for the matrix equation m.x==b.

Details

The linear least absolute value problem is also referred to as linear ℓ1 norm minimization.
ResourceFunction["L1Solve"][m,b] gives a vector x that minimizes Norm[m.x-b,1].
All entries in the matrix m and the vector b must be real numbers.
SparseArray objects can be used in ResourceFunction["L1Solve"].
ResourceFunction["L1Solve"] takes the same options as LinearProgramming.

Examples

Basic Examples (1) 

Solve a simple least absolute value problem:

In[1]:=
ResourceFunction["L1Solve"][{{1, 1}, {1, 2}, {1, 3}}, {7, 7, 8}]
Out[1]=

Scope (2) 

Create a 4×3 matrix, and b is a length-4 vector:

In[2]:=
m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; b = {1, 2, 4, 8};

Use exact arithmetic to find a vector x that minimizes :

In[3]:=
ResourceFunction["L1Solve"][m, b]
Out[3]=

Use machine arithmetic:

In[4]:=
ResourceFunction["L1Solve"][N[m], b]
Out[4]=

Use 20-digit-precision arithmetic:

In[5]:=
ResourceFunction["L1Solve"][N[m, 20], b]
Out[5]=

Use a sparse matrix:

In[6]:=
s = SparseArray[{{i_, j_} /; j == i + 1 -> N[i]}, {10, 10}]; ResourceFunction["L1Solve"][N[s], {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
Out[7]=

Applications (4) 

Here is some data:

In[8]:=
data = {{0, 1}, {1, 0}, {3, 2}, {5, 4}};

Find the line that best fits the data in the least absolute deviation sense:

In[9]:=
line = ResourceFunction["L1Solve"][DesignMatrix[data, {1, x}, x], data[[All, -1]]] . {1, x}
Out[9]=

Find the quadratic that best fits the data in the least absolute deviation sense:

In[10]:=
parabola = ResourceFunction["L1Solve"][DesignMatrix[data, {1, x, x^2}, x], data[[All, -1]]] . {1, x, x^2}
Out[10]=

Show the data with the two curves:

In[11]:=
Show[ListPlot[data, PlotStyle -> Red], Plot[{line, parabola}, {x, 0, 5}]]
Out[11]=

Properties and Relations (2) 

For a vector b, L1Solve is equivalent to ArgMin[Norm[m.x-b,1],x]:

In[12]:=
m = {{1, 2}, {3, 4}, {1, 1}}; x = {x1, x2}; b = {1, 2, 3};
In[13]:=
ResourceFunction["L1Solve"][m, b] == ArgMin[Norm[m . x - b, 1], x]
Out[13]=

Create a 5×2 matrix and a length-5 vector:

In[14]:=
m = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}}; b = {1, 2, 4, 3, 5};

Solve the least absolute value problem:

In[15]:=
a = ResourceFunction["L1Solve"][m, b]
Out[15]=

This is the minimizer of :

In[16]:=
Show[Plot3D[Norm[m . {x, y} - b, 1], {x, -2, 2}, {y, 0, 2}, MeshFunctions -> {#3 &}, ColorFunction -> (Hue[.65 (1 - #3)] &)], Graphics3D[{Red, PointSize[0.05], Point[{a[[1]], a[[2]], Norm[m . a - b]}]}]]
Out[16]=

It also gives the coefficients for the line with least absolute deviation from the points:

In[17]:=
Show[ListPlot[{{1, 1}, {2, 2}, {3, 4}, {4, 3}, {5, 5}}], Plot[a . {1, x}, {x, 1, 5}]]
Out[17]=

Version History

  • 1.0.0 – 06 January 2021

Source Metadata

  • Citation:
    • Barrodale, I., Young, A., "Algorithms for Best L^1 and L^∞ Linear Approximations on a Discrete Set." Numerische Mathematik, vol. 8, 295–306, 1966.
      DOI: 10.1007/BF02162565
    • Charnes A., Cooper W.W., Ferguson R.O., "Optimal Estimation of Executive Compensation by Linear Programming." Management Science, vol. 1, no. 2, 138-151, 1955.
      DOI: 10.1287/mnsc.1.2.138
    • Watson G.A., "Approximation in normed linear spaces." Journal of Computational and Applied Mathematics, vol. 121, 1-36, 2000.
      DOI: 10.1016/S0377-0427(00)00333-2

Related Resources

License Information