Відмінності між версіями «Сингулярне розкладання»

(Усічене SVD при зверненні матриць)
Рядок 169: Рядок 169:
 
<center>
 
<center>
 
  <math>{{\Lambda }^{-1}}=\text{diag}(\frac{1}{{{\lambda }_{1}}},...,\frac{1}{{{\lambda }_{n}}})</math>
 
  <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>
 
  <math>\frac{1}{{{\lambda }_{1}}}\le \frac{1}{{{\lambda }_{2}}}...\le \frac{1}{{{\lambda }_{n}}}.</math>
 
</center>
 
</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> <\br>
 +
Визначимо усічену псевдообернену матрицю <math>A_{s}^{+}~</math> як
 
<center>
 
<center>
 
  <math>A_{s}^{+}=V\Lambda _{s}^{-1}{{U}^{T}},</math>
 
  <math>A_{s}^{+}=V\Lambda _{s}^{-1}{{U}^{T}},</math>
Рядок 180: Рядок 181:
 
де <math>\Lambda _{s}^{-1}=\text{diag}(\lambda _{1}^{-1},...,\lambda _{s}^{-1},0,...,0)~</math> -  
 
де <math>\Lambda _{s}^{-1}=\text{diag}(\lambda _{1}^{-1},...,\lambda _{s}^{-1},0,...,0)~</math> -  
 
<math>(n\times n)-</math> діагональна матриця.
 
<math>(n\times n)-</math> діагональна матриця.
 
 
  
 
= Список використаних літератури =
 
= Список використаних літератури =

Версія за 01:49, 1 березня 2012

Blue check.png Дана стаття являється неперевіреним навчальним завданням.
Студент: Чура Н. Я.
Викладач: Назаревич О. Б.
Термін до: 18 березня 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]~r[/math] - ранг матриці[math]A[/math]. Зокрема, якщо [math]A[/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] ортогональні,

[math]{{U}^{T}}U=U{{U}^{T}}=I[/math], також [math]~{{V}^{T}}V=V{{V}^{T}}=I[/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]{{\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] <\br> Визначимо усічену псевдообернену матрицю [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