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

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

До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону.


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

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

LaTeX: {{U}^{T}}AV=\Lambda .

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

LaTeX: {{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{r}}>{{\lambda }_{r+1}}=...={{\lambda }_{n}}=0,
де LaTeX: ~r - ранг матриціLaTeX: A. Зокрема, якщо LaTeX: A невироджена, то
LaTeX: {{\lambda }_{1}}\ge {{\lambda }_{2}}\ge ...\ge {{\lambda }_{n}}>0~.

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

LaTeX: A=\left( \begin{matrix}
  0.96 & 1.72  \\
  2.28 & 0.96  \\
\end{matrix} \right)

має сингулярне розкладання

LaTeX: 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}}

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

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

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

Зміст

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

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

Простори матриці і SVD

Сингулярне розкладання дозволяє знайти ортогональні базиси різних векторних просторів розкладається матриці

LaTeX: {{A}_{(n\times n)}}={{U}_{(n\times n)}}{{\Lambda }_{(n\times n)}}V_{(n\times n)}^{T}.

Для прямокутних матриць існує так зване економне уявлення сингулярного розкладання матриці

LaTeX: {{A}_{(m\times n)}}={{U}_{(m\times m)}}{{\Lambda }_{(m\times n)}}V_{(n\times n)}^{T}

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

LaTeX: {{A}_{(m\times n)}}={{U}_{(m\times r)}}{{\Lambda }_{(r\times r)}}V_{(r\times n)}^{T},

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

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

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

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

LaTeX: \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}

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

LaTeX: \begin{matrix}
  A{{A}^{T}}U=U{{\Lambda }^{2}},  \\
  {{A}^{T}}AV=V{{\Lambda }^{2}}.  \\
\end{matrix}

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

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

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

LaTeX: \|\mathbf{x}\|_{E}^{2}={{\mathbf{x}}^{T}}\mathbf{x}.

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

LaTeX: \|A\|_{E}=\underset{\|\mathbf{x}\|=1}{\max }\,\left( \frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|} \right).

Альтернативою Евклідової нормі є норма Фробеніуса:

LaTeX: \|A\|_{F}=\sqrt{\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{a_{ij}^{2}}}}.

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

LaTeX: \|A\|_{E}={{\lambda }_{1}},
і
LaTeX: \|A\|_{F}=\sqrt{\sum\limits_{k=1}^{r}{\lambda _{k}^{2}}}.

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

LaTeX: \left. \{A\mathbf{x} \right|\|\mathbf{x}\|_{E}=1\}.

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

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

LaTeX: \begin{array}
  {{{A}^{+}}A={{I}_{n}},  \\
  A{{A}^{+}}={{I}_{m}},  \\
  {{A}^{+}}A{{A}^{+}}={{A}^{+}},  \\
  A{{A}^{+}}A=A.  \\
}\end{array}

Нехай знайдено розкладання матриці виду

LaTeX: A=U\Lambda {{V}^{T}},

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

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

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

LaTeX: \|Y-A\mathbf{w}\|_{E}\to \min.

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

LaTeX: \mathbf{w}={{({{A}^{T}}A)}^{-1}}({{A}^{T}}Y).

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

LaTeX: \kappa (A)=\|A\|_{E}\|{{A}^{-1}}\|_{E}.

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

LaTeX: \kappa (A)=\frac{{{\lambda }_{1}}}{{{\lambda }_{n}}}.

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

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

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

LaTeX: {{\Lambda }^{-1}}=\text{diag}(\frac{1}{{{\lambda }_{1}}},...,\frac{1}{{{\lambda }_{n}}})
і
LaTeX: \frac{1}{{{\lambda }_{1}}}\le \frac{1}{{{\lambda }_{2}}}...\le \frac{1}{{{\lambda }_{n}}}.

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

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

LaTeX: A_{s}^{+}=V\Lambda _{s}^{-1}{{U}^{T}},

де LaTeX: \Lambda _{s}^{-1}=\text{diag}(\lambda _{1}^{-1},...,\lambda _{s}^{-1},0,...,0)~ - LaTeX: (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

Особисті інструменти
реклама