Собственное разложение

Материал из MachineLearning.

(Различия между версиями)

Версия 19:57, 19 июля 2026

Содержание

1 Собственное разложение матрицы

Собственное разложение матрицы

Собственное разложение (Eigenvalue Decomposition, EVD) матрицы $A \in \mathbb{R}^{n \times n}$ (или $\mathbb{C}^{n \times n}$ ) — представление матрицы в виде произведения $A = V \Lambda V^{-1},$ где $\Lambda = \operatorname{diag}(\lambda_1,\dots,\lambda_n)$ — диагональная матрица собственных значений, а столбцы матрицы $V$ — собственные векторы матрицы $A$ . Это разложение является центральным инструментом линейной алгебры, вычислительной математики и анализа данных. Оно раскрывает геометрическую суть линейного преобразования, определяет важнейшие свойства матрицы и лежит в основе многих алгоритмов машинного обучения.

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

Квадратная матрица $A$ задаёт линейное преобразование векторов пространства $\mathbb{R}^n$ . Собственные векторы — это такие ненулевые векторы $x$ , направление которых не изменяется под действием $A$ : $A x = \lambda x,$ где $\lambda$ — соответствующее собственное значение. Геометрически это означает, что преобразование лишь растягивает или сжимает вектор вдоль его прямой (и, возможно, меняет направление на противоположное при $\lambda < 0$ ). Если $A$ обладает полным набором линейно независимых собственных векторов, любое преобразование можно представить как масштабирование вдоль этих инвариантных направлений.

Если представить произвольный вектор $y$ в базисе из собственных векторов, $y = V c$ , то действие матрицы сводится к покомпонентному умножению на собственные значения: $A y = V \Lambda c.$ Именно в этом заключается сила диагонализации — сложная связанная система распадается на одномерные независимые задачи.

Определения и свойства

Пусть $A$ — квадратная матрица порядка $n$ . Число $\lambda \in \mathbb{C}$ и ненулевой вектор $x \in \mathbb{C}^n$ называются собственной парой, если $A x = \lambda x.$

Из этого уравнения следует, что $(A - \lambda I)x = 0$ , а для существования ненулевого решения необходимо, чтобы матрица $A - \lambda I$ была вырожденной. Поэтому собственные значения являются корнями характеристического многочлена: $p(\lambda) = \det(A - \lambda I) = 0.$

Множество всех собственных значений называется спектром матрицы. Вещественные матрицы могут иметь комплексно-сопряжённые пары собственных значений; симметричные вещественные матрицы обладают только вещественным спектром.

Важнейшими инвариантами, сохраняющимися при подобии, являются след и определитель:

$\operatorname{tr}(A) = \sum_{i=1}^n \lambda_i,$
$\det(A) = \prod_{i=1}^n \lambda_i.$

Диагонализируемость

Матрица $A$ называется диагонализируемой (или приводимой к диагональному виду подобием), если существует невырожденная матрица $V$ такая, что $V^{-1} A V = \Lambda,$ где $\Lambda$ диагональна. Эквивалентно, $A$ обладает $n$ линейно независимыми собственными векторами.

Необходимое и достаточное условие диагонализируемости: алгебраическая кратность каждого собственного значения (кратность корня характеристического многочлена) равна его геометрической кратности (размерности собственного подпространства $\ker(A - \lambda I)$ ). Если это условие нарушено, матрица называется дефектной; для неё собственное разложение не существует, и максимально упрощённой формой становится жорданова нормальная форма [1, гл. 3].

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

Спектральная теорема для симметричных матриц

Вещественная симметричная матрица $A = A^T$ имеет только вещественные собственные значения и обладает ортонормированным базисом из собственных векторов. Следовательно, её собственное разложение принимает вид $A = Q \Lambda Q^T,$ где $Q$ — ортогональная матрица ( $Q^{-1} = Q^T$ ), а столбцы $Q$ — ортонормированные собственные векторы. Это утверждение известно как спектральная теорема [2, гл. 7], [3, гл. 6].

Для комплексных эрмитовых матриц ( $A = A^*$ ) аналогом служит разложение с унитарной матрицей $U$ : $A = U \Lambda U^*$ .

Из ортогональности $Q$ вытекают два полезных представления:

спектральное разложение: $A = \sum_{i=1}^n \lambda_i q_i q_i^T,$
квадратичная форма: $x^T A x = \sum_{i=1}^n \lambda_i (q_i^T x)^2.$

Симметричное собственное разложение численно устойчивее общего случая и составляет фундамент многих методов анализа данных.

Вычислительные методы

Прямое вычисление собственных значений через характеристический полином практически не используется из-за плохой обусловленности задачи для матриц порядка больше нескольких десятков. Современные надёжные алгоритмы основаны на итерационных ортогональных преобразованиях. Основным рабочим инструментом для плотных несимметричных матриц служит QR-алгоритм [4, гл. 7–8], [5, лек. 28].

QR-алгоритм (со сдвигами): матрица приводится к верхней хессенберговой форме, после чего итерационно выполняется $A_k = Q_k R_k$ , $A_{k+1} = R_k Q_k$ . Последовательность сходится к форме Шура — квазитреугольной матрице, на диагонали которой (или в блоках 2×2) находятся собственные значения. Для симметричных матриц метод сводится к трёхдиагональной форме и сходится к диагональной матрице собственных значений с накоплением ортогональных преобразований, дающих собственные векторы. Вычислительная сложность — $O(n^3)$ (примерно $25 n^3$ для собственных значений и ещё $10 n^3$ для собственных векторов в несимметричном случае).

Степенной метод и обратный степенной метод: находят наибольшее по модулю собственное значение и соответствующий вектор. Обратный метод с фиксированным сдвигом $\mu$ ищет собственное значение, ближайшее к $\mu$ ; он лежит в основе итераций Рэлея, где сдвиг динамически обновляется как отношение Рэлея $\rho(x) = \frac{x^T A x}{x^T x}$ . Последний обладает кубической сходимостью для симметричных матриц.

Для больших разреженных матриц вычисление полного спектра нецелесообразно. Вместо этого применяют методы подпространства Крылова: алгоритм Арнольди (несимметричный случай) и метод Ланцоша (симметричный) с рестартами и ортогонализацией. Они эффективно аппроксимируют крайние собственные значения и реализованы в библиотеках типа ARPACK.

Для сверхбольших задач (например, графовые матрицы) используют рандомизированные алгоритмы, приближённо строящие подпространство, близкое к инвариантному [6].

Численные особенности: задача вычисления собственных значений невырожденной матрицы может быть плохо обусловленной, особенно для несимметричных матриц с почти кратными собственными значениями; чувствительность определяется числом обусловленности матрицы собственных векторов.

Сравнение с другими матричными разложениями

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

Разложение	Формула	Тип матрицы	Требования	Сложность (плотная)	Прямоугольные	Типичные приложения в ML
EVD (собственное)	$A = V \Lambda V^{-1}$	Квадратная	Диагонализируемость	$O(n^3)$	Нет	PCA, спектральная кластеризация, анализ устойчивости
SVD (сингулярное)	$A = U \Sigma V^T$	Любая $m \times n$	Нет	$O(m n \min(m,n))$	Да	PCA, сжатие изображений, рекомендательные системы, псевдообращение
QR-разложение	$A = Q R$	Любая $m \times n$	Нет	$O(m n^2)$	Да	Решение линейных систем, ортогонализация, начальный этап QR-алгоритма
Разложение Шура	$A = U T U^*$	Квадратная	Нет (всегда существует)	$O(n^3)$	Нет	Универсальная форма для недиагонализируемых матриц, функции от матриц

Важно: SVD применимо к любой прямоугольной матрице и всегда даёт ортогональные/унитарные множители, тогда как EVD требует квадратности и диагонализируемости. Для симметричной положительно полуопределённой матрицы $A^T A$ (или $A A^T$ ) собственное разложение и SVD связаны: левые и правые сингулярные векторы являются собственными векторами $A A^T$ и $A^T A$ , а сингулярные числа — корнями из соответствующих собственных значений. Поэтому PCA можно реализовать как через EVD ковариационной матрицы, так и через SVD центрированной матрицы данных.

Применения в машинном обучении и анализе данных

Анализ главных компонент (PCA)

PCA — ключевой метод снижения размерности. Для центрированной матрицы данных $X \in \mathbb{R}^{m \times n}$ строится выборочная ковариационная матрица $C = \frac{1}{m-1} X^T X$ . Собственные векторы $C$ , соответствующие наибольшим собственным значениям, задают направления максимальной дисперсии данных. Проекция данных на первые $k$ главных компонент выполняется как $Z = X V_k$ , где $V_k$ — матрица из $k$ ведущих собственных векторов. Собственные значения показывают долю объяснённой дисперсии [7, гл. 14.5], [8, гл. 12].

Спектральная кластеризация

В спектральной кластеризации строится граф близости объектов, его матрица Лапласа $L = D - W$ (или нормализованные варианты), где $W$ — матрица смежности, $D$ — диагональная матрица степеней вершин. Собственные векторы, отвечающие наименьшим ненулевым собственным значениям, задают вложение вершин в пространство низкой размерности, в котором кластеры становятся хорошо разделимыми. Полученное представление затем обрабатывается алгоритмом k-средних [7, гл. 14.5.3], [9, гл. 25].

Анализ графов и графовые нейронные сети

Собственное разложение лапласиана лежит в основе спектральной теории графов. Такие характеристики, как алгебраическая связность (второе наименьшее собственное значение), характеризуют разбиение графа. Собственный вектор, соответствующий наибольшему собственному значению матрицы смежности, определяет центральность вершин; PageRank также опирается на собственный вектор стохастической матрицы. В графовых нейронных сетях первые спектральные подходы (Spectral CNN) использовали собственные векторы лапласиана для определения свёртки, однако из-за высокой вычислительной стоимости были вытеснены пространственными методами, применяющими полиномиальные аппроксимации (Чебышёвские многочлены) и избавляющимися от явного вычисления собственных векторов.

Анализ ковариационных матриц и оптимизация

Спектр ковариационной матрицы определяет размах и ориентацию многомерного распределения. В задачах оптимизации собственные числа матрицы Гессе в точке минимума характеризуют локальную кривизну поверхности функции потерь. Максимальное и минимальное собственные значения Гессиана определяют число обусловленности, влияющее на скорость сходимости градиентных методов первого порядка. Анализ собственных значений используется для диагностики седловых точек в нейронных сетях и для адаптации шага обучения в методах типа естественного градиента [9, гл. 8].

Анализ устойчивости динамических систем

Для линейной системы дифференциальных уравнений $\dot{x} = A x$ или разностного уравнения $x_{k+1} = A x_k$ асимптотическая устойчивость определяется расположением собственных значений матрицы $A$ на комплексной плоскости: для непрерывных систем все собственные значения должны иметь отрицательные вещественные части; для дискретных — лежать строго внутри единичного круга. Собственное разложение (или форма Шура) позволяет расщепить динамику на независимые моды и даёт исчерпывающее описание поведения системы [2, гл. 5].

Обработка изображений и рекомендательные системы

Собственное разложение лежит в основе метода «собственных лиц» (Eigenfaces) для распознавания и сжатия изображений: изображения из обучающего набора вытягиваются в векторы, строится ковариационная матрица и её главные компоненты служат базисом для представления. В рекомендательных системах, хотя SVD более распространён из-за универсальности, разложение симметричных матриц сходства (item-item или user-user) также выполняют через EVD.

Преимущества и ограничения

Преимущества:

Раскрывает фундаментальную структуру линейного оператора — масштабирование вдоль инвариантных направлений.
Даёт аналитические формулы для степеней матрицы ( $A^k = V \Lambda^k V^{-1}$ ), экспоненты и других функций от матриц.
Для симметричных матриц приводит к ортогональному базису, удобному в анализе данных.
Хорошо изученные, устойчивые алгоритмы вычисления (QR, Ланцош).

Ограничения:

Применимо только к квадратным диагонализируемым матрицам; дефектные матрицы не диагонализируемы.
Для несимметричных матриц собственные векторы могут быть сильно неортогональными, что ведёт к численной неустойчивости представления.
Вычисление полного спектра плотной матрицы имеет кубическую сложность, неприемлемую для задач с миллионами переменных.
В машинном обучении большинство матриц данных прямоугольны; прямое EVD накладывает избыточное требование квадратности, тогда как SVD лишено этого ограничения.

Современные тенденции

В эпоху больших данных прямое вычисление плотного собственного разложения часто заменяется приближёнными матричными разложениями, рандомизированными SVD и методами на основе Nyström. Для анализа крупнейших графов используются методы типа LOBPCG, ускоренные на GPU. Тем не менее, теоретический аппарат собственных значений остаётся незаменимым для понимания свойств операторов и построения новых алгоритмов.

Литература

Horn R.A., Johnson C.R. Matrix Analysis. 2nd ed. Cambridge University Press, 2013.
Strang G. Introduction to Linear Algebra. 5th ed. Wellesley-Cambridge Press, 2016.
Axler S. Linear Algebra Done Right. 3rd ed. Springer, 2015.
Golub G.H., Van Loan C.F. Matrix Computations. 4th ed. Johns Hopkins University Press, 2013.
Trefethen L.N., Bau D. Numerical Linear Algebra. SIAM, 1997.
Halko N., Martinsson P.G., Tropp J.A. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions // SIAM Review, 53(2), 2011.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. 2nd ed. Springer, 2009.
Murphy K.P. Probabilistic Machine Learning: An Introduction. MIT Press, 2022.
Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
Strang G. Linear Algebra and Learning from Data. Wellesley-Cambridge Press, 2019.

Источник — «http://recognition.su/wiki/index.php?title=%D0%A1%D0%BE%D0%B1%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5»