Diskrete lineare L1-Approximation

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

Problemstellung

Gegeben seien

• eine feste endliche Menge <math>X_m=\{x_1, x_2, \ldots, x_m\}</math>, die in einem reellen Intervall <math>I</math> liegt
• eine reellwertige Funktion <math>f</math>, die auf <math>X_m</math> definiert ist: <math>f:X_m\rightarrow \R</math>
• <math>n</math> stetige reellwertige Funktionen <math>\Phi_1, \Phi_2, \ldots, \Phi_n</math> mit <math>n \le m</math>, die auf dem Intervall <math>I</math> definiert sind.

Die Funktion <math>f</math> soll auf der Menge <math>X_m</math> im Sinne der l₁-Norm möglichst gut durch eine Linearkombination der stetigen Funktionen <math>\Phi_i</math> approximiert werden. Das heißt, unter den Vektoren <math>a = (a_1,a_2,\ldots,a_n)^T</math> wird derjenige Vektor <math>a^*</math> gesucht, für den gilt:

<math>\sum_{i=1}^m \left| f(x_i) - L(a^*,x_i) \right| \le \sum_{i=1}^m \left| f(x_i) - L(a,x_i) \right|</math>

mit

<math> L(a,x) := L(a_1, a_2, \ldots a_n;x) := \sum_{j=1}^n a_j \Phi_j (x) </math>

und <math> a_j \in \R.</math>

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

<math>\| x \|_1 := \sum_{i=1}^n | x_i |</math>

Es wird also die Summe der Fehlerbeträge in den einzelnen Punkten <math>x_i</math> 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

<math>f_n := f(x_i)</math>

<math>\Phi_{ji} := \Phi_j (x_i)</math>

<math>r_i = r_i (a) := f(x_i) - L(a,x_i)</math>

lässt sich das Problem schreiben als:

Minimiere <math>z = \sum_{i=1}^m | r_i(a) |</math>

unter den Nebenbedingungen

<math>f_i = L(a,x_i) + r_i</math>   für   <math>i=1,2, \ldots, m</math>   und

<math>a \in \R^n.</math>

Um das Problem mit der Simplexmethode lösen zu können, muss noch die Zielfunktion linearisiert werden. Dazu setzt man

<math>r_i = u_i - v_i</math>   für   <math>i=1,2, \ldots, m</math>

mit <math>u_i, v_i \ge 0</math> und erhält schließlich ein lineares Optimierungsproblem, das mit dem Simplex-Verfahren gelöst werden kann:

 

Minimiere <math>z = \sum_{i=1}^m (u_i + v_i)</math>

unter den Nebenbedingungen

<math>f_i = \sum\limits_{j=1}^n a_j \Phi_{ji} + u_i -v_i</math>   für   <math>i=1,2, \ldots, m </math>

<math>u_i, v_i \ge 0</math>

<math>a_j</math>   freie Variable für   <math>j=1,2, \ldots, n</math>

 

Nicht-Eindeutigkeit von Lösungen

Die Lösung ist nicht immer eindeutig, wie das folgende Beispiel zeigt:

Sei <math>X_m=X_2=\{0, 1\}</math>, also <math>m = 2,</math>

<math>

f(x)=\begin{cases}

  1, & \text{wenn} \; x = 0 \\
 -1, & \text{wenn} \; x = 1

\end{cases} </math>

und <math>\Phi_1(x) = 1,</math> also <math>n = 1.</math>

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

<math>|f(x_i) - L(a^*,x_i)|.</math>

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)