Сингулярное разложение SVD: главный фокус линейной алгебры
Геометрическая идея
Возьмём любую матрицу A размера m\times n и применим её к единичному кругу в \mathbb{R}^{n} (то есть к множеству всех векторов x с \left\lVert x \right\rVert=1, где \left\lVert \cdot \right\rVert — обычная евклидова длина). Что получится в \mathbb{R}^{m}?
Для любой вещественной матрицы A размера m\times n существует разложение
\begin{equation} \tag{0.1} \;A \;=\; U\,\Sigma\,V^{\!\top}\; \end{equation}
где
U — ортогональная матрица m\times m (поворот в \mathbb{R}^{m});
V — ортогональная матрица n\times n (поворот в \mathbb{R}^{n});
\Sigma — «диагональная» матрица m\times n с неотрицательными числами \sigma_1\geq \sigma_2\geq\ldots\geq \sigma_r > 0 на диагонали (и нулями ниже), где r=\mathrm{rank}\,A.
Числа \sigma_i называются сингулярными числами матрицы A.
Содержательно (0.1) говорит: любая линейная операция — это три простых действия подряд:
\underbrace{V^{\!\top}}_{\text{поворот в исходном пространстве}} \;\to\; \underbrace{\Sigma}_{\text{растяжение по координатным осям}} \;\to\; \underbrace{U}_{\text{поворот в новом пространстве}}.
Геометрически это значит: образ единичной сферы под действием A — это эллипсоид, у которого полуоси равны \sigma_1,\sigma_2,\ldots (см. рис. 0.1).
Рисунок fig:svd-ellipse не сгенерирован: C:\Users\712\AppData\Local\MiKTeX\miktex\log\miktex-maketfm.log
Рис. 0.1. SVD геометрически. Матрица A переводит единичный круг в эллипс, полуоси которого равны сингулярным числам \sigma_1,\sigma_2, а направления полуосей — столбцы матрицы U (левые сингулярные векторы). Векторы v_1,v_2 (столбцы V, правые сингулярные векторы) — это те направления в исходном пространстве, которые A переводит в полуоси эллипса.
Связь с собственными значениями
Сингулярные числа — это, по сути, переодетые собственные значения. А именно:
\begin{equation} \tag{0.2} A^{\!\top} A \;=\; (U\Sigma V^{\!\top})^{\!\top}(U\Sigma V^{\!\top}) \;=\; V\,\Sigma^{\!\top}\Sigma\,V^{\!\top}. \end{equation}
Матрица \Sigma^{\!\top}\Sigma — диагональная, на её диагонали стоят \sigma_1^{2},\sigma_2^{2},\ldots. Значит, \sigma_i^{2} — это собственные значения симметричной матрицы A^{\!\top}A, а столбцы V — её собственные векторы. Эта формула важна нам по двум причинам: (1) она обосновывает существование SVD (через известную спектральную теорему для симметричных матриц), (2) она будет рабочим инструментом в § 0.5, когда мы будем вычислять собственные лица.
Сингулярное разложение независимо открыли итальянский математик Эудженио Бельтрами (1873 г.) и француз Камилл Жордан (1874 г.). В современном виде, как разложение прямоугольной матрицы, его сформулировал Карл Эккарт с Гейлом Янгом в 1936 г. Численно надёжный алгоритм вычисления SVD появился лишь в 1965 г. (Голуб и Кахан) — и стал одним из ключевых алгоритмов XX века. Сегодня он реализован в любой математической библиотеке: numpy.linalg.svd, scipy.linalg.svd, torch.svd.