Diskrete lineare L1-Approximation

Bei der diskreten linearen l₁-Approximation wird in der Mathematik eine vorgegebene reellwertige Funktion $f$ durch einfachere stetige Funktionen in diskreten Punkten bezüglich der l₁-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₁-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₁-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₁ Approximation

Ian Barrodale beobachtete in L₁-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₁ 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₂ Approximation oder einer l_∞ Approximation nicht auf und verschlechtern die gesamte Lösung. Daher empfiehlt Barrodale, zunächst mittels einer l₁ 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.

Literatur

• Nabih N. Abdelmalek: Linear l₁-approximation for a discrete point set and l₁-solutions of overdetermined linear equations., Journal of the ACM 18 (1971), S. 41–47
• Nabih N. Abdelmalek: On the discrete linear l₁-approximation and l₁-solutions of overdetermined linear equations., Journal of Approximation Theory 11 (1974), S. 38–53
• Nabih N. Abdelmalek: An efficient method for the discrete linear l₁-approximation problem., Mathematics of Computation 29 (1975) S. 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), S. 51–57
• Ian Barrodale: On computing best l₁ approximations, Approximation Theory (A. Talbot, Editor), Academic Press 1970, S. 205–215
• Ian Barrodale, Frank D.K. Roberts: Applications of mathematical programming to l_p approximation, Nonlinear Programming (J.B. Rosen, O.L. Mangasarian, K. Ritter, Editors), Academic Press 1970, S. 447–464
• Ian Barrodale, Frank D.K. 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), S. 295–306
• G. Croucher: Best l₁ and l_∞ linear approximations on a discrete set, 1971, M.Sc. thesis, Birkbeck College, London University
• P.D. Robers, A. Ben-Israel: An interval programming algorithm for discrete linear l₁-approximation problems., Journal of Approximation Theory 2 (1969), S. 323–326
• Karl H. Usow: On l₁ approximation II: Computation for discrete functions and discretisation effects., SIAM Journal Numerical Analysis 4 (1967), S. 233–244

Weblinks

• K. Spyropuolos, E. Kiountouzis, A.Young: Discrete approximation in the L₁ norm, The Computer Journal 16 (1972) S.180-186 (abgerufen am 28. Dezember 2011; PDF; 3,9 MB)