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

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

Сингулярное разложение матрицы  позволяет вычислять сингулярные числа данной матрицы, а также левые и правые сингулярные векторы матрицы :
 левые сингулярные векторы матрицы  — это собственные векторы матрицы ;
 правые сингулярные векторы матрицы  — это собственные векторы матрицы .
Где — эрмитово-сопряжённая матрица к матрице , для вещественной матрицы .

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

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

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

Определение 
Пусть матрица  порядка  состоит из элементов из поля , где  — либо поле вещественных чисел, либо поле комплексных чисел.

Сингулярные числа и сингулярные векторы 
Неотрицательное вещественное число  называется сингулярным числом матрицы , когда существуют два вектора единичной длины  и  такие, что:
  и 
Такие векторы  и  называются, соответственно, левым сингулярным вектором и правым сингулярным вектором, соответствующим сингулярному числу .

Разложение матрицы 
Сингулярным разложением матрицы  порядка  является разложение следующего вида
 
где  — матрица размера  с неотрицательными элементами, у которой элементы, лежащие на главной диагонали — это сингулярные числа (а все элементы, не лежащие на главной диагонали, являются нулевыми), а матрицы  (порядка ) и  (порядка ) — это две унитарные матрицы, состоящие из левых и правых сингулярных векторов соответственно (а  — это сопряжённо-транспонированная матрица к ).

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

Одним из сингулярных разложений этой матрицы является разложение , где матрицы ,  и  следующие:
 
так как матрицы  и  унитарны ( и , где  — единичная матрица), а  — прямоугольная диагональная матрица, то есть , если .

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

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

Для более визуального представления рассмотрим сферу  единичного радиуса в пространстве . Линейное отображение  отображает эту сферу в эллипсоид пространства . Тогда ненулевые сингулярные значения диагонали матрицы  являются длинами полуосей этого эллипсоида. В случае когда  и все сингулярные величины различны и отличны от нуля, сингулярное разложение линейного отображения  может быть легко проанализировано как последствие трех действий: рассмотрим эллипсоид  и его оси; затем рассмотрим направления в , которые отображение  переводит в эти оси. Эти направления ортогональны. Вначале применим изометрию , отобразив эти направления на координатные оси . Вторым шагом применим эндоморфизм , диагонализированный вдоль координатных осей и расширяющий/сжимающий эти направления, используя длины полуосей  как коэффициенты растяжения. Тогда произведение  отображает единичную сферу на изометричный эллипсоид . Для определения последнего шага  просто применим изометрию к этому эллипсоиду так, чтобы перевести его в . Как можно легко проверить, произведение  совпадает с .

Приложения

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

Если , то псевдообратная к ней матрица находится по формуле:

где  — псевдообратная к матрице , получающаяся из неё заменой каждого диагонального элемента  на обратный к нему:  и транспонированием.

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

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

Если элементы матрицы  упорядочены по невозрастанию, то выражение для матрицы  можно переписать в такой форме:
 
где матрицы ,  и  получаются из соответствующих матриц в сингулярном разложении матрицы  обрезанием до ровно  первых столбцов.

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

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

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

 

Вычисляются только  столбцов  и  строк . Остальные столбцы  и строки  не вычисляются. Это экономит большое количество памяти при .

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

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

 при этом матрица  как было сказано ранее является диагональной. После чего, если мы хотим сохранить только  информации, то мы должны взять , таким образом, чтобы сумма квадратов первых элементов  была  от общей суммы всех квадратов диагональных элементов .

Таким образом мы получим  размерностью  (взяв  столбцов),  с размерностью  и  с  . После, вместо матрицы  мы можем манипулировать матрицей  с меньшей размерностью , которую часто интерпретируют, как матрицу оценок пользователей по категориям фильмов.

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

Численные алгоритмы нахождения сингулярного разложения встроены во многие математические пакеты. Например, в системах 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

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

Примечания

Литература

Ссылки

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

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

Разложения матриц
Численные методы линейной алгебры