Discrete linear L ₁ approximation

In the discrete linear l ₁ approximation in mathematics a given real-valued function is approximated by simpler continuous functions in discrete points with respect to the l ₁ norm . ${\displaystyle f}$

Problem

Are given

• a fixed finite set that lies in a real interval ${\displaystyle X_{m}=\{x_{1},x_{2},\ldots ,x_{m}\}}$ ${\displaystyle I}$
• a real-valued function defined on : ${\displaystyle f}$ ${\displaystyle X_{m}}$ ${\displaystyle f:X_{m}\rightarrow \mathbb {R} }$
• ${\displaystyle n}$continuous real-valued functions with which are defined on the interval . ${\displaystyle \Phi _{1},\Phi _{2},\ldots ,\Phi _{n}}$ ${\displaystyle n\leq m}$ ${\displaystyle I}$

The function should be approximated as well as possible on the set in the sense of the l ₁ norm by a linear combination of the continuous functions . That means, that vector is searched for among the vectors for which the following applies: ${\displaystyle f}$ ${\displaystyle X_{m}}$ ${\displaystyle \Phi _{i}}$ ${\displaystyle a=(a_{1},a_{2},\ldots ,a_{n})^{T}}$ ${\displaystyle a^{*}}$

${\displaystyle \sum _{i=1}^{m}\left|f(x_{i})-L(a^{*},x_{i})\right|\leq \sum _{i=1}^{m}\left|f(x_{i})-L(a,x_{i})\right|}$

With

${\displaystyle L(a,x):=L(a_{1},a_{2},\ldots a_{n};x):=\sum _{j=1}^{n}a_{j}\Phi _{j}(x)}$

and ${\displaystyle a_{j}\in \mathbb {R} .}$

Underlies the l ₁ norm, a special case of L _p -norm with which also known amount sum norm is known: ${\displaystyle p=1}$

${\displaystyle \|x\|_{1}:=\sum _{i=1}^{n}|x_{i}|}$

The sum of the error amounts in the individual points is thus minimized. ${\displaystyle x_{i}}$

Formulation as a linear optimization problem

With a suitable reformulation, the problem can be represented as a linear optimization problem and solved with the appropriate methods, such as the simplex method .

With the abbreviations

${\displaystyle f_{n}:=f(x_{i})}$

${\displaystyle \Phi _{ji}:=\Phi _{j}(x_{i})}$

${\displaystyle r_{i}=r_{i}(a):=f(x_{i})-L(a,x_{i})}$

the problem can be written as:

Minimize ${\displaystyle z=\sum _{i=1}^{m}|r_{i}(a)|}$

under the constraints

${\displaystyle f_{i}=L(a,x_{i})+r_{i}}$   for     and ${\displaystyle i=1,2,\ldots ,m}$

${\displaystyle a\in \mathbb {R} ^{n}.}$

In order to be able to solve the problem with the simplex method, the objective function has to be linearized. To do this you put

${\displaystyle r_{i}=u_{i}-v_{i}}$   For   ${\displaystyle i=1,2,\ldots ,m}$

with and finally receives a linear optimization problem that can be solved with the simplex method: ${\displaystyle u_{i},v_{i}\geq 0}$

 

Minimize ${\displaystyle z=\sum _{i=1}^{m}(u_{i}+v_{i})}$

under the constraints

${\displaystyle f_{i}=\sum \limits _{j=1}^{n}a_{j}\Phi _{ji}+u_{i}-v_{i}}$   For   ${\displaystyle i=1,2,\ldots ,m}$

${\displaystyle u_{i},v_{i}\geq 0}$

${\displaystyle a_{j}}$   free variable for   ${\displaystyle j=1,2,\ldots ,n}$

 

Non-uniqueness of solutions

The solution is not always clear, as the following example shows:

Be so ${\displaystyle X_{m}=X_{2}=\{0,1\}}$ ${\displaystyle m=2,}$

${\displaystyle f(x)={\begin{cases}1,&{\text{wenn}}\;x=0\\-1,&{\text{wenn}}\;x=1\end{cases}}}$

and so ${\displaystyle \Phi _{1}(x)=1,}$ ${\displaystyle n=1.}$

Then every function has a best approximation, so there are any number of solutions. ${\displaystyle L(a,x)=a_{1}}$ ${\displaystyle -1\leq a_{1}\leq +1}$

Use the l ₁ approximation

Ian Barrodale observed the following property in L ₁ -approximation and the analysis of data (see literature): If large measurement errors occur in a few of the measured values ​​in a series of measurements, then these poor values ​​are in many cases recognized by an optimal solution of the l ₁ approximation and ignored. This means that there is a much larger error in relation to the "almost correct" values

${\displaystyle |f(x_{i})-L(a^{*},x_{i})|.}$

In contrast, such "large measurement errors" are not noticeable in the case of a l ₂ approximation or an l _∞ approximation and worsen the overall solution. Barrodale therefore recommends first using a l ₁ approximation to identify the bad values ​​("wild points") and then to omit them or to replace them with better values. An approximation could then be made in the desired norm.

literature

• Nabih N. Abdelmalek: Linear l ₁ -approximation for a discrete point set and l ₁ -solutions of overdetermined linear equations. , Journal of the ACM 18 (1971), pp. 41-47
• Nabih N. Abdelmalek: On the discrete linear l ₁ -approximation and l ₁ -solutions of overdetermined linear equations. , Journal of Approximation Theory 11 (1974), pp. 38-53
• Nabih N. Abdelmalek: An efficient method for the discrete linear l ₁ -approximation problem. , Mathematics of Computation 29 (1975) pp. 844-855
• Ian Barrodale: Approximation in l ₁ and l _∞ norms by linear programming. , Ph.D. thesis, University of Liverpool, 1967
• Ian Barrodale: L ₁ -approximation and the analysis of data. , Applied Statistics 17 (1968), pp. 51-57
• Ian Barrodale: On computing best l ₁ approximations , Approximation Theory (A. Talbot, editor), Academic Press 1970, p 205-215
• Ian Barrodale, Frank DK Roberts: Applications of mathematical programming to l _p approximation , Nonlinear Programming (JB Rosen, OL Mangasarian, K. Ritter, Editors), Academic Press 1970, pp. 447-464
• Ian Barrodale, Frank DK Roberts: An improved algorithm for discrete linear l ₁ -approximation. , University of Wisconsin, MRC Report No. 1172, 1970
• Ian Barrodale, Andrew Young: Algorithms for best l ₁ and l _∞ linear approximations on a discrete set , Numerische Mathematik 8 (1966), pp. 295-306
• G. Croucher: Best l ₁ and l _∞ linear approximations on a discrete set , 1971, M.Sc. thesis, Birkbeck College, London University
• PD Robers, A. Ben-Israel: An interval programming algorithm for discrete linear l ₁ -approximation problems. , Journal of Approximation Theory 2 (1969), pp. 323-326
• Karl H. Usow: On l ₁ approximation II: Computation for discrete functions and discretization effects. , SIAM Journal Numerical Analysis 4 (1967), pp. 233-244

Web links

• K. Spyropuolos, E. Kiountouzis, A. Young: Discrete approximation in the L ₁ norm , The Computer Journal 16 (1972) 180-186 (accessed December 28, 2011; PDF; 3.9 MB)