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

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

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

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

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

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

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

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

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

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

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

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

Mv = \sigma u, \! и M^{*} u = \sigma v. \,\!

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

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

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

M = U\Sigma V^{*}, \,\!

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

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

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

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}

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


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},

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

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

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

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

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

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

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

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

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

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

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

 M^+ = V \Sigma^+ U^*, \,

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

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

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

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

\! M_k = U \Sigma_k V^*,

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

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

\! M_k = U_k \Sigma_k V_k^*,

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

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

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

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

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

\! M = U_r \Sigma_r V_r^*.

Вычисляются только r столбцов U и r строк V^*. Остальные столбцы U и строки V^* не вычисляются. Это экономит большое количество памяти при r<<n.

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

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

  1. Сингулярное разложение на вики Распознавание
  2. Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.

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

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

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

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