WikiSort.ru - Не сортированное

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

Сингулярное разложение матрицы ${\displaystyle M}$ позволяет вычислять сингулярные числа данной матрицы, а также левые и правые сингулярные векторы матрицы ${\displaystyle M}$ :

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

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

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

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

Определение

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

Пример

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

${\displaystyle 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}}}$

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

${\displaystyle 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}},}$

так как матрицы ${\displaystyle U}$ и ${\displaystyle V}$ унитарны (${\displaystyle UU^{*}=I}$ и ${\displaystyle VV^{*}=I}$ , где ${\displaystyle I}$  — единичная матрица), а ${\displaystyle \Sigma }$  — прямоугольная диагональная матрица, то есть ${\displaystyle \Sigma _{ij}=0}$ , если ${\displaystyle i\neq j}$ .

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

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

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

Приложения

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

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

${\displaystyle M=U_{r}\Sigma _{r}V_{r}^{*}.}$

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

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

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

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

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

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

Численные алгоритмы нахождения сингулярного разложения встроены во многие математические пакеты. Например, в системах 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://docs.scipy.org/doc/numpy-1.12.0/reference/generated/numpy.linalg.svd.html

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

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

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

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

См. также

• Разложение матрицы
• Метод главных компонент
• Латентно-семантический анализ

Примечания

Литература

• William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Singular Value Decomposition // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5.

Ссылки