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

Пусть матрица ${\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\ll 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://numpy.org/doc/stable/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.