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

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

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

Определение

Любая матрица $M$ порядка $m \times n$, элементы которой — комплексные числа, может быть представлена в следующем виде, называемом сингулярным разложением матрицы $M$:

$M = U \Sigma V^*, \!$

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

Под диагональной прямоугольной матрицей здесь понимается матрица $\Sigma$ такая, что все её недиагональные элементы равны нулю:

$\! \Sigma_{ij} = 0,$ если $i \neq j.$

В частном случае, когда $M$ состоит из вещественных чисел, существует сингулярное разложение вида $M = U \Sigma V^T$, в котором $U$ и $V$ — ортогональные матрицы.

Элементы $\Sigma_{ii}$ на диагонали матрицы $\Sigma$ называются сингулярными числами матрицы $M$ и определены с точностью до их перестановки. Обычно требуют, чтобы они располагались в матрице $\Sigma$ в невозрастающем порядке — тогда $\Sigma$ (но не $U$ и $V$) однозначно определяется по матрице $M$. Столбцы матриц $U$ и $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);

Сингулярные числа и сингулярные векторы

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

Пусть матрица $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 = U\Sigma V^{*}, \,\!$

диагональные элементы матрицы $\Sigma$ с необходимостью являются сингулярными числами матрицы $M$, а столбцы матриц $U$ и $V$ содержат левые и правые сингулярные векторы для соответствующих им сингулярных значений на диагонали матрицы $\Sigma$.

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

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

Для более визуального представления рассмотрим сферу $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$. Известна следующая теорема, которую иногда называют теоремой Эккарта — Янга.

Если потребовать, чтобы такое приближение было наилучшим в том смысле, что Фробениусова норма разности матриц $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.

См. также

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

Литература

• William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Singular Value Decomposition // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5

Ссылки

Статьи

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

Лекции on-line

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