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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Визуализация сингулярного разложения в двумерном случае с вещественной матрицей сдвига M. Сначала мы видим единичный круг голубого цвета с двумя каноническими единичными векторами. Затем мы видим воздействие матрицы M, превращающей диск в эллипс. Сингулярное разложение раскладывает M на три простых преобразования: поворот V*, масштабирование Σ вдоль вращающихся координатных осей и второй поворот U. Длины σ1 и σ2 полуосей эллипса и есть сингулярные значения M.

Сингуля́рное разложе́ние (англ. singular value decomposition, SVD) — это разложение прямоугольной вещественной или комплексной матрицы, имеющее широкое применение, в силу своей наглядной геометрической интерпретации, при решении многих прикладных задач.

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

  • левые сингулярные векторы матрицы  — это собственные векторы матрицы ;
  • правые сингулярные векторы матрицы  — это собственные векторы матрицы .

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

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

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

Определение[править | править вики-текст]

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

Сингулярные числа и сингулярные векторы[править | править вики-текст]

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

и

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

Разложение матрицы[править | править вики-текст]

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

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

Пример[править | править вики-текст]

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

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

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

Реализация[править | править вики-текст]

Численные алгоритмы нахождения сингулярного разложения встроены во многие математические пакеты. Например, в системах MATLAB и GNU Octave его можно найти командой:

[U, S, V] = svd(M);

Геометрический смысл[править | править вики-текст]

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

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

Приложения[править | править вики-текст]

Псевдообратная матрица[править | править вики-текст]

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

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

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

Приближение матрицей меньшего ранга[править | править вики-текст]

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

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

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

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

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

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

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

Сокращенное представление[править | править вики-текст]

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

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

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

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

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

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

Программные реализации[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Сингулярное разложение на вики Распознавание
  2. Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.
  3. Peter Harrington. Machine Learning in Action. — Shelter Island, 2012. — С. 280. — ISBN 9781617290183.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]

Статьи[править | править вики-текст]

Лекции on-line[править | править вики-текст]