Pseudoinverse en kleinste kwadraten methode

SVD, pseudoinverse en PCA: SVD, pseudoinverse en PCA

Pseudoinverse en kleinste kwadraten methode

Stel dat $A$ een ( $n\times n$ )-matrix is en $\vec{b}$ een vector in $\mathbb{R}^n$ is en je de vergelijking $A\vec{v}=\vec{b}$ wilt oplossen. Als het beeld van $A$ de hele ruimte is, dan heeft de vergelijking een oplossing, namelijk $\vec{v}=A^{-1}\vec{b}$ . Maar wat te doen als $\vec{b}$ niet in het beeld van $A$ zit? Dan kunnen we een vector $\vec{\beta}$ in het beeld van $A$ bepalen met kortste afstand tot $\vec{b}$ : $\left\lVert\vec{b}-\vec{\beta}\right\rVert\le\left\lVert\vec{b}-\vec{v}\right\rVert$ voor alle $v\in\text{im}(A)$ . Wat we zoeken is dan de orthogonale projectie van $\vec{b}$ op het beeld van $A$ , oftewel, we zoeken een vector $\vec{v}$ zodanig dat $A\vec{v}=\text{projectie van }\vec{b}\text{ op im}(A)$ Zo'n vector heet een kleinste-kwadratenoplossing van de vergelijking $A\vec{v}=\vec{b}$ . We weten dat $\vec{b}-A\vec{v}$ loodrecht op het beeld van $A$ staat en dus is $A\vec{x}\boldsymbol{\cdot}(\vec{b}-A\vec{v})=0$ voor alle $\vec{x}$ . Opgeschreven als matrixproduct hebben we: $\vec{x}^{\top}\!A^{\top}\!(\vec{b}-A\vec{v})=0$ voor alle $\vec{x}$ . Dus met het inproduct: $\vec{x}\cdot A^{\top}\!(\vec{b}-A\vec{v})=0$ voor alle $\vec{x}$ . In het bijzonder geldt dit voor $\vec{x}=A^{\top}\!(\vec{b}-A\vec{v})$ en dus: $A^{\top}\!(\vec{b}-A\vec{v})\boldsymbol{\cdot} A^{\top}\!(\vec{b}-A\vec{v})=0$ . Maar dan moet gelden dat $A^{\top}\!(\vec{b}-A\vec{v})=\vec{0}$ , Met andere woorden: $\vec{b}-A\vec{v}$ is element van de kern van $A^{\top}$ . Omdat $A^{\top}\!(\vec{b}-A\vec{v})=\vec{0}$ equivalent is met $A^{\top}\!A\vec{v}=A^{\top}\!\vec{b}$ geldt, onder de conditie dat $A^{\top}\!A$ inverteerbaar is, dat $\vec{v}=(A^{\top}\!A)^{-1}\!A^{\top}\,\vec{b}\tiny.$

Als $A$ een ( $m\times n$ )-matrix is met $\text{rang}(A^{\top})=n$ , dan is $A^{\top}A$ inverteerbaar en is de pseudoinverse van $A$ , ook wel Moore-Penrose inverse genaamd, de matrix $A^{+}$ gedefinieerd door $A^{+}=(A^{\top}\!A)^{-1}\!A^{\top}$

Merk op dat de pseudoinverse van een ( $m\times n$ )-matrix een ( $n\times m$ )-matrix is.

Toepassing van de pseudoinverse van een matrix op een vector levert dus de kleinste kwadraten benadering van de vector op. Het verband tussen pseudoinverse en singulierewaardenontbinding is als volgt en generaliseert de definitie van pseudoinverse tot een willekeurige matrix.

Laat $A$ een ( $m\times n$ )-matrix zijn met singulierewaardenontbinding $U\Sigma V^{\top}$ , waarbij $\Sigma=\matrix{D & 0\\ 0 & 0}$ een ( $m\times n$ )-matrix met ( $r\times r$ )-diagonaalmatrix $D$ waarbij op de hoofddiagonaal de singuliere waarden van $A$ ongelijk aan nul staan, dat wil zeggen, $\sigma_1\ge\sigma_2\ge\cdots\ge \sigma_r\gt 0$ . De pseudoinverse van $A$ is dan de ( $n\times m$ )-matrix $A^{+}$ gedefinieerd door $A^{+}=V\,\Sigma^{+}U^{\top}$ waarbij $\Sigma^{+}$ de ( $n\times m$ )-matrix $\Sigma^{+}=\matrix{D^{-1} & 0\\ 0 & 0}$ is.

Nu geldt:

Het probleem $A\vec{v}=\vec{b}$ heeft een unieke kleinste-kwadratenoplossing zodat $A\vec{v}$ het dichtst bij $\vec{b}$ ligt en wel $\vec{v}=A^{+}\vec{b}\tiny.$

Laten we als voorbeeld een eerder regressieprobleem bekijken: een regressielijn voor de punten $(1,2)$ , $(2,2)$ en $(3,4)$ . Bij het regressietype hoort de matrix $A=\matrix{1 & 1\\ 2& 1 \\ 3 & 1}$ We kunnen de pseudoinverse van $A$ berekenen: $A^{\top}\!A = \matrix{1 & 2 & 3\\ 1 & 1 & 1}\matrix{1 & 1\\ 2 & 1 \\ 3 & 1}= \matrix{14 & 6\\ 6 & 3}$ met determinant $14\times 3-6\times 6=6$ . Dus is de inverse van deze $2\times 2$ -matrix als volgt: $(A^{\top}\!A)^{-1} = \frac{1}{6}\matrix{3 & -6\\ -6 & 14 }=\matrix{\frac{1}{2} & -1\\ -1 & \frac{7}{3}}$ De pseudoinverse is nu: $A^{+}=(A^{\top}\!A)^{-1}\!A^{\top}= \matrix{\frac{1}{2} & -1\\ -1 & \frac{7}{3}} \matrix{1 & 2 & 3\\ 1 & 1 & 1} = \matrix{-\frac{1}{2} & 0 & \frac{1}{2} \\ \frac{4}{3} & \frac{1}{3} & -\frac{2}{3}}$ Om de regressielijn te bepalen, moeten we nu het volgende matrix-vector product uitrekenen om de coëfficiënten van de regressielijn $y=at+b$ te bepalen: $\matrix{-\frac{1}{2} & 0 & \frac{1}{2} \\ \frac{4}{3} & \frac{1}{3} & -\frac{2}{3}}\cv{2 \\ 2\\ 4}=\cv{1\\ \frac{2}{3}}$ We hebben dus de lijn $y=t+\frac{2}{3}$ gevonden.