Diskrete lineare L1-Approximation
# 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.

