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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • И некоторые другие

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.

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

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

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

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