Відмінності між версіями «Сингулярне розкладання»
(→SVD і норма матриць) |
|||
(Не показано 50 проміжних версій цього користувача) | |||
Рядок 16: | Рядок 16: | ||
|} | |} | ||
− | '''Сингулярне розкладання''' (Singular Value Decomposition, SVD) – декомпозиція речовинної матриці з метою її приведення до канонічного виду. Сингулярне розкладання є зручним методом при роботі з матрицями. Воно показує геометричну структуру матриці і дозволяє наочно представити наявні дані. Сингулярне розкладання використовується при вирішенні найрізноманітніших завдань - від наближення методом найменших квадратів і рішення систем рівнянь до стиснення зображень. При цьому використовуються різні властивості сингулярного розкладання, наприклад, здатність показувати ранг матриці, наближати матриці даного рангу. SVD дозволяє обчислювати зворотні і | + | '''Сингулярне розкладання''' (Singular Value Decomposition, SVD) – декомпозиція речовинної матриці з метою її приведення до канонічного виду. Сингулярне розкладання є зручним методом при роботі з матрицями. Воно показує геометричну структуру матриці і дозволяє наочно представити наявні дані. Сингулярне розкладання використовується при вирішенні найрізноманітніших завдань - від наближення методом найменших квадратів і рішення систем рівнянь до стиснення зображень. При цьому використовуються різні властивості сингулярного розкладання, наприклад, здатність показувати ранг матриці, наближати матриці даного рангу. SVD дозволяє обчислювати зворотні і псевдообернених матриць великого розміру, що робить його корисним інструментом при вирішенні задач регресійного аналізу.<br> |
Для будь-якої речовинної <math>(n\times n)</math> - матриці <math>A</math> існує дві речовинні ортогональні <math>(n\times n)</math> - матриці <math>U</math> і <math>V</math> й такі, що <math>{{U}^{T}}AV</math> - діагональна матриця <math>\Lambda </math>, | Для будь-якої речовинної <math>(n\times n)</math> - матриці <math>A</math> існує дві речовинні ортогональні <math>(n\times n)</math> - матриці <math>U</math> і <math>V</math> й такі, що <math>{{U}^{T}}AV</math> - діагональна матриця <math>\Lambda </math>, | ||
<center> | <center> | ||
Рядок 33: | Рядок 33: | ||
Наприклад, матриця | Наприклад, матриця | ||
<center> | <center> | ||
− | <math>A=\left( \begin{matrix} | + | <math>A=\left( \begin{matrix} |
0.96 & 1.72 \\ | 0.96 & 1.72 \\ | ||
2.28 & 0.96 \\ | 2.28 & 0.96 \\ | ||
− | \end{matrix} \right)</math> | + | \end{matrix} \right)</math> |
</center> | </center> | ||
має сингулярне розкладання | має сингулярне розкладання | ||
<center> | <center> | ||
− | <math>A=U\Lambda {{V}^{T}}=\left( \begin{matrix} | + | <math>A=U\Lambda {{V}^{T}}=\left( \begin{matrix} |
0.6 & 0.8 \\ | 0.6 & 0.8 \\ | ||
0.8 & -0.6 \\ | 0.8 & -0.6 \\ | ||
− | \end{matrix} \right)\left( \begin{matrix} | + | \end{matrix} \right)\left( \begin{matrix} |
3 & 0 \\ | 3 & 0 \\ | ||
0 & 1 \\ | 0 & 1 \\ | ||
− | \end{matrix} \right){{\left( \begin{matrix} | + | \end{matrix} \right){{\left( \begin{matrix} |
0.8 & -0.6 \\ | 0.8 & -0.6 \\ | ||
0.6 & 0.8 \\ | 0.6 & 0.8 \\ | ||
− | \end{matrix} \right)}^{T}}</math> | + | \end{matrix} \right)}^{T}}</math> |
</center> | </center> | ||
Легко побачити, що матриці <math>U</math> і <math>V</math> ортогональні, | Легко побачити, що матриці <math>U</math> і <math>V</math> ортогональні, | ||
− | <center><math>{{U}^{T}}U=U{{U}^{T}}=I</math>, також <math>~{{V}^{T}}V=V{{V}^{T}}=I</math>,</center> | + | <center> <math>{{U}^{T}}U=U{{U}^{T}}=I</math>, також <math>~{{V}^{T}}V=V{{V}^{T}}=I</math>,</center> |
і сума квадратів значень їх стовпців дорівнює одиниці. | і сума квадратів значень їх стовпців дорівнює одиниці. | ||
Рядок 86: | Рядок 86: | ||
Сингулярне розкладання володіє властивістю, яке пов'язує задачу відшукання сингулярного розкладання і завдання відшукання власних векторів. Власний вектор <math>\mathbf{x}</math> матриці <math>A</math> - такий вектор, при якому виконується умова <math>A\mathbf{x}=\lambda \mathbf{x},~</math> число <math>\lambda</math> називається власним числом. Так як матриці <math>U</math> і <math>V</math> ортогональні, то | Сингулярне розкладання володіє властивістю, яке пов'язує задачу відшукання сингулярного розкладання і завдання відшукання власних векторів. Власний вектор <math>\mathbf{x}</math> матриці <math>A</math> - такий вектор, при якому виконується умова <math>A\mathbf{x}=\lambda \mathbf{x},~</math> число <math>\lambda</math> називається власним числом. Так як матриці <math>U</math> і <math>V</math> ортогональні, то | ||
<center> | <center> | ||
− | <math>\begin{matrix} | + | <math>\begin{matrix} |
A{{A}^{T}}=U\Lambda {{V}^{T}}V\Lambda {{U}^{T}}=U{{\Lambda }^{2}}{{U}^{T}}, \\ | A{{A}^{T}}=U\Lambda {{V}^{T}}V\Lambda {{U}^{T}}=U{{\Lambda }^{2}}{{U}^{T}}, \\ | ||
{{A}^{T}}A=V\Lambda {{U}^{T}}U\Lambda {{V}^{T}}=V{{\Lambda }^{2}}{{V}^{T}}. \\ | {{A}^{T}}A=V\Lambda {{U}^{T}}U\Lambda {{V}^{T}}=V{{\Lambda }^{2}}{{V}^{T}}. \\ | ||
− | \end{matrix}</math> | + | \end{matrix}</math> |
</center> | </center> | ||
Домножуючи обидва вирази справа відповідно на <math>U</math> і <math>V</math> отримуємо | Домножуючи обидва вирази справа відповідно на <math>U</math> і <math>V</math> отримуємо | ||
<center> | <center> | ||
− | <math>\begin{matrix} | + | <math>\begin{matrix} |
A{{A}^{T}}U=U{{\Lambda }^{2}}, \\ | A{{A}^{T}}U=U{{\Lambda }^{2}}, \\ | ||
{{A}^{T}}AV=V{{\Lambda }^{2}}. \\ | {{A}^{T}}AV=V{{\Lambda }^{2}}. \\ | ||
− | \end{matrix}</math> | + | \end{matrix}</math> |
</center> | </center> | ||
З цього випливає, що стовпці матриці <math>U</math> є власними векторами матриці <math>A{{A}^{T}},</math> а квадрати сингулярних чисел <math>\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}})</math> - її власними числами. Також стовпці матриці <math>V</math> є власними векторами матриці <math>{{A}^{T}}A,</math> а квадрати сингулярних чисел є її власними числами. | З цього випливає, що стовпці матриці <math>U</math> є власними векторами матриці <math>A{{A}^{T}},</math> а квадрати сингулярних чисел <math>\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}})</math> - її власними числами. Також стовпці матриці <math>V</math> є власними векторами матриці <math>{{A}^{T}}A,</math> а квадрати сингулярних чисел є її власними числами. | ||
Рядок 103: | Рядок 103: | ||
Розглянемо зміну довжини вектора <math>x</math> до і після його множення зліва на матрицю <math>A.</math> Евклидова норма вектора визначена як | Розглянемо зміну довжини вектора <math>x</math> до і після його множення зліва на матрицю <math>A.</math> Евклидова норма вектора визначена як | ||
+ | <center> | ||
+ | <math>\|\mathbf{x}\|_{E}^{2}={{\mathbf{x}}^{T}}\mathbf{x}.</math> | ||
+ | </center> | ||
+ | Якщо матриця <math>A.</math> ортогональна, довжина вектора <math>A\mathbf{x}</math> залишається незмінною. В іншому випадку можна вирахувати, наскільки матриця <math>A</math> розтянула вектор <math>x</math>.<br> | ||
+ | Евклидова норма матриці є максимальний коефіцієнт розтягування довільного вектора <math>x</math> заданої матрицею <math>A.</math> | ||
+ | <center> | ||
+ | <math>\|A\|_{E}=\underset{\|\mathbf{x}\|=1}{\max }\,\left( \frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|} \right).</math> | ||
+ | </center> | ||
+ | Альтернативою Евклідової нормі є норма Фробеніуса: | ||
+ | <center> | ||
+ | <math>\|A\|_{F}=\sqrt{\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{a_{ij}^{2}}}}.</math> | ||
+ | </center> | ||
+ | Якщо відомо сингулярне розкладання, то обидві ці норми легко обчислити. Нехай <math>{{\lambda }_{1}},\ldots ,{{\lambda }_{r}}~</math> - сингулярні числа матриці<math>A,</math> відмінні від нуля. Тоді | ||
+ | <center> | ||
+ | <math>\|A\|_{E}={{\lambda }_{1}},</math> | ||
+ | </center> | ||
+ | <center>і</center> | ||
+ | <center> | ||
+ | <math>\|A\|_{F}=\sqrt{\sum\limits_{k=1}^{r}{\lambda _{k}^{2}}}.</math> | ||
+ | </center> | ||
+ | Сингулярні числа матриці <math>A</math> - це довжини осей еліпсоїда, заданого безліччю | ||
+ | <center> | ||
+ | <math>\left. \{A\mathbf{x} \right|\|\mathbf{x}\|_{E}=1\}.</math> | ||
+ | </center> | ||
− | <math>\|\mathbf{ | + | = Знаходження псевдооберненої матриці за допомогою SVD = |
+ | |||
+ | Якщо <math>(m\times n)</math> - матриця <math>A</math> є виродженою або прямокутною, то оберненої матриці <math>{{A}^{-1}}</math> для неї не існує. Однак для <math>A</math> може бути знайдена псевдообернена матриця <math>{{A}^{+}}</math> - така матриця, для якої виконуються умови | ||
+ | <center> | ||
+ | <math>\begin{array} | ||
+ | {{{A}^{+}}A={{I}_{n}}, \\ | ||
+ | A{{A}^{+}}={{I}_{m}}, \\ | ||
+ | {{A}^{+}}A{{A}^{+}}={{A}^{+}}, \\ | ||
+ | A{{A}^{+}}A=A. \\ | ||
+ | }\end{array}</math> | ||
+ | </center> | ||
+ | Нехай знайдено розкладання матриці виду | ||
+ | <center> | ||
+ | <math>A=U\Lambda {{V}^{T}},</math> | ||
+ | </center> | ||
+ | де <math>\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}}),~r=\min (m,n)~</math> і <math>{{U}^{T}}U={{I}_{m}},V{{V}^{T}}={{I}_{n}}.</math> Тоді матриця <math>{{A}^{+}}={{V}^{T}}{{\Lambda }^{-1}}U</math> є для матриці <math>A</math> псевдооберненою. Дійсно, <math>{{A}^{+}}A=V{{\Lambda }^{-1}}{{U}^{T}}U\Lambda {{V}^{T}}={{I}_{n}},~A{{A}^{+}}=U\Lambda {{V}^{T}}V{{\Lambda }^{-1}}{{U}^{T}}={{I}_{m}}.</math> | ||
+ | |||
+ | = Метод найменших квадратів і число обумовленості = | ||
+ | Задача найменших квадратів ставиться наступним чином. Дано дійсна <math>(m\times n)-</math>матриця <math>A</math> і дійсний <math>(m)-</math>вектор <math>Y.</math> Потрібно знайти дійсний <math>(n)-</math>вектор<math>\mathbf{w},</math> що мінімізує Евклідову довжину вектора нев'язки, | ||
+ | <center> | ||
+ | <math>\|Y-A\mathbf{w}\|_{E}\to \min.</math> | ||
+ | </center> | ||
+ | Рішення задачі найменших квадратів - | ||
+ | <center> | ||
+ | <math>\mathbf{w}={{({{A}^{T}}A)}^{-1}}({{A}^{T}}Y).</math> | ||
+ | </center> | ||
+ | Для відшукання рішення <math>\mathbf{w}</math> потрібно звернути матрицю <math>{{A}^{T}}A.</math> Для квадратних матриць <math>A</math> число обумовленості <math>\kappa(A)</math> визначено відношенням | ||
+ | <center> | ||
+ | <math>\kappa (A)=\|A\|_{E}\|{{A}^{-1}}\|_{E}.</math> | ||
+ | </center> | ||
+ | З формули евклідової норми матриці і попередньої формули випливає, що число обумовленості матриці є ставлення її першого сингулярного числа до останнього. | ||
+ | <center> | ||
+ | <math>\kappa (A)=\frac{{{\lambda }_{1}}}{{{\lambda }_{n}}}.</math> | ||
+ | </center> | ||
+ | Отже, число обумовленості матриці <math>{{A}^{T}}A</math> є квадрат числа обумовленості матриці <math>A.</math> Це висловлювання справедливо і для вироджених матриць, якщо вважати число обумовленості як відношення, <math>{{\lambda }_{1}}/{{\lambda }_{r}},~r~</math> - ранг матриці <math>A.</math> Тому для отримання звернення, стійкого до малих змін значень матриці <math>A,</math> використовується усічене SVD. | ||
+ | |||
+ | = Усічене SVD при зверненні матриць = | ||
+ | |||
+ | Нехай матриця <math>A</math> представлена у вигляді <math>A=U\Lambda {{V}^{T}}.</math> Тоді при знаходженні оберненої матриці <math>{{A}^{+}}=V{{\Lambda }^{-1}}{{U}^{T}}~</math> в силу ортогональності матриць <math>U</math> і <math>V</math> і в силу умови убування діагональних елементів матриці <math>\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{n}}),</math> псевдообернена матриця <math>{{A}^{+}}</math> буде більш залежати від тих елементів матриці | ||
+ | <math>\Lambda,</math> які мають менші значення, ніж від перших сингулярних чисел. Дійсно, якщо матриця <math>A</math> має сингулярні числа <math>{{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{n}},</math> то сингулярні числа матриці <math>{{A}^{+}}</math> дорівнюють | ||
+ | <center> | ||
+ | <math>{{\Lambda }^{-1}}=\text{diag}(\frac{1}{{{\lambda }_{1}}},...,\frac{1}{{{\lambda }_{n}}})</math> | ||
+ | </center> | ||
+ | <center>і</center> | ||
+ | <center> | ||
+ | <math>\frac{1}{{{\lambda }_{1}}}\le \frac{1}{{{\lambda }_{2}}}...\le \frac{1}{{{\lambda }_{n}}}.</math> | ||
+ | </center> | ||
+ | Вважаючи перший сингулярних чисел визначальними власний простір матриці <math>A,</math> використовуємо при зверненні матриці <math>A</math> перша <math>s</math> сингулярність чисел, <math>s\le \text{rank}A.</math> Тоді обернена матриця <math>{{A}^{+}}</math> буде знайдена як <math>{{A}^{+}}=V\Lambda _{s}^{-1}{{U}^{T}}.</math> | ||
+ | |||
+ | Визначимо усічену псевдообернену матрицю <math>A_{s}^{+}~</math> як | ||
+ | <center> | ||
+ | <math>A_{s}^{+}=V\Lambda _{s}^{-1}{{U}^{T}},</math> | ||
+ | </center> | ||
+ | де <math>\Lambda _{s}^{-1}=\text{diag}(\lambda _{1}^{-1},...,\lambda _{s}^{-1},0,...,0)~</math> - | ||
+ | <math>(n\times n)-</math> діагональна матриця. | ||
= Список використаних літератури = | = Список використаних літератури = |
Поточна версія на 10:05, 1 березня 2012
Дана стаття являється неперевіреним навчальним завданням.
До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону. |
Прізвище | Чура |
Ім'я | Наталя |
По-батькові | Ярославівна |
Факультет | ФІС |
Група | СНм-51 |
Залікова книжка | СНм-11-256 |
Сингулярне розкладання (Singular Value Decomposition, SVD) – декомпозиція речовинної матриці з метою її приведення до канонічного виду. Сингулярне розкладання є зручним методом при роботі з матрицями. Воно показує геометричну структуру матриці і дозволяє наочно представити наявні дані. Сингулярне розкладання використовується при вирішенні найрізноманітніших завдань - від наближення методом найменших квадратів і рішення систем рівнянь до стиснення зображень. При цьому використовуються різні властивості сингулярного розкладання, наприклад, здатність показувати ранг матриці, наближати матриці даного рангу. SVD дозволяє обчислювати зворотні і псевдообернених матриць великого розміру, що робить його корисним інструментом при вирішенні задач регресійного аналізу.
Для будь-якої речовинної [math](n\times n)[/math] - матриці [math]A[/math] існує дві речовинні ортогональні [math](n\times n)[/math] - матриці [math]U[/math] і [math]V[/math] й такі, що [math]{{U}^{T}}AV[/math] - діагональна матриця [math]\Lambda[/math],
[math]{{U}^{T}}AV=\Lambda[/math].
Матриці [math]U[/math] і [math]V[/math] вибираються так, щоб диагональні елементи матриці [math]\Lambda[/math] мали вид
[math]{{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{r}}\gt {{\lambda }_{r+1}}=...={{\lambda }_{n}}=0[/math],
[math]{{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{n}}\gt 0~[/math].
Індекс [math]r[/math] елемента [math]{{\lambda }_{r}}[/math] є фактична розмірність власного простору матриці [math]A[/math].
Стовпці матриць [math]U[/math] і [math]V[/math] називаються відповідно лівими і правими сингулярними векторами, а значення діагоналі матриці [math]\Lambda[/math] називаються сингулярними числами.
Еквівалентна запис сингулярного розкладання [math]A=U\Lambda {{V}^{T}}[/math].
Наприклад, матриця
[math]A=\left( \begin{matrix}
0.96 & 1.72 \\
2.28 & 0.96 \\
\end{matrix} \right)[/math]
має сингулярне розкладання
[math]A=U\Lambda {{V}^{T}}=\left( \begin{matrix}
0.6 & 0.8 \\
0.8 & -0.6 \\
\end{matrix} \right)\left( \begin{matrix}
3 & 0 \\
0 & 1 \\
\end{matrix} \right){{\left( \begin{matrix}
0.8 & -0.6 \\
0.6 & 0.8 \\
\end{matrix} \right)}^{T}}[/math]
Легко побачити, що матриці [math]U[/math] і [math]V[/math] ортогональні,
і сума квадратів значень їх стовпців дорівнює одиниці.
Зміст
Геометричний зміст SVD
Нехай матриці [math]A[/math] поставлений у відповідність лінійний оператор. Cінгулярне розкладання можна переформулювати в геометричних термінах. Лінійний оператор, що відображає елементи простору [math]{{R}^{n}}[/math] в себе представимо у вигляді послідовно виконуваних лінійних операторів обертання, розтягування і обертання. Тому компоненти сингулярного розкладання наочно показують геометричні зміни при відображенні лінійним оператором [math]A[/math] безлічі векторів з векторного простору в себе або в векторний простір іншої розмірності.
Простори матриці і SVD
Сингулярне розкладання дозволяє знайти ортогональні базиси різних векторних просторів розкладається матриці
[math]{{A}_{(n\times n)}}={{U}_{(n\times n)}}{{\Lambda }_{(n\times n)}}V_{(n\times n)}^{T}.[/math]
Для прямокутних матриць існує так зване економне уявлення сингулярного розкладання матриці
[math]{{A}_{(m\times n)}}={{U}_{(m\times m)}}{{\Lambda }_{(m\times n)}}V_{(n\times n)}^{T}[/math]
Згідно з цим поданням при [math]m\gt n[/math], діагональна матриця [math]\Lambda[/math] має порожні рядки (їх елементи рівні нулю), а при [math]m\lt n[/math] - порожні стовпці. Тому існує ще одне економне подання
[math]{{A}_{(m\times n)}}={{U}_{(m\times r)}}{{\Lambda }_{(r\times r)}}V_{(r\times n)}^{T},[/math]
в якому [math]r=\min (m,n).[/math] Нуль-простір матриці [math]A[/math] - набір векторів [math]\mathbf{x}[/math], для якого справедливе висловлювання [math]A\mathbf{x}=\mathbf{0}.[/math] Власне простір матриці [math]A[/math] - набір векторів [math]\mathbf{b}[/math], при якому рівняння [math]A\mathbf{x}=\mathbf{b}[/math] має ненульове рішення для [math]\mathbf{x}[/math]. Позначимо [math]{{\mathbf{u}}_{k}}[/math] і [math]{{\mathbf{v}}_{k}}[/math] - стовпці матриць [math]U[/math] і [math]V[/math]. Тоді розкладання [math]A=U\Lambda {{V}^{T}}~[/math] може бути записано у вигляді: [math]A=\sum\limits_{k=1}^{r}{{{A}_{k}}},\text{ }[/math] де [math]~{{A}_{k}}={{\mathbf{u}}_{k}}{{\lambda }_{k}}\mathbf{v}_{k}^{T}.[/math] Якщо сингулярне число [math]{{\lambda }_{k}}=0,[/math] то [math]A{{\mathbf{v}}_{k}}=\mathbf{0}~[/math] і [math]{{\mathbf{v}}_{k}}[/math] знаходиться в нуль-просторі матриці [math]A[/math], а якщо сингулярне число [math]{{\lambda }_{k}}\ne 0,[/math] то вектор [math]{{\mathbf{u}}_{k}}[/math] перебувають у власному просторі матриці [math]A[/math]. Отже, можна сконструювати базиси для різних векторних підпросторів, визначених матрицею [math]A[/math]. Hабір векторів [math]{{\mathbf{v}}_{1}},\ldots ,{{\mathbf{v}}_{k}}[/math] у векторному просторі [math]V~[/math] формує базис для [math]V~[/math], якщо будь-який вектор [math]\mathbf{x}[/math] з [math]V~[/math] можна представити у вигляді лінійної комбінації векторів [math]{{\mathbf{v}}_{1}},\ldots ,{{\mathbf{v}}_{k}}[/math] єдиним способом. Нехай [math]{{V}_{0}}[/math] буде набором тих стовпців [math]{{\mathbf{u}}_{k}},[/math] для яких [math]{{\lambda }_{k}}\ne 0,[/math] а [math]{{V}_{1}}[/math] - всі інші стовпці [math]{{\lambda }_{k}}\ne 0,[/math]. Також, нехай [math]{{U}_{0}}[/math] буде набором стовпців [math]{{\mathbf{u}}_{k}},[/math] для яких [math]{{\lambda }_{k}}\ne 0,[/math] а [math]{{U}_{1}}[/math] - всі інші стовпці [math]{{\mathbf{u}}_{k}},[/math] включаючи і ті, для яких [math]k\gt n.[/math] Тоді, якщо [math]r[/math] - кількість ненульових сингулярних чисел, то [math]r[/math] мається стовпців в наборі [math]{{V}_{0}}[/math] і [math]n-r~[/math] стовпців в наборі [math]{{V}_{1}}[/math] і [math]{{U}_{1}},[/math] а також [math]m-n+r[/math] стовпців в наборі [math]{{U}_{0}}.[/math] Кожен з цих наборів формує базис векторного простору матриці [math]A[/math]:
- [math]{{V}_{0}}[/math] - Ортонормований базис для ортогонального комплементарного нуль-простору [math]A[/math],
- [math]{{V}_{1}}[/math] - Ортонормований базис для нуль-простору [math]A[/math],
- [math]{{U}_{0}}[/math] - Ортонормований базис для власного простору [math]A[/math],
- [math]{{U}_{1}}[/math] - Ортонормований базис для ортогонального комплементарного нуль-простору [math]A[/math].
SVD і власні числа матриці
Сингулярне розкладання володіє властивістю, яке пов'язує задачу відшукання сингулярного розкладання і завдання відшукання власних векторів. Власний вектор [math]\mathbf{x}[/math] матриці [math]A[/math] - такий вектор, при якому виконується умова [math]A\mathbf{x}=\lambda \mathbf{x},~[/math] число [math]\lambda[/math] називається власним числом. Так як матриці [math]U[/math] і [math]V[/math] ортогональні, то
[math]\begin{matrix}
A{{A}^{T}}=U\Lambda {{V}^{T}}V\Lambda {{U}^{T}}=U{{\Lambda }^{2}}{{U}^{T}}, \\
{{A}^{T}}A=V\Lambda {{U}^{T}}U\Lambda {{V}^{T}}=V{{\Lambda }^{2}}{{V}^{T}}. \\
\end{matrix}[/math]
Домножуючи обидва вирази справа відповідно на [math]U[/math] і [math]V[/math] отримуємо
[math]\begin{matrix}
A{{A}^{T}}U=U{{\Lambda }^{2}}, \\
{{A}^{T}}AV=V{{\Lambda }^{2}}. \\
\end{matrix}[/math]
З цього випливає, що стовпці матриці [math]U[/math] є власними векторами матриці [math]A{{A}^{T}},[/math] а квадрати сингулярних чисел [math]\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}})[/math] - її власними числами. Також стовпці матриці [math]V[/math] є власними векторами матриці [math]{{A}^{T}}A,[/math] а квадрати сингулярних чисел є її власними числами.
SVD і норма матриць
Розглянемо зміну довжини вектора [math]x[/math] до і після його множення зліва на матрицю [math]A.[/math] Евклидова норма вектора визначена як
[math]\|\mathbf{x}\|_{E}^{2}={{\mathbf{x}}^{T}}\mathbf{x}.[/math]
Якщо матриця [math]A.[/math] ортогональна, довжина вектора [math]A\mathbf{x}[/math] залишається незмінною. В іншому випадку можна вирахувати, наскільки матриця [math]A[/math] розтянула вектор [math]x[/math].
Евклидова норма матриці є максимальний коефіцієнт розтягування довільного вектора [math]x[/math] заданої матрицею [math]A.[/math]
[math]\|A\|_{E}=\underset{\|\mathbf{x}\|=1}{\max }\,\left( \frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|} \right).[/math]
Альтернативою Евклідової нормі є норма Фробеніуса:
[math]\|A\|_{F}=\sqrt{\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{a_{ij}^{2}}}}.[/math]
Якщо відомо сингулярне розкладання, то обидві ці норми легко обчислити. Нехай [math]{{\lambda }_{1}},\ldots ,{{\lambda }_{r}}~[/math] - сингулярні числа матриці[math]A,[/math] відмінні від нуля. Тоді
[math]\|A\|_{E}={{\lambda }_{1}},[/math]
[math]\|A\|_{F}=\sqrt{\sum\limits_{k=1}^{r}{\lambda _{k}^{2}}}.[/math]
Сингулярні числа матриці [math]A[/math] - це довжини осей еліпсоїда, заданого безліччю
[math]\left. \{A\mathbf{x} \right|\|\mathbf{x}\|_{E}=1\}.[/math]
Знаходження псевдооберненої матриці за допомогою SVD
Якщо [math](m\times n)[/math] - матриця [math]A[/math] є виродженою або прямокутною, то оберненої матриці [math]{{A}^{-1}}[/math] для неї не існує. Однак для [math]A[/math] може бути знайдена псевдообернена матриця [math]{{A}^{+}}[/math] - така матриця, для якої виконуються умови
[math]\begin{array}
{{{A}^{+}}A={{I}_{n}}, \\
A{{A}^{+}}={{I}_{m}}, \\
{{A}^{+}}A{{A}^{+}}={{A}^{+}}, \\
A{{A}^{+}}A=A. \\
}\end{array}[/math]
Нехай знайдено розкладання матриці виду
[math]A=U\Lambda {{V}^{T}},[/math]
де [math]\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}}),~r=\min (m,n)~[/math] і [math]{{U}^{T}}U={{I}_{m}},V{{V}^{T}}={{I}_{n}}.[/math] Тоді матриця [math]{{A}^{+}}={{V}^{T}}{{\Lambda }^{-1}}U[/math] є для матриці [math]A[/math] псевдооберненою. Дійсно, [math]{{A}^{+}}A=V{{\Lambda }^{-1}}{{U}^{T}}U\Lambda {{V}^{T}}={{I}_{n}},~A{{A}^{+}}=U\Lambda {{V}^{T}}V{{\Lambda }^{-1}}{{U}^{T}}={{I}_{m}}.[/math]
Метод найменших квадратів і число обумовленості
Задача найменших квадратів ставиться наступним чином. Дано дійсна [math](m\times n)-[/math]матриця [math]A[/math] і дійсний [math](m)-[/math]вектор [math]Y.[/math] Потрібно знайти дійсний [math](n)-[/math]вектор[math]\mathbf{w},[/math] що мінімізує Евклідову довжину вектора нев'язки,
[math]\|Y-A\mathbf{w}\|_{E}\to \min.[/math]
Рішення задачі найменших квадратів -
[math]\mathbf{w}={{({{A}^{T}}A)}^{-1}}({{A}^{T}}Y).[/math]
Для відшукання рішення [math]\mathbf{w}[/math] потрібно звернути матрицю [math]{{A}^{T}}A.[/math] Для квадратних матриць [math]A[/math] число обумовленості [math]\kappa(A)[/math] визначено відношенням
[math]\kappa (A)=\|A\|_{E}\|{{A}^{-1}}\|_{E}.[/math]
З формули евклідової норми матриці і попередньої формули випливає, що число обумовленості матриці є ставлення її першого сингулярного числа до останнього.
[math]\kappa (A)=\frac{{{\lambda }_{1}}}{{{\lambda }_{n}}}.[/math]
Отже, число обумовленості матриці [math]{{A}^{T}}A[/math] є квадрат числа обумовленості матриці [math]A.[/math] Це висловлювання справедливо і для вироджених матриць, якщо вважати число обумовленості як відношення, [math]{{\lambda }_{1}}/{{\lambda }_{r}},~r~[/math] - ранг матриці [math]A.[/math] Тому для отримання звернення, стійкого до малих змін значень матриці [math]A,[/math] використовується усічене SVD.
Усічене SVD при зверненні матриць
Нехай матриця [math]A[/math] представлена у вигляді [math]A=U\Lambda {{V}^{T}}.[/math] Тоді при знаходженні оберненої матриці [math]{{A}^{+}}=V{{\Lambda }^{-1}}{{U}^{T}}~[/math] в силу ортогональності матриць [math]U[/math] і [math]V[/math] і в силу умови убування діагональних елементів матриці [math]\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{n}}),[/math] псевдообернена матриця [math]{{A}^{+}}[/math] буде більш залежати від тих елементів матриці [math]\Lambda,[/math] які мають менші значення, ніж від перших сингулярних чисел. Дійсно, якщо матриця [math]A[/math] має сингулярні числа [math]{{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{n}},[/math] то сингулярні числа матриці [math]{{A}^{+}}[/math] дорівнюють
[math]{{\Lambda }^{-1}}=\text{diag}(\frac{1}{{{\lambda }_{1}}},...,\frac{1}{{{\lambda }_{n}}})[/math]
[math]\frac{1}{{{\lambda }_{1}}}\le \frac{1}{{{\lambda }_{2}}}...\le \frac{1}{{{\lambda }_{n}}}.[/math]
Вважаючи перший сингулярних чисел визначальними власний простір матриці [math]A,[/math] використовуємо при зверненні матриці [math]A[/math] перша [math]s[/math] сингулярність чисел, [math]s\le \text{rank}A.[/math] Тоді обернена матриця [math]{{A}^{+}}[/math] буде знайдена як [math]{{A}^{+}}=V\Lambda _{s}^{-1}{{U}^{T}}.[/math]
Визначимо усічену псевдообернену матрицю [math]A_{s}^{+}~[/math] як
[math]A_{s}^{+}=V\Lambda _{s}^{-1}{{U}^{T}},[/math]
де [math]\Lambda _{s}^{-1}=\text{diag}(\lambda _{1}^{-1},...,\lambda _{s}^{-1},0,...,0)~[/math] - [math](n\times n)-[/math] діагональна матриця.
Список використаних літератури
1. Голуб Дж., Ван-Лоун Ч. Матричные вычисления. М.: Мир. 1999.
2. Деммель Дж. Вычислительная линейная алгебра. URSS. 2001.
3. Логинов Н.В. Сингулярное разложение матриц. М.: МГАПИ. 1996.
4. Стренг Г. Линейная алгебра и ее применения. М.: Мир. 1980.
5. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир. 1969.
6. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир. 1989.
7. Vetterling W. T. Flannery B. P. Numerical Recipies in C: The Art of Scientific Computing. NY: Cambridge University Press. 1999.
Посилання
http://www.prip.tuwien.ac.at/teaching/ws/statistische-mustererkennung/apponly.pdf