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

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

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

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

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

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

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

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

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

Определение

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

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

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

[math]\displaystyle{ Mv = \sigma u, }[/math] и [math]\displaystyle{ M^{*} u = \sigma v. }[/math]

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

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

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

[math]\displaystyle{ M = U\Sigma V^{*}, }[/math]

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

Пример

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

[math]\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} }[/math]

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

[math]\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}, }[/math]

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

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

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

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

Приложения

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

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

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

[math]\displaystyle{ M^+ = V \Sigma^{-1} U^*, }[/math]

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

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

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

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

[math]\displaystyle{ M_k = U \Sigma_k V^*, }[/math]

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

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

[math]\displaystyle{ M_k = U_k \Sigma_k V_k^*, }[/math]

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

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

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

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

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

[math]\displaystyle{ M = U_r \Sigma_r V_r^*. }[/math]

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

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

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

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

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

См. также

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

Литература

• 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 (англ.)