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,\dots ,x_m\}$, die in einem reellen Intervall $I$ liegt
• eine reellwertige Funktion $f$, die auf $X_m$ definiert ist: $f:X_m\to ℝ$
• $n$ stetige reellwertige Funktionen ${\mathrm{\Phi }}_1,{\mathrm{\Phi }}_2,\dots ,{\mathrm{\Phi }}_n$ mit $n\le 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 ${\mathrm{\Phi }}_i$ approximiert werden. Das heißt, unter den Vektoren $a=(a_1,a_2,\dots ,a_n{)}^T$ wird derjenige Vektor $a^{*}$ gesucht, für den gilt:

$\sum _{i=1}^m|f(x_i)-L(a^{*},x_i)|\le \sum _{i=1}^m|f(x_i)-L(a,x_i)|$

mit

$L(a,x):=L(a_1,a_2,\dots a_n;x):=\sum _{j=1}^n{a}_j{\mathrm{\Phi }}_j(x)$

und $a_j\in ℝ.$

Zugrunde liegt die l₁-Norm, ein Spezialfall der l_p-Norm mit $p=1$, die auch unter dem Namen Betragssummennorm bekannt ist:

$\Vert x{\Vert }_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)$

${\mathrm{\Phi }}_{ji}:={\mathrm{\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,\dots ,m$   und

$a\in {ℝ}^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,\dots ,m$

mit $u_i,v_i\ge 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 _{j=1}^n{a}_j{\mathrm{\Phi }}_{ji}+u_i-v_i$   für   $i=1,2,\dots ,m$

$u_i,v_i\ge 0$

$a_j$   freie Variable für   $j=1,2,\dots ,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{array}{cc}1,& \text{wenn}x=0\\ -1,& \text{wenn}x=1\end{array}$

und ${\mathrm{\Phi }}_1(x)=1,$ also $n=1.$

Dann ist jede Funktion $L(a,x)=a_1$ mit $-1\le a_1\le +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)