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

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

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

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

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

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

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

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

Определение

Пусть матрица $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$ множества векторов из векторного пространства в себя или в векторное пространство другой размерности^[1].

Для более визуального представления рассмотрим сферу $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 ^{+}U^{*},

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

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

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

Если потребовать, чтобы такое приближение было наилучшим в том смысле, что Фробениусова норма разности матриц $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$ часто используют компактное представление разложения^[3]:

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

Вычисляются только $r$ столбцов $U$ и $r$ строк $V^{*}$ . Остальные столбцы $U$ и строки $V^{*}$ не вычисляются. Это экономит большое количество памяти при $r<<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://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

См. также

Примечания

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

Литература

Шаблон:Книга

Ссылки

Статьи

Статья о сингулярном разложении на machinelearning.ru
Статья на MathWorld и пример использования для сжатия изображения.Шаблон:Ref-en

Лекции on-line

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

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

↑ Сингулярное разложение на вики Распознавание
↑ Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.
↑ Шаблон:Книга

[1] Сингулярное разложение на вики Распознавание

[2] Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.

[3] Шаблон:Книга

[1]

[2]

[3]

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

Содержание