Сингулярне розкладання

Дана стаття являється неперевіреним навчальним завданням. Студент: Чура Н. Я. Викладач: Назаревич О. Б. Термін до: 18 березня 2012 До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону.

Прізвище	Чура
Ім'я	Наталя
По-батькові	Ярославівна
Факультет	ФІС
Група	СНм-51
Залікова книжка	СНм-11-256

Сингулярне розкладання (Singular Value Decomposition, SVD) – декомпозиція речовинної матриці з метою її приведення до канонічного виду. Сингулярне розкладання є зручним методом при роботі з матрицями. Воно показує геометричну структуру матриці і дозволяє наочно представити наявні дані. Сингулярне розкладання використовується при вирішенні найрізноманітніших завдань - від наближення методом найменших квадратів і рішення систем рівнянь до стиснення зображень. При цьому використовуються різні властивості сингулярного розкладання, наприклад, здатність показувати ранг матриці, наближати матриці даного рангу. SVD дозволяє обчислювати зворотні і псевдообернених матриць великого розміру, що робить його корисним інструментом при вирішенні задач регресійного аналізу.
Для будь-якої речовинної $(n\times n)$ - матриці $A$ існує дві речовинні ортогональні $(n\times n)$ - матриці $U$ і $V$ й такі, що ${{U}^{T}}AV$ - діагональна матриця $\Lambda$,

[math]{{U}^{T}}AV=\Lambda[/math].

Матриці $U$ і $V$ вибираються так, щоб диагональні елементи матриці $\Lambda$ мали вид

[math]{{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{r}}\gt {{\lambda }_{r+1}}=...={{\lambda }_{n}}=0[/math],

де $~r$ - ранг матриці$A$. Зокрема, якщо $A$ невироджена, то

[math]{{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{n}}\gt 0~[/math].

Індекс $r$ елемента ${{\lambda }_{r}}$ є фактична розмірність власного простору матриці $A$.
Стовпці матриць $U$ і $V$ називаються відповідно лівими і правими сингулярними векторами, а значення діагоналі матриці $\Lambda$ називаються сингулярними числами.
Еквівалентна запис сингулярного розкладання $A=U\Lambda {{V}^{T}}$.
Наприклад, матриця

[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]

Легко побачити, що матриці $U$ і $V$ ортогональні,

${{U}^{T}}U=U{{U}^{T}}=I$, також $~{{V}^{T}}V=V{{V}^{T}}=I$,

і сума квадратів значень їх стовпців дорівнює одиниці.

Геометричний зміст SVD

Нехай матриці $A$ поставлений у відповідність лінійний оператор. Cінгулярне розкладання можна переформулювати в геометричних термінах. Лінійний оператор, що відображає елементи простору ${{R}^{n}}$ в себе представимо у вигляді послідовно виконуваних лінійних операторів обертання, розтягування і обертання. Тому компоненти сингулярного розкладання наочно показують геометричні зміни при відображенні лінійним оператором $A$ безлічі векторів з векторного простору в себе або в векторний простір іншої розмірності.

Простори матриці і 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]

Згідно з цим поданням при $m\gt n$, діагональна матриця $\Lambda$ має порожні рядки (їх елементи рівні нулю), а при $m\lt n$ - порожні стовпці. Тому існує ще одне економне подання

[math]{{A}_{(m\times n)}}={{U}_{(m\times r)}}{{\Lambda }_{(r\times r)}}V_{(r\times n)}^{T},[/math]

в якому $r=\min (m,n).$ Нуль-простір матриці $A$ - набір векторів $\mathbf{x}$, для якого справедливе висловлювання $A\mathbf{x}=\mathbf{0}.$ Власне простір матриці $A$ - набір векторів $\mathbf{b}$, при якому рівняння $A\mathbf{x}=\mathbf{b}$ має ненульове рішення для $\mathbf{x}$. Позначимо ${{\mathbf{u}}_{k}}$ і ${{\mathbf{v}}_{k}}$ - стовпці матриць $U$ і $V$. Тоді розкладання $A=U\Lambda {{V}^{T}}~$ може бути записано у вигляді: $A=\sum\limits_{k=1}^{r}{{{A}_{k}}},\text{ }$ де $~{{A}_{k}}={{\mathbf{u}}_{k}}{{\lambda }_{k}}\mathbf{v}_{k}^{T}.$ Якщо сингулярне число ${{\lambda }_{k}}=0,$ то $A{{\mathbf{v}}_{k}}=\mathbf{0}~$ і ${{\mathbf{v}}_{k}}$ знаходиться в нуль-просторі матриці $A$, а якщо сингулярне число ${{\lambda }_{k}}\ne 0,$ то вектор ${{\mathbf{u}}_{k}}$ перебувають у власному просторі матриці $A$. Отже, можна сконструювати базиси для різних векторних підпросторів, визначених матрицею $A$. Hабір векторів ${{\mathbf{v}}_{1}},\ldots ,{{\mathbf{v}}_{k}}$ у векторному просторі $V~$ формує базис для $V~$, якщо будь-який вектор $\mathbf{x}$ з $V~$ можна представити у вигляді лінійної комбінації векторів ${{\mathbf{v}}_{1}},\ldots ,{{\mathbf{v}}_{k}}$ єдиним способом. Нехай ${{V}_{0}}$ буде набором тих стовпців ${{\mathbf{u}}_{k}},$ для яких ${{\lambda }_{k}}\ne 0,$ а ${{V}_{1}}$ - всі інші стовпці ${{\lambda }_{k}}\ne 0,$. Також, нехай ${{U}_{0}}$ буде набором стовпців ${{\mathbf{u}}_{k}},$ для яких ${{\lambda }_{k}}\ne 0,$ а ${{U}_{1}}$ - всі інші стовпці ${{\mathbf{u}}_{k}},$ включаючи і ті, для яких $k\gt n.$ Тоді, якщо $r$ - кількість ненульових сингулярних чисел, то $r$ мається стовпців в наборі ${{V}_{0}}$ і $n-r~$ стовпців в наборі ${{V}_{1}}$ і ${{U}_{1}},$ а також $m-n+r$ стовпців в наборі ${{U}_{0}}.$ Кожен з цих наборів формує базис векторного простору матриці $A$:

• ${{V}_{0}}$ - Ортонормований базис для ортогонального комплементарного нуль-простору $A$,
• ${{V}_{1}}$ - Ортонормований базис для нуль-простору $A$,
• ${{U}_{0}}$ - Ортонормований базис для власного простору $A$,
• ${{U}_{1}}$ - Ортонормований базис для ортогонального комплементарного нуль-простору $A$.

SVD і власні числа матриці

Сингулярне розкладання володіє властивістю, яке пов'язує задачу відшукання сингулярного розкладання і завдання відшукання власних векторів. Власний вектор $\mathbf{x}$ матриці $A$ - такий вектор, при якому виконується умова $A\mathbf{x}=\lambda \mathbf{x},~$ число $\lambda$ називається власним числом. Так як матриці $U$ і $V$ ортогональні, то

[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]

Домножуючи обидва вирази справа відповідно на $U$ і $V$ отримуємо

[math]\begin{matrix}
A{{A}^{T}}U=U{{\Lambda }^{2}},  \\
{{A}^{T}}AV=V{{\Lambda }^{2}}.  \\
\end{matrix}[/math]

З цього випливає, що стовпці матриці $U$ є власними векторами матриці $A{{A}^{T}},$ а квадрати сингулярних чисел $\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}})$ - її власними числами. Також стовпці матриці $V$ є власними векторами матриці ${{A}^{T}}A,$ а квадрати сингулярних чисел є її власними числами.

SVD і норма матриць

Розглянемо зміну довжини вектора $x$ до і після його множення зліва на матрицю $A.$ Евклидова норма вектора визначена як

[math]\|\mathbf{x}\|_{E}^{2}={{\mathbf{x}}^{T}}\mathbf{x}.[/math]

Якщо матриця $A.$ ортогональна, довжина вектора $A\mathbf{x}$ залишається незмінною. В іншому випадку можна вирахувати, наскільки матриця $A$ розтянула вектор $x$.
Евклидова норма матриці є максимальний коефіцієнт розтягування довільного вектора $x$ заданої матрицею $A.$

[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]

Якщо відомо сингулярне розкладання, то обидві ці норми легко обчислити. Нехай ${{\lambda }_{1}},\ldots ,{{\lambda }_{r}}~$ - сингулярні числа матриці$A,$ відмінні від нуля. Тоді

[math]\|A\|_{E}={{\lambda }_{1}},[/math]

і

[math]\|A\|_{F}=\sqrt{\sum\limits_{k=1}^{r}{\lambda _{k}^{2}}}.[/math]

Сингулярні числа матриці $A$ - це довжини осей еліпсоїда, заданого безліччю

[math]\left. \{A\mathbf{x} \right|\|\mathbf{x}\|_{E}=1\}.[/math]

Знаходження псевдооберненої матриці за допомогою SVD

Якщо $(m\times n)$ - матриця $A$ є виродженою або прямокутною, то оберненої матриці ${{A}^{-1}}$ для неї не існує. Однак для $A$ може бути знайдена псевдообернена матриця ${{A}^{+}}$ - така матриця, для якої виконуються умови

[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]

де $\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{r}}),~r=\min (m,n)~$ і ${{U}^{T}}U={{I}_{m}},V{{V}^{T}}={{I}_{n}}.$ Тоді матриця ${{A}^{+}}={{V}^{T}}{{\Lambda }^{-1}}U$ є для матриці $A$ псевдооберненою. Дійсно, ${{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}}.$

Метод найменших квадратів і число обумовленості

Задача найменших квадратів ставиться наступним чином. Дано дійсна $(m\times n)-$матриця $A$ і дійсний $(m)-$вектор $Y.$ Потрібно знайти дійсний $(n)-$вектор$\mathbf{w},$ що мінімізує Евклідову довжину вектора нев'язки,

[math]\|Y-A\mathbf{w}\|_{E}\to \min.[/math]

Рішення задачі найменших квадратів -

[math]\mathbf{w}={{({{A}^{T}}A)}^{-1}}({{A}^{T}}Y).[/math]

Для відшукання рішення $\mathbf{w}$ потрібно звернути матрицю ${{A}^{T}}A.$ Для квадратних матриць $A$ число обумовленості $\kappa(A)$ визначено відношенням

[math]\kappa (A)=\|A\|_{E}\|{{A}^{-1}}\|_{E}.[/math]

З формули евклідової норми матриці і попередньої формули випливає, що число обумовленості матриці є ставлення її першого сингулярного числа до останнього.

[math]\kappa (A)=\frac{{{\lambda }_{1}}}{{{\lambda }_{n}}}.[/math]

Отже, число обумовленості матриці ${{A}^{T}}A$ є квадрат числа обумовленості матриці $A.$ Це висловлювання справедливо і для вироджених матриць, якщо вважати число обумовленості як відношення, ${{\lambda }_{1}}/{{\lambda }_{r}},~r~$ - ранг матриці $A.$ Тому для отримання звернення, стійкого до малих змін значень матриці $A,$ використовується усічене SVD.

Усічене SVD при зверненні матриць

Нехай матриця $A$ представлена ​​у вигляді $A=U\Lambda {{V}^{T}}.$ Тоді при знаходженні оберненої матриці ${{A}^{+}}=V{{\Lambda }^{-1}}{{U}^{T}}~$ в силу ортогональності матриць $U$ і $V$ і в силу умови убування діагональних елементів матриці $\Lambda =\text{diag}({{\lambda }_{1}},...,{{\lambda }_{n}}),$ псевдообернена матриця ${{A}^{+}}$ буде більш залежати від тих елементів матриці $\Lambda,$ які мають менші значення, ніж від перших сингулярних чисел. Дійсно, якщо матриця $A$ має сингулярні числа ${{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{n}},$ то сингулярні числа матриці ${{A}^{+}}$ дорівнюють

[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]

Вважаючи перший сингулярних чисел визначальними власний простір матриці $A,$ використовуємо при зверненні матриці $A$ перша $s$ сингулярність чисел, $s\le \text{rank}A.$ Тоді обернена матриця ${{A}^{+}}$ буде знайдена як ${{A}^{+}}=V\Lambda _{s}^{-1}{{U}^{T}}.$

Визначимо усічену псевдообернену матрицю $A_{s}^{+}~$ як

[math]A_{s}^{+}=V\Lambda _{s}^{-1}{{U}^{T}},[/math]

де $\Lambda _{s}^{-1}=\text{diag}(\lambda _{1}^{-1},...,\lambda _{s}^{-1},0,...,0)~$ - $(n\times n)-$ діагональна матриця.

Список використаних літератури

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