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

Сингулярное разложение (англ. Singular Value Decomposition, SVD) — это факторизация вещественной или комплексной матрицы, которая представляет её в виде произведения трёх матриц: левой унитарной (ортогональной для вещественных матриц) матрицы, диагональной матрицы сингулярных чисел и правой унитарной (ортогональной) матрицы. Является одним из фундаментальных понятий линейной алгебры и численного анализа, обобщающим понятие спектрального разложения на произвольные прямоугольные матрицы. Сингулярное разложение существует для любой матрицы, что делает его универсальным инструментом для анализа данных, сжатия информации, решения систем линейных уравнений и машинного обучения.

История

Первые работы, связанные с разложением матриц на произведение ортогональных и диагональных компонентов, появились в конце XIX века. В 1873 году итальянский математик Эудженио Бельтрами независимо друг от друга и от французского математика Камиля Жордана (1874) опубликовали работы о сингулярном разложении билинейных форм. Однако современная формулировка SVD была предложена немецким математиком Германом Вейлем в 1912 году в контексте теории интегральных уравнений. В 1965 году американский математик Джин Голуб впервые предложил устойчивый вычислительный алгоритм для нахождения SVD, что положило начало его широкому применению в численных методах. В 1970-х годах SVD стало ключевым инструментом в обработке сигналов и статистике, а с развитием вычислительной техники в конце XX века — в машинном обучении и анализе больших данных.

Математическое определение

Пусть \( A \) — вещественная матрица размера \( m \times n \). Сингулярное разложение матрицы \( A \) имеет вид:

\[ A = U \Sigma V^T \]

где:

\( U \) — ортогональная матрица размера \( m \times m \) (столбцы — левые сингулярные векторы);
\( \Sigma \) — диагональная матрица размера \( m \times n \), на диагонали которой стоят неотрицательные числа \( \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0 \), называемые сингулярными числами;
\( V \) — ортогональная матрица размера \( n \times n \) (столбцы — правые сингулярные векторы);
\( r = \text{rank}(A) \) — ранг матрицы.

Для комплексных матриц ортогональные матрицы заменяются на унитарные, а транспонирование — на эрмитово сопряжение.

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

Сингулярные числа \( \sigma_i \) — это квадратные корни из собственных значений матрицы \( A^T A \) (или \( AA^T \)).
Количество ненулевых сингулярных чисел равно рангу матрицы.
Наибольшее сингулярное число \( \sigma_1 \) равно спектральной норме матрицы \( \|A\|_2 \).
Сингулярные числа инвариантны относительно ортогональных преобразований строк и столбцов.

Геометрическая интерпретация

Сингулярное разложение можно рассматривать как разложение линейного преобразования, задаваемого матрицей \( A \), на три последовательных действия:

Поворот (или отражение) — преобразование \( V^T \), которое переводит ортонормированный базис в пространстве \( \mathbb{R}^n \) в другой ортонормированный базис.
Масштабирование — диагональная матрица \( \Sigma \), которая растягивает или сжимает векторы вдоль осей с коэффициентами \( \sigma_i \).
Поворот (или отражение) — преобразование \( U \), которое переводит результат обратно в исходное пространство \( \mathbb{R}^m \).

Таким образом, любое линейное отображение между евклидовыми пространствами сводится к двум поворотам и одному масштабированию.

Вычислительные алгоритмы

Прямые методы

Для небольших матриц (до нескольких тысяч элементов) используется алгоритм на основе QR-разложения с использованием преобразований Хаусхолдера или Гивенса. Этот метод находит все сингулярные числа и векторы за \( O(mn^2) \) операций для матрицы \( m \times n \) (при \( m \ge n \)).

Итерационные методы

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

Стохастические методы

В задачах машинного обучения с очень большими матрицами (например, в рекомендательных системах) используются рандомизированные алгоритмы, которые с высокой вероятностью аппроксимируют SVD за \( O(mn \log k) \) операций, где \( k \) — количество искомых сингулярных чисел.

Применение

Сжатие данных

SVD позволяет представить матрицу в виде суммы \( r \) матриц ранга 1:

\[ A = \sum_{i=1}^{r} \sigma_i u_i v_i^T \]

Если оставить только \( k \) наибольших сингулярных чисел (\( k < r \)), получается наилучшее приближение исходной матрицы матрицей ранга \( k \) в смысле нормы Фробениуса (теорема Эккарта — Янга). Это используется для сжатия изображений, аудио и видео: вместо хранения полной матрицы хранятся только \( k \) сингулярных чисел и соответствующие векторы.

Обработка естественного языка

В латентно-семантическом анализе (LSA) SVD используется для снижения размерности матрицы «термин — документ». Это позволяет выявить скрытые семантические связи между словами и документами, улучшая качество информационного поиска и классификации текстов.

Решение систем линейных уравнений

Для плохо обусловленных систем \( Ax = b \) SVD позволяет найти псевдообратную матрицу Мура — Пенроуза \( A^+ = V \Sigma^+ U^T \), где \( \Sigma^+ \) — диагональная матрица с обратными ненулевыми сингулярными числами. Это даёт решение с минимальной нормой и наименьшей среднеквадратичной ошибкой.

Обработка сигналов и изображений

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

Анализ данных и машинное обучение

Метод главных компонент (PCA) эквивалентен SVD центрированной матрицы данных.
Кластеризация — SVD используется в спектральной кластеризации для снижения размерности графа.
Сжатие нейронных сетей — веса полносвязных слоёв аппроксимируются матрицами малого ранга через SVD, что ускоряет вычисления и уменьшает объём модели.

Ограничения и недостатки

Вычислительная сложность — полное SVD для больших матриц требует значительных ресурсов, особенно при \( m \) и \( n \) порядка миллионов.
Чувствительность к выбросам — SVD минимизирует среднеквадратичную ошибку, поэтому выбросы в данных могут сильно искажать результат.
Неотрицательность — стандартное SVD не гарантирует неотрицательности компонент, что может быть неудобно для интерпретации в некоторых приложениях (например, в анализе текстов).
Неединственность — сингулярные числа единственны, но сингулярные векторы определены с точностью до знака (или фазы для комплексных матриц).

Вариации и обобщения

Усечённое SVD — нахождение только \( k \) наибольших сингулярных чисел и векторов.
Взвешенное SVD — учёт весов строк или столбцов.
SVD с разреженными ограничениями — наложение условий разреженности на сингулярные векторы.
Тензорное SVD — обобщение на многомерные массивы (тензоры), используется в анализе многомерных данных.
Квантовое SVD — алгоритмы для квантовых компьютеров, позволяющие экспоненциально ускорить разложение.

Интересные факты

SVD является основой для алгоритма PageRank в ранних версиях поисковой системы Google (через анализ ссылочной структуры).
В 2009 году Netflix присудил премию в 1 миллион долларов команде, разработавшей алгоритм на основе SVD для улучшения рекомендательной системы.
SVD используется в криптографии для анализа стойкости шифров и в биоинформатике для анализа экспрессии генов.
В России метод SVD активно применяется в задачах обработки сигналов в системах связи и радиолокации, а также в геофизике для интерпретации сейсмических данных.

Источники

Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
Хорн Р., Джонсон Ч. Матричный анализ. — М.: Мир, 1989.
Strang G. Introduction to Linear Algebra. — 5th ed. — Wellesley-Cambridge Press, 2016.
Kalman D. A Singularly Valuable Decomposition: The SVD of a Matrix // The College Mathematics Journal. — 1996. — Vol. 27, No. 1. — P. 2–23.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →