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

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

Геометрический смысл сингулярного разложения в двумерном случае.

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

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

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

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

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

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

Определение

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

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

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

$Mv=\sigma u,$ и $M^{*}u=\sigma v.$

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

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

Сингулярным разложением матрицы $M$ размера $m\times n$ является разложение следующего вида

$M=U\Sigma V^{*},$

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

Пример

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

$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}}$

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

$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}},$

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

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

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

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

Приложения

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

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

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

$M^{+}=V\Sigma ^{-1}U^{*},$

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

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

В некоторых практических задачах требуется приближать заданную матрицу $M$ некоторой другой матрицей $M_{k}$ с заранее заданным рангом $k$. Известна следующая теорема, которую иногда называют теоремой Эккарта — Янга.

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

$M_{k}=U\Sigma _{k}V^{*},$

где $\Sigma _{k}$ — матрица $\Sigma$, в которой заменили нулями все диагональные элементы, кроме $k$ наибольших элементов.

Если элементы матрицы $\Sigma$ упорядочены по невозрастанию, то выражение для матрицы $M_{k}$ можно переписать в такой форме:

$M_{k}=U_{k}\Sigma _{k}V_{k}^{*},$

где матрицы $U_{k}$, $\Sigma _{k}$ и $V_{k}$ получаются из соответствующих матриц в сингулярном разложении матрицы $M$ обрезанием до ровно $k$ первых столбцов.

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

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

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

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

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

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

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

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

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

Таким образом мы получим $U$ размерностью $[m\times r]$ (взяв $r$ столбцов), $\Sigma$ с размерностью $[r\times r]$ и $V^{*}$ с $[r\times n]$. После, вместо матрицы $M$ мы можем манипулировать матрицей $M'=U\Sigma$ с меньшей размерностью $[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/linalg/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.

Ссылки

Статьи

• Статья о сингулярном разложении на machinelearning.ru
• Статья на MathWorld и пример использования для сжатия изображения. (англ.)

Лекции on-line

• Лекция о сингулярном разложении в контексте метода главных компонент, Хайдельбергский университет, проф. Fred Hamprecht (англ.)