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

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

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

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

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

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

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

Разложение матрицы Сингулярным разложением матрицы размера является разложение следующего вида

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

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

Одним из сингулярных разложений этой матрицы является разложение , где матрицы , и следующие:

так как матрицы и унитарны ( и , где  — единичная матрица), а  — прямоугольная диагональная матрица, то есть , если .

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

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

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

Приложения

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

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

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

Приближение матрицей меньшего ранга В некоторых практических задачах требуется приближать заданную матрицу некоторой другой матрицей с заранее заданным рангом . Известна следующая теорема, которую иногда называют теоремой Эккарта — Янга.Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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