Aalto MOOC Matriisilaskenta 2019: Singulaariarvohajotelma

Jokainen matriisi \(\mathbf{A}\in \mathbb{C}^{m\times n}\) voidaan esittää muodossa

\[ \mathbf{A} = \mathbf{U}\Sigma \mathbf{V}^*, \]

missä \(\mathbf{U}\in \mathbb{C}^{m\times p}\), \(\mathbf{V}\in\mathbb{C}^{n\times p}\), \(\Sigma\in \mathbb{C}^{p\times p}\), \(p=\min\{n,m\}\).

Matriisien \(\mathbf{U},\mathbf{V}\) sarakevektorit \(\mathbf{u}_1,\ldots,\mathbf{u}_p\in \mathbb{C}^m\), \(\mathbf{v}_1,\ldots,\mathbf{v}_p\in \mathbb{C}^{n}\) ovat ortonormaaleja ja

\[ \Sigma = \begin{pmatrix} \sigma_1 & \cdots & 0\\ \vdots & \dots & \vdots \\ 0 & \cdots & \sigma_n \end{pmatrix}, \qquad \sigma_1 \ge \cdots \ge \sigma_p \ge 0 \]

ovat matriisin singulaariarvot .

Ominaisarvoja on vain neliömatriiseilla, mutta singulaariarvot ja -hajotelma on kaikilla matriiseilla.

Matriisi \(\mathbf{U}\) on unitaarinen, eli \(\mathbf{U}^* = \mathbf{U}^{-1}\), jos \(p=m\). Vastaavasti \(\mathbf{V}^* = \mathbf{V}^{-1}\), jos \(p=n\).

Jos \(\mathbf{x} \in \mathbb{C}^n\), niin

\[ \mathbf{A} \mathbf{x} = \mathbf{U}\Sigma\mathbf{V}^*\mathbf{x} = \begin{pmatrix} \sigma_1 \mathbf{u}_1 & \cdots & \sigma_p\mathbf{u}_p \end{pmatrix} \begin{pmatrix} \langle \mathbf{x},\mathbf{v}_1 \rangle \\ \vdots \\ \langle \mathbf{x},\mathbf{v}_p \rangle \end{pmatrix} \] \[ = \sum_{j=1}^p \sigma_j\langle \mathbf{v}_j,\mathbf{x} \rangle \mathbf{u}_j. \]

Siten \(\mathbf{A}\) kertoo \(\mathbf{x}\):n vektorin \(\mathbf{v}_j\in \mathbb{C}^n\) suuntaisen komponentin \(\langle \mathbf{x},\mathbf{v}_j \rangle\) singulaariarvolla \(\sigma_j\ge 0\) ja siirtää sen suuntaan \(\mathbf{u}_j\).

Vektorit \(\{\mathbf{u}_1,\ldots,\mathbf{u}_r\}\), missä \(\sigma_1\ge \cdots \ge \sigma_r> \sigma_{r+1} = \cdots = \sigma_p=0\), muodostavat matriisin \(\mathbf{A}\) kuva-avaruuden \(R(\mathbf{A})\) kannan.

Singulaariarvohajotelmalla on paljon erilaisia sovelluksia mm. signaalinkäsittelyssä, tilastotieteessä ja tieteellisessä laskennassa.

Singulaariarvohajotelman laskeminen*

Seuraavaksi tutkitaan, miten matriisille \(\mathbf{A}\in \mathbb{C}^{m\times n}\) voidaan löytää singulaariarvohajotelma.

Lisäksi jos \(\mathbf{A}^*\mathbf{A} \mathbf{v} = \lambda \mathbf{v}\), niin

\[ ||\mathbf{A}\mathbf{v}|| = \langle \mathbf{A}\mathbf{v},\mathbf{A}\mathbf{v} \rangle = \langle \mathbf{A}^*\mathbf{A}\mathbf{v},\mathbf{v}\rangle \] \[ \langle \lambda\mathbf{v}, \mathbf{v}\rangle = \lambda ||\mathbf{v}||^2. \]

Siten ominaisarvot \(\lambda_1\ge \cdots \ge \lambda_r >\lambda_{r+1}=\ldots =\lambda_n=0\) ovat ei-negatiivisia.

Voidaan valita

\[ \sigma_j := \sqrt{\lambda_j}= ||\mathbf{A}\mathbf{v}_j||,\textrm{ kun } j=1,\ldots,r. \]

Lisäksi ominaisvektoreille \(\mathbf{v}_j,\mathbf{v}_k\) pätee

\[ \left\{\begin{array}{rcl} \mathbf{A}^*\mathbf{A}\mathbf{v}_j &=& \lambda_j\mathbf{v}_j,\\ \mathbf{A}^*\mathbf{A}\mathbf{v}_k &=& \lambda_k\mathbf{v}_k, \end{array}\right. \]

joten

\[ \langle \mathbf{A}\mathbf{v}_j,\mathbf{A}\mathbf{v}_k \rangle = \langle \mathbf{A}^*\mathbf{A}\mathbf{v}_j,\mathbf{v}_k \rangle \] \[ =\langle \lambda_j\mathbf{v}_j,\mathbf{v}_k \rangle = \lambda_j\langle \mathbf{v}_j,\mathbf{v}_k \rangle =0, \]

koska \(\mathbf{A}^*\mathbf{A}\) on unitaarisesti diagonalisoituva.

Siten vektoreille

\[ \mathbf{u}_j= \frac{\mathbf{A}\mathbf{v}_j}{||\mathbf{A}\mathbf{v}_j||}\in \mathbb{C}^m \]

pätee \(\langle \mathbf{u}_j,\mathbf{u}_k\rangle=0\), kun \(j,k\le r\) ja \(j\neq k\).

Näin ollen, jokaiselle \(\mathbf{x} = c_1\mathbf{v}_1+\ldots +c_n\mathbf{v}_n\in \mathbb{C}^n\) pätee

\[ \mathbf{A}\mathbf{x}= c_1\mathbf{A}\mathbf{v}_1+\ldots + c_r\mathbf{A}\mathbf{v}_r + c_{r+1}\cdot 0 + \ldots + c_n\cdot 0 \] \[ =\langle \mathbf{x},\mathbf{v}_1 \rangle ||\mathbf{A}\mathbf{v}_1||\mathbf{u}_1+\ldots+\langle \mathbf{x},\mathbf{v}_r \rangle ||\mathbf{A}\mathbf{v}_r||\mathbf{u}_r. \]

Jos täydennetään \(\{\mathbf{u}_1,\ldots,\mathbf{u}_r\}\) ortonormaaliksi vektorijoukoksi \(\{\mathbf{u}_1,\ldots,\mathbf{u}_p\}\) mielivaltaisella tavalla, saadaan

\[ \mathbf{A}\mathbf{x}=\sum_{j=1}^p \langle \mathbf{x},\mathbf{v}_j \rangle ||\mathbf{A}\mathbf{v}_j ||\mathbf{u}_j=\mathbf{U}\Sigma\mathbf{V}^*\mathbf{x}. \]

Tässä

\[ \mathbf{U} = \begin{pmatrix} \mathbf{u}_1 \cdots \mathbf{u}_p \end{pmatrix},\qquad \Sigma = \begin{pmatrix} \sigma_1 & \cdots & 0\\ \vdots & \ddots & \vdots \\ 0 &\cdots &\sigma_p \end{pmatrix}, \]

\[ \mathbf{V} = \begin{pmatrix} \mathbf{v}_1 & \cdots &\mathbf{v}_p \end{pmatrix}. \]

Yhteenveto singulaariarvohajotelman laskemisesta*

Diagonalisoi unitaarisesti \(\mathbf{A}^*\mathbf{A}= \mathbf{V}\Lambda \mathbf{V}^*\) siten, että

\[ \Lambda =\begin{pmatrix} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots &\lambda_p \end{pmatrix}, \quad \lambda_1\ge \cdots \ge \lambda_r>\lambda_{r+1}=\cdots = \lambda_p=0. \]
Aseta \(\sigma_j=\sqrt{\lambda_j}\), \(j=1,\ldots,p\), ja \(\mathbf{u}_j = \mathbf{A}\mathbf{v}_j/\sigma_j\), \(j=1,\ldots,r\).
Täydennä \(\{\mathbf{u}_1,\ldots,\mathbf{u}_r\}\) ortonormaaliksi joukoksi \(\{\mathbf{u}_1,\ldots,\mathbf{u}_p\}\), jos \(r< p\). Unohda \(\mathbf{v}_{p+1},\ldots,\mathbf{v}_r\), jos \(n> p\). Tällöin

\[ \mathbf{A} = \begin{pmatrix} \mathbf{u}_1 & \cdots & \mathbf{u}_p \end{pmatrix} \begin{pmatrix} \sigma_1 & \cdots & 0\\ \vdots & \ddots & \vdots \\ 0 &\cdots &\sigma_p \end{pmatrix} \begin{pmatrix} \mathbf{v}_1^* \\ \vdots \\ \mathbf{v}_p^* \end{pmatrix} = \mathbf{U}\Sigma\mathbf{V}^*. \]

Esimerkki

Lasketaan matriisin

\[ \mathbf{A} = \begin{pmatrix} 1 & -1 \\ -2 & 2 \\ 2 & -2 \end{pmatrix} \] singulaariarvohajotelma.

Lasketaan aluksi

\[ \mathbf{A}^*\mathbf{A} = \begin{pmatrix} 1 & -2 & 2\\ -1 & 2 & -2 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ -2 & 2 \\ 2 & -2 \end{pmatrix} = \begin{pmatrix} 9 & -9 \\ -9 & 9 \end{pmatrix}. \] Muodostetaan karakteristinen polynomi \[ P_{\mathbf{A}^*\mathbf{A}}(\lambda) = \begin{vmatrix} 9-\lambda & -9 \\ -9 & 9-\lambda \end{vmatrix} = (9-\lambda)^2-81 = \lambda (\lambda -18). \] Ominaisarvolle \(\lambda_1 = 18\) saadaan yhtälö \(\mathbf{A}^*\mathbf{A}\mathbf{v}_1 = 18\mathbf{v}_1\), eli \[ \begin{pmatrix} 9-18 & -9 \\ -9 & 9-18 \end{pmatrix} \mathbf{v}_1 = \begin{pmatrix} -9 & -9 \\ -9 & -9 \end{pmatrix}\mathbf{v}_1 =0. \] Saadaan \(v_1^1 = - v_1^2\), ja siten voidaan valita \[ \mathbf{v}_1 = \begin{pmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{pmatrix}. \] Ominaisarvosta \(\lambda_2= 0\) saadaan vastaavasti yhtälö \[ \begin{pmatrix} 9 & -9 \\ -9 & 9 \end{pmatrix} \mathbf{v}_2 =0, \] eli \(v_2^1 = v_2^2\). Voidaan valita \[ \mathbf{v}_2=\begin{pmatrix} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} \end{pmatrix}. \] Nyt \(\sigma_1 = \sqrt{\lambda_1}=\sqrt{18}\), ja \(\sigma_2 = \sqrt{\lambda_2}=0\).

Saadaan myös

\[ \mathbf{u}_1= \frac{\mathbf{A}\mathbf{v}_1}{\Vert \mathbf{A}\mathbf{v}_1 \Vert}= \frac{1}{3\sqrt{2}}\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & -1 \\ -2 & 2 \\ 2 & -2 \end{pmatrix} \begin{pmatrix} 1 \\-1 \end{pmatrix} = \begin{pmatrix} \frac{1}{3} \\-\frac{2}{3}\\ \frac{2}{3} \end{pmatrix}. \] Huomaa, että \(||\mathbf{u}_1||=1\) automaattisesti.

Koska \(\sigma_2=0\), täytyy \(\mathbf{u}_2\) etsiä erikseen. Vektorit \(\mathbf{u}_1\) ja \((1,0,0)\) ovat lineaarisesti riippumattomia, ja ne voidaan ortonormeerata Gram-Schmidt -algoritmilla:

\[ \mathbf{w} = (1,0,0) -\langle \mathbf{u}_1,(1,0,0) \rangle \mathbf{u}_1 \] \[ = (1,0,0) - \frac{1}{3}\left( \frac{1}{3},-\frac{2}{3},\frac{2}{3}\right) =\left( \frac{8}{9},\frac{2}{9},-\frac{2}{9}\right). \] Nyt \[ ||\mathbf{w}|| = \sqrt{64/81 + 4/81 + 4/81} = \sqrt{72/81} = \sqrt{8}/3. \] Saadaan \[ \mathbf{u}_2 = \frac{\mathbf{w}}{||\mathbf{w}||} = \begin{pmatrix} \frac{\sqrt{8}}{3} \\ \frac{2}{3\sqrt{8}} \\-\frac{2}{3\sqrt{8}} \end{pmatrix} = \begin{pmatrix} 2\sqrt{2}/3\\ \sqrt{2}/6 \\ - \sqrt{2}/6 \end{pmatrix}. \] Siten singulaariarvohajotelma on \(\mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^*\), missä \[ \mathbf{U} = \begin{pmatrix} 1/3 & 2\sqrt{2}/3\\ -2/3 & \sqrt{2}/6 \\ 2/3 & -\sqrt{2}/6 \end{pmatrix}, \Sigma = \begin{pmatrix} 3\sqrt{2} & 0 \\ 0 & 0 \end{pmatrix}, \mathbf{V} = \begin{pmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ -1/\sqrt{2} & 1/\sqrt{2} \end{pmatrix}. \]

Last modified: Monday, 15 February 2016, 5:10 PM