# Diskrete lineare L1-Approximation

Bei der diskreten linearen l$_1$-Approximation wird in der Mathematik eine vorgegebene reellwertige Funktion $f$ durch einfachere stetige Funktionen in diskreten Punkten bezüglich der l$_1$-Norm angenähert.

## Problemstellung

Gegeben seien
* eine feste endliche Menge $X_{m}=\{x_{1},x_{2},\ldots ,x_{m}\}$, die in einem reellen Intervall $I$ liegt
* eine reellwertige Funktion $f$, die auf $X_{m}$ definiert ist: $f:X_{m}\rightarrow \mathbb {R}$
* $n$ stetige reellwertige Funktionen $\Phi _{1},\Phi _{2},\ldots ,\Phi _{n}$ mit $n\leq m$, die auf dem Intervall $I$ definiert sind.
Die Funktion $f$ soll auf der Menge $X_{m}$ im Sinne der l$_1$-Norm möglichst gut durch eine Linearkombination der stetigen Funktionen $\Phi _{i}$ approximiert werden. Das heißt, unter den Vektoren $a=(a_{1},a_{2},\ldots ,a_{n})^{T}$ wird derjenige Vektor $a^{*}$ gesucht, für den gilt:
    $\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|$
mit
    $L(a,x):=L(a_{1},a_{2},\ldots a_{n};x):=\sum _{j=1}^{n}a_{j}\Phi _{j}(x)$
und $a_{j}\in \mathbb {R} .$
Zugrunde liegt die l$_1$-Norm, ein Spezialfall der l$_p$-Norm mit $p=1$, die auch unter dem Namen Betragssummennorm bekannt ist:
    $\|x\|_{1}:=\sum _{i=1}^{n}|x_{i}|$
Es wird also die Summe der Fehlerbeträge in den einzelnen Punkten $x_{i}$ minimiert.

## Formulierung als lineares Optimierungsproblem

Durch geeignete Umformulierung lässt sich das Problem als lineares Optimierungsproblem darstellen und mit den entsprechenden Methoden, etwa dem Simplex-Verfahren, lösen.
Mit den Abkürzungen
    $f_{n}:=f(x_{i})$
    $\Phi _{ji}:=\Phi _{j}(x_{i})$
    $r_{i}=r_{i}(a):=f(x_{i})-L(a,x_{i})$
lässt sich das Problem schreiben als:
    Minimiere $z=\sum _{i=1}^{m}|r_{i}(a)|$
    unter den Nebenbedingungen
       $f_{i}=L(a,x_{i})+r_{i}$ für $i=1,2,\ldots ,m$ und
       $a\in \mathbb {R} ^{n}.$
Um das Problem mit der Simplexmethode lösen zu können, muss noch die Zielfunktion linearisiert werden. Dazu setzt man
    $r_{i}=u_{i}-v_{i}$ für $i=1,2,\ldots ,m$
mit $u_{i},v_{i}\geq 0$ und erhält schließlich ein lineares Optimierungsproblem, das mit dem Simplex-Verfahren gelöst werden kann:
    Minimiere $z=\sum _{i=1}^{m}(u_{i}+v_{i})$
    unter den Nebenbedingungen
       $f_{i}=\sum \limits _{j=1}^{n}a_{j}\Phi _{ji}+u_{i}-v_{i}$ für $i=1,2,\ldots ,m$
       $u_{i},v_{i}\geq 0$
       $a_{j}$ freie Variable für $j=1,2,\ldots ,n$

## Nicht-Eindeutigkeit von Lösungen

Die Lösung ist nicht immer eindeutig, wie das folgende Beispiel zeigt:
    Sei $X_{m}=X_{2}=\{0,1\}$, also $m=2,$
    $f(x)={\begin{cases}1,&{\text{wenn}}\;x=0\\-1,&{\text{wenn}}\;x=1\end{cases}}$
    und $\Phi _{1}(x)=1,$ also $n=1.$
    Dann ist jede Funktion $L(a,x)=a_{1}$ mit $-1\leq a_{1}\leq +1$ eine beste Approximation, es gibt also beliebig viele Lösungen.

## Nutzen der l$_1$ Approximation

Ian Barrodale beobachtete in L$_1$-approximation and the analysis of data (siehe Literatur) folgende Eigenschaft: Treten in einer Messreihe in wenigen der Messwerte große Messfehler auf, dann werden diese schlechten Werte in vielen Fällen von einer optimalen Lösung der l$_1$ Approximation erkannt und ignoriert. Das heißt, an diesen Stellen ergibt sich im Verhältnis zu den "fast richtigen" Werten ein wesentlich größerer Fehler
    $|f(x_{i})-L(a^{*},x_{i})|.$
Dagegen fallen solche "großen Messfehler" etwa bei einer l$_2$ Approximation oder einer l$_∞$ Approximation nicht auf und verschlechtern die gesamte Lösung. Daher empfiehlt Barrodale, zunächst mittels einer l$_1$ Approximation die schlechten Werte ("wild points") zu erkennen und diese dann fortzulassen oder durch bessere Werte zu ersetzen. Danach könnte eine Approximation in der gewünschten Norm erfolgen.