Русская Википедия:Сингулярное разложение

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Singular-Value-Decomposition.svg
Геометрический смысл сингулярного разложения в двумерном случае.

Сингуля́рное разложе́ние — определённого типа разложение прямоугольной матрицы, имеющее широкое применение, в силу своей наглядной геометрической интерпретации, при решении многих прикладных задач. Переформулировка сингулярного разложения, так называемое разложение Шмидта, имеет приложения в квантовой теории информации, например, в запутанности.

Сингулярное разложение матрицы <math>M</math> позволяет вычислять сингулярные числа данной матрицы, а также левые и правые сингулярные векторы матрицы <math>M</math>:

  • левые сингулярные векторы матрицы <math>M</math> — это собственные векторы матрицы <math>MM^{*}</math>;
  • правые сингулярные векторы матрицы <math>M</math> — это собственные векторы матрицы <math>M^{*}M</math>.

Где <math>M^{*}</math>— эрмитово-сопряжённая матрица к матрице <math>M</math>, для вещественной матрицы <math>M^{*} = M^{T} </math>.

Сингулярные числа матрицы не следует путать с собственными числами той же матрицы.

Сингулярное разложение является удобным при вычислении ранга матрицы, ядра матрицы и псевдообратной матрицы.

Сингулярное разложение также используется для приближения матриц матрицами заданного ранга.

Определение

Пусть матрица <math>M</math> порядка <math>m \times n</math> состоит из элементов из поля <math>K</math>, где <math>K</math> — либо поле вещественных чисел, либо поле комплексных чисел.

Сингулярные числа и сингулярные векторы

Неотрицательное вещественное число <math>\sigma</math> называется сингулярным числом матрицы <math>M</math>, когда существуют два вектора единичной длины <math>u \in K^m</math> и <math>v \in K^n</math> такие, что:

<math>Mv = \sigma u,</math> и <math>M^{*} u = \sigma v.</math>

Такие векторы <math>u</math> и <math>v</math> называются, соответственно, левым сингулярным вектором и правым сингулярным вектором, соответствующим сингулярному числу <math>\sigma</math>.

Разложение матрицы

Сингулярным разложением матрицы <math>M</math> порядка <math>m \times n</math> является разложение следующего вида

<math>M = U\Sigma V^{*},</math>

где <math>\Sigma</math> — матрица размера <math>m \times n</math> с неотрицательными элементами, у которой элементы, лежащие на главной диагонали — это сингулярные числа (а все элементы, не лежащие на главной диагонали, являются нулевыми), а матрицы <math>U</math> (порядка <math>m</math>) и <math>V</math> (порядка <math>n</math>) — это две унитарные матрицы, состоящие из левых и правых сингулярных векторов соответственно (а <math>V^*</math> — это сопряжённо-транспонированная матрица к <math>V</math>).

Пример

Пусть дана матрица:

<math>M =

\begin{bmatrix} 1 & 0 & 0 & 0 & 2\\ 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0\end{bmatrix} </math>

Одним из сингулярных разложений этой матрицы является разложение <math>M = U \Sigma V^*</math>, где матрицы <math>U</math>, <math>\Sigma</math> и <math>V^*</math> следующие:

<math>

U = \begin{bmatrix} 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & -1\\ 1 & 0 & 0 & 0\end{bmatrix}, \quad

\Sigma = \begin{bmatrix} 4 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0\\ 0 & 0 & \sqrt{5} & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{bmatrix}, \quad

V^* = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8}\\ 0 & 0 & 0 & 1 & 0\\ -\sqrt{0.8} & 0 & 0 & 0 & \sqrt{0.2}\end{bmatrix}, </math> так как матрицы <math>U</math> и <math>V</math> унитарны (<math>UU^* = I</math> и <math>VV^* = I</math>, где <math>I</math> — единичная матрица), а <math>\Sigma</math> — прямоугольная диагональная матрица, то есть <math>\Sigma_{ij} = 0</math>, если <math>i \neq j</math>.

Геометрический смысл

Пусть матрице <math>A</math> поставлен в соответствие линейный оператор. Сингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства <math>\R^n</math> в себя, представим в виде последовательно выполняемых линейных операторов вращения и растяжения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором <math>A</math> множества векторов из векторного пространства в себя или в векторное пространство другой размерности[1].

Для более визуального представления рассмотрим сферу <math>S</math> единичного радиуса в пространстве <math>\R^n</math>. Линейное отображение <math>T</math> отображает эту сферу в эллипсоид пространства <math>\R^m</math>. Тогда ненулевые сингулярные значения диагонали матрицы <math>\Sigma</math> являются длинами полуосей этого эллипсоида. В случае когда <math>n = m</math> и все сингулярные величины различны и отличны от нуля, сингулярное разложение линейного отображения <math>T</math> может быть легко проанализировано как последствие трех действий: рассмотрим эллипсоид <math>T(S)</math> и его оси; затем рассмотрим направления в <math>\R^n</math>, которые отображение <math>T</math> переводит в эти оси. Эти направления ортогональны. Вначале применим изометрию <math>\mathbf{v}^*</math>, отобразив эти направления на координатные оси <math>\R^n</math>. Вторым шагом применим эндоморфизм <math>\mathbf{d}</math>, диагонализированный вдоль координатных осей и расширяющий/сжимающий эти направления, используя длины полуосей <math>T(S)</math> как коэффициенты растяжения. Тогда произведение <math>\mathbf{d} \otimes \mathbf{v}^*</math> отображает единичную сферу на изометричный эллипсоид <math>T(S)</math>. Для определения последнего шага <math>u</math> просто применим изометрию к этому эллипсоиду так, чтобы перевести его в <math>T(S)</math>. Как можно легко проверить, произведение <math>\mathbf{u} \otimes \mathbf{d} \otimes \mathbf{v}^*</math> совпадает с <math>T</math>.

Приложения

Псевдообратная матрица

Сингулярное разложение может быть использовано для нахождения псевдообратных матриц, которые применяются, в частности, в методе наименьших квадратов.

Если <math>M = U\Sigma V^*</math>, то псевдообратная к ней матрица находится по формуле:

<math> M^+ = V \Sigma^{-1} U^*,</math>

где <math>\Sigma^{-1}</math> — псевдообратная к матрице <math>\Sigma</math>, получающаяся из неё заменой каждого диагонального элемента <math>\sigma</math> на обратный к нему: <math>{\sigma}^{-1}</math> и транспонированием.

Приближение матрицей меньшего ранга

В некоторых практических задачах требуется приближать заданную матрицу <math>M</math> некоторой другой матрицей <math>M_k</math> с заранее заданным рангом <math>k</math>. Известна следующая теорема, которую иногда называют теоремой Эккарта — Янга.[2]

Если потребовать, чтобы такое приближение было наилучшим в том смысле, что евклидова норма разности матриц <math>M</math> и <math>M_k</math> минимальна, при ограничении <math>\mbox{rank}(M_k) = k</math>, то оказывается, что наилучшая такая матрица <math>M_k</math> получается из сингулярного разложения матрицы <math>M</math> по формуле:

<math>M_k = U \Sigma_k V^*,</math>

где <math>\Sigma_k</math> — матрица <math>\Sigma</math>, в которой заменили нулями все диагональные элементы, кроме <math>k</math> наибольших элементов.

Если элементы матрицы <math>\Sigma</math> упорядочены по невозрастанию, то выражение для матрицы <math>M_k</math> можно переписать в такой форме:

<math>M_k = U_k \Sigma_k V_k^*,</math>

где матрицы <math>U_k</math>, <math>\Sigma_k</math> и <math>V_k</math> получаются из соответствующих матриц в сингулярном разложении матрицы <math>M</math> обрезанием до ровно <math>k</math> первых столбцов.

Таким образом видно, что приближая матрицу <math>M</math> матрицей меньшего ранга, мы выполняем своего рода сжатие информации, содержащейся в <math>M</math>: матрица <math>M</math> размера <math>m \times n</math> заменяется меньшими матрицами размеров <math>m \times k</math> и <math>k \times n</math> и диагональной матрицей с <math>k</math> элементами. При этом сжатие происходит с потерями — в приближении сохраняется лишь наиболее существенная часть матрицы <math>M</math>.

Во многом благодаря этому свойству сингулярное разложение и находит широкое практическое применение: в сжатии данных, обработке сигналов, численных итерационных методах для работы с матрицами, методе главных компонент, латентно-семантическом анализе и прочих областях.

Сокращенное представление

Для матрицы <math>M</math> порядка <math>m \times n</math> при необходимости приближения матрицей ранга <math>r</math> меньшего чем <math>n</math> часто используют компактное представление разложения[3]:

<math>M = U_r \Sigma_r V_r^*.</math>

Вычисляются только <math>r</math> столбцов <math>U</math> и <math>r</math> строк <math>V^*</math>. Остальные столбцы <math>U</math> и строки <math>V^*</math> не вычисляются. Это экономит большое количество памяти при <math>r \ll n</math>.

Приведем пример, допустим <math>m</math> это количество пользователей, каждый из которых проставил часть оценок фильмам, общее количество которых будем обозначать <math>n</math>, тогда матрица (сильно разреженная, т. к. каждый пользователь оценил лишь малую часть фильмов) будет обозначаться <math>M</math> и иметь достаточно большую размерность <math>[m\times n]</math>.

При желании работать с матрицей меньшей размерности мы должны вычислить сингулярное разложение:

<math>M = U\Sigma V^{*}</math> при этом матрица <math>\Sigma</math> как было сказано ранее является диагональной. После чего, если мы хотим сохранить только <math>90\% </math> информации, то мы должны взять <math>r</math>, таким образом, чтобы сумма квадратов первых элементов <math>\Sigma</math> была <math>90\% </math> от общей суммы всех квадратов диагональных элементов <math>\Sigma</math>.

Таким образом мы получим <math>U</math> размерностью <math>[m\times r]</math> (взяв <math>r</math> столбцов), <math>\Sigma</math> с размерностью <math>[r\times r]</math> и <math>V^*</math> с <math>[r\times n]</math>. После, вместо матрицы <math>M</math> мы можем манипулировать матрицей <math>M' = U\Sigma</math> с меньшей размерностью <math>[m\times r]</math>, которую часто интерпретируют, как матрицу оценок пользователей по категориям фильмов.

Программные реализации

Численные алгоритмы нахождения сингулярного разложения встроены во многие математические пакеты. Например, в системах MATLAB и GNU Octave его можно найти командой 

[U, S, V] = svd(M);

SVD входит в список основных методов многих математических библиотек, в том числе свободно распространяемых.
Так, например, существуют реализации

  • В GNU Scientific library (GSL):

https://www.gnu.org/software/gsl/manual/html_node/Singular-Value-Decomposition.html

  • Во framework'е ROOT, разрабатываемом в CERN и широко используемом в научной среде:

https://root.cern.ch/root/htmldoc/guides/users-guide/LinearAlgebra.html#svd

  • В библиотеке Intel® Math Kernel Library (Intel® MKL).

https://software.intel.com/en-us/intel-mkl

  • В библиотеке numpy для линейной алгебры в Python:

https://numpy.org/doc/stable/reference/generated/numpy.linalg.svd.html

  • В библиотеке для машинного обучения tensorflow:

https://www.tensorflow.org/api_docs/python/tf/linalg/svd

  • И некоторые другие

https://tedlab.mit.edu/~dr/SVDLIBC/
http://www.alglib.net/matrixops/general/svd.php

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Статьи

Лекции on-line

Шаблон:Векторы и матрицы

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.
  3. ↑ Шаблон:Книга
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Сингулярное_разложение&oldid=10798377