Die Regressionsmethode der kleinsten Quadrate (englisch: Least Squares Method) basiert auf der Minimierung der Summe der Quadrate der Fehler auf einen möglichst kleinen Wert, daher der Name kleinste Quadrate. Im Grunde muss der Abstand zwischen den Datenpunkten (Messwerten) und der Regressionsfunktion so weit wie möglich minimiert werden.

Problemstellung

Gegeben sei \(\textbf{A} \in \mathbb{K}^{m\text{x}n}\) und gemessen sei \(\textbf{b} \in \mathbb{K}^m\), wobei \(m\) die Anzahl der Messungen, \(n\) die Anzahl der zu schätzenden Parameter sind und \(m > n\) ist.
Gesucht wird ein \(\textbf{x}^\ast\) so das:

\[\Vert \textbf{A}\textbf{x}^\ast - \textbf{b} \Vert_2 = \underset{x\in\mathbb{K}^n}{\min} \Vert \textbf{A}\textbf{x} - \textbf{b}\Vert_2\]

\(\Vert \textbf{A}\textbf{x} - \textbf{b}\Vert_2 = 0\) kann nur im idealen Fall und mit exakten Werten auftreten. Also das Vektor \(\textbf{b} - \textbf{A}\textbf{x}\) existiert immer und wird als Residuum bezeichnet. Die Methode der kleinsten Quadrate ist also ein Optimierungsproblem und sie besteht darin, die euklidische Norm des Residuums zu minimieren.

Die Normalengleichung kann nun aus (1) abgeleitet werden, indem man \(\nabla f(x) \stackrel{!}{=} 0\) setzt, wobei \(f(x) = \Vert \textbf{A}\textbf{x} - \textbf{b}\Vert_2^2\) ist.
Dadurch lässt sich das Problem wie folgt umformulieren:
\(\textbf{x}^\ast \in \mathbb{K}^n\) ist genau dann Lösung des linearen Ausgleichsproblems (1) wenn \(\textbf{x}^\ast\) Lösung der Normalengleichungen

\[\textbf{A}^T\textbf{A}\textbf{x} = \textbf{A}^T\textbf{b}\]

ist. Das System der Normalengleichungen hat stets mindestens eine Lösung.

Besitzt \(\textbf{A}\) den vollen Rang, ist die Lösung bzw. die Approximation eindeutig sprich \(\textbf{x}^\ast = \textbf{x}\).
Ist aber \(Rang(\textbf{A}) < \min(m,n)\), existiert dann eine Lösungsmenge X, wobei \(\textbf{x}^\ast = \underset{x \in X}{\min}\Vert x \Vert\).

Im Folgenden werden zwei Lösungsmethoden für das LS-Problem erläutert.

Pseudoinverse und Singulärwertzerlegung

Falls \(\textbf{A}\) den vollen Rang besitzt, dann ist \(\textbf{A}^T\textbf{A}\) symmetrisch und positiv definit. Also die Inverse \((\textbf{A}^T\textbf{A})^{-1}\) existiert und ist eindeutig. (2) kann dann wie folgt gelöst werden:

\[\textbf{x} = ((\textbf{A}^T\textbf{A})^{-1}\textbf{A}^T)\textbf{b} = \textbf{A}^\dag\textbf{b},\]

wobei \(\textbf{A}^\dag = (\textbf{A}^T\textbf{A})^{-1}\textbf{A}^T\) als Pseudoinverse bezeichnet wird.
Die Pseudoinverse stellt also eine Verallgemeinerung der inversen Matrix auf singuläre und nichtquadratische Matrizen dar. Sie muss die sog. Penrose-Bedingungen erfüllen:

  1. \(\textbf{A} \textbf{A}^\dag \textbf{A} = \textbf{A}\),
    • \(\textbf{A}\textbf{A}^\dag\) muss nicht die allgemeine Identitätsmatrix sein, aber sie bildet alle Spaltenvektoren von A auf sich selbst ab;
  2. \(\textbf{A}^\dag \textbf{A} \textbf{A}^\dag = \textbf{A}^\dag\),
  3. \((\textbf{A} \textbf{A}^\dag)^H = \textbf{A}\textbf{A}^\dag\),
  4. \((\textbf{A}^\dag \textbf{A})^H = \textbf{A}^\dag \textbf{A}\),
    • \(\textbf{A}^\dag \textbf{A}\) ist auch hermitesch.

Ist aber \(Rang(\textbf{A}) < \min(m,n)\), definiert man dann die Pseudoinverse über die Singulärwertzerlegung (SVD).

Sei \(\textbf{A} \in \mathbb{K}^{m\text{x}n}\) eine Matrix von Rang \(r\). Dann gibt es orthogonale Matrizen \(\textbf{U} \in \mathbb{K}^{m\text{x}m}\) und \(\textbf{V}\in\mathbb{K}^{n\text{x}n}\) sowie eine Diagonalmatrix

\[\Sigma = \left[\begin{array}{cc} \Sigma_r & 0 \\ 0 & 0 \end{array}\right] \in \mathbb{K}^{m\text{x}n}\]

mit \(\Sigma_r = diag(\sigma_1,\sigma_2,\dots,\sigma_r) \in \mathbb{K}^{r\text{x}r}\) und \(\sigma_1\geqslant \sigma_2\geqslant \dots \geqslant \sigma_r > 0\), so dass \(\textbf{A}\) die Zerlegung

\[\textbf{A} = \textbf{U} \Sigma \textbf{V}^T\]

besitzt. Dies heißt Singulärwertzerlegung von \(\textbf{A}\). Die Werte \(\sigma_i\) nennt man Singulärwerte von \(\textbf{A}\). Die Anzahl der Singulärwerte \(\sigma_i \neq 0\) entspricht dem Rang von \(\textbf{A}\).

Nun ist die Pseudoinverse von A wie folgt definiert:

\[\textbf{A}^\dag = \textbf{V}\Sigma^\dag\textbf{U}^T \in \mathbb{K}^{n\text{x}m} \text{~, wobei~} \Sigma^\dag = \left[\begin{array}{cc} \Sigma_r^{-1} & 0 \\ 0 & 0 \end{array}\right]\]

Wenn aber \(Rang(\textbf{A}) = m = n\) ist, ist dann \(\textbf{A}^\dag = \textbf{A}^{-1}\).

Kondition einer Matrix

In dem vorherigen Abschnitt wurde gezeigt, dass eine Matrix anhand Approximationen immer invertierbar ist sprich die Normalengleichung besitzt immer mindestens eine Lösung. Nun stellt sich die Frage ob diese Lösung Sinn macht.
Ein wichtiger Maß dafür ist die Kondition eines Problems. Sie gibt an, mit welchen unvermeidlichen Fehlern man in jedem Fall, selbst bei exakter Lösung, rechnen muss:
Ein Problem heißt gut konditioniert, wenn kleine Störungen der Eingangsdaten kleine Änderungen im Ergebnis bewirken.
Die Kondition einer Matrix \(\textbf{A} \in \mathbb{K}^{m\text{x}n}\) bezüglich einer Norm ist definiert als

\[\kappa_{\Vert \cdot \Vert}(\textbf{A}) = \text{cond}_{\Vert \cdot \Vert}(\textbf{A}) = \frac{\underset{\Vert \textbf{x}\Vert = 1}{\max} \Vert \textbf{A}\textbf{x}\Vert}{\underset{\Vert \textbf{x}\Vert = 1}{\min} \Vert \textbf{A}\textbf{x}\Vert}\]

und sie hat folgende Eigenschaften:

  • \(\kappa(\textbf{A}) = \kappa(\textbf{A}^{-1})\),
  • \(\kappa(\textbf{A}) \geqslant 1\) ,
  • \(\forall \lambda \in \mathbb{C}^\ast \text{~gilt~} \kappa(\lambda \textbf{A}) = \kappa(\textbf{A})\).

Im Fall sehr schlechter Konditionszahl kann man auch das SVD-Lösung verwenden, indem man die kleinsten Singulärwerte bei der Schätzung weg lässt, um Rauschverstärkung zu vermeiden.

Quellen

  1. Stephen M. Kogon Dimitris G. Manolakis, Vinay K. Ingle. “Statistical and adaptive signal processing”. Artech house, 2005.
  2. Proofs involving the Moore–Penrose inverse.
  3. S. Kacem. ”Kompensation von frequenzselektiver I/Q-Imbalance in breitbandigen Direktmisch-Sendern”. Studienarbeit 2011.
  4. Mathpedia, Methode der kleinsten Quadrate