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

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

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

• • Собственное разложение матрицы** (Eigenvalue Decomposition, EVD) — фундаментальный инструмент линейной алгебры, позволяющий представить квадратную матрицу в форме, раскрывающей её действие как линейного преобразования. Оно особенно важно в машинном обучении для анализа данных, снижения размерности, спектрального анализа графов и оптимизации.

1. 1. 1. Оглавление

1. [Введение: геометрическая интуиция](#intro) 2. [Определения: собственные значения и векторы](#defs) 3. [Диагонализируемость и условия существования EVD](#diagonalizable) 4. [Спектральная теорема для симметричных матриц](#spectral) 5. [Построение и интерпретация разложения](#construction) 6. [Численные методы вычисления](#algorithms) 7. [Сравнение с другими разложениями](#comparison) 8. [Применения в машинном обучении и анализе данных](#applications) 9. [Преимущества, ограничения и численные особенности](#limits) 10. [Литература](#refs)

1. 1. 1. 1. Введение: геометрическая интуиция <a name="intro"></a>

Представьте линейное преобразование в двумерном пространстве. Большинство векторов меняют и направление, и длину. Однако существуют особые направления (**собственные векторы**), вдоль которых вектор только растягивается или сжимается (возможно, с изменением знака). Коэффициент этого изменения называется **собственным значением** \(\lambda\).

Собственное разложение выявляет эти «инвариантные направления» и коэффициенты растяжения. Геометрически: матрица \(A\) действует как поворот/растяжение в базисе собственных векторов.

1. 1. 1. 2. Определения <a name="defs"></a>

Ненулевой вектор \(\mathbf{x}\) называется **собственным вектором** матрицы \(A\) с **собственным значением** \(\lambda\), если

или эквивалентно

Собственные значения находятся из **характеристического уравнения**:

Многочлен \(\det(A - \lambda I)\) — **характеристический многочлен** степени \(n\) для матрицы \(n \times n\).

1. 1. 1. 3. Диагонализируемость <a name="diagonalizable"></a>

Матрица \(A\) **диагонализируема**, если существует обратимая матрица \(V\) (столбцы — линейно независимые собственные векторы) и диагональная матрица \(\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)\) такие, что

• • Необходимое и достаточное условие**: у матрицы существует полный набор линейно независимых собственных векторов (алгебраическая кратность каждого \(\lambda\) равна геометрической).

Не все матрицы диагонализируемы. Пример: матрица Жордана с блоком \(\begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}\).

1. 1. 1. 4. Спектральная теорема для симметричных (эрмитовых) матриц <a name="spectral"></a>

Для вещественной симметричной матрицы \(A = A^T\) (или эрмитовой \(A = A^H\)):

- Все собственные значения вещественны. - Собственные векторы можно выбрать ортонормированными. - Существует ортогональная (унитарная) матрица \(Q\) такая, что

Это — **спектральная теорема** (см. Horn & Johnson, Matrix Analysis; Strang, Linear Algebra and Learning from Data).

1. 1. 1. 5. Построение и интерпретация <a name="construction"></a>

1. Решить характеристическое уравнение → найти \(\lambda_i\). 2. Для каждого \(\lambda_i\) решить \((A - \lambda_i I)\mathbf{v}_i = 0\) → собственные векторы. 3. Сформировать \(V = [\mathbf{v}_1 | \dots | \mathbf{v}_n]\), \(\Lambda\).

Интерпретация: в базисе столбцов \(V\) матрица \(A\) становится диагональной — преобразование сводится к независимым масштабированиям по осям.

1. 1. 1. 6. Численные методы вычисления <a name="algorithms"></a>

- **QR-алгоритм** (основной для плотных матриц, Golub & Van Loan). - **Степенной метод** — для доминирующего собственного значения. - **Обратный степенной метод** + сдвиг — для ближайшего к сдвигу значения. - **Метод Релея** — итерационное уточнение. - Для больших разреженных матриц — методы Ланцоша/Арнольди, библиотеки ARPACK, SciPy.

• • Сложность**: для плотных \(n \times n\) — \(O(n^3)\); для разреженных — лучше.

1. 1. 1. 7. Сравнение разложений

| Характеристика | EVD | SVD | QR-разложение | Разложение Шура | |-------------------------|------------------------------|----------------------------------|-----------------------------|----------------------------| | Область | Квадратные | Любые (прямоугольные) | Квадратные/прямоугольные | Квадратные | | Требования | Диагонализируема | Всегда существует | — | Всегда | | Сложность | \(O(n^3)\) | \(O(\min(mn^2, m^2n))\) | \(O(n^3)\) / \(O(mn^2)\) | \(O(n^3)\) | | Устойчивость | Чувствительна к обусловленности | Высокая (всегда) | Хорошая | Хорошая | | Прямоугольные матрицы | Нет | Да | Да | Нет | | Применения в ML | PCA (симметр.), Гессиан | PCA (общий), рекомендательные системы | Решение СЛАУ | Анализ устойчивости |

SVD более общий и численно устойчивый (Trefethen & Bau, Numerical Linear Algebra).

1. 1. 1. 8. Применения в машинном обучении <a name="applications"></a>

• • Principal Component Analysis (PCA)**: собственное разложение ковариационной матрицы \(X^T X\) даёт главные компоненты (Hastie et al., Elements of Statistical Learning).

• • Спектральная кластеризация**: собственные векторы графа Лапласиана используются для embedding и кластеризации.

• • Анализ графов и GNN**: спектральные свойства графовых лапласианов, PageRank (степенной метод).

• • Ковариационные матрицы**: в Gaussian processes, Kalman filter.

• • Снижение размерности**, анализ устойчивости динамических систем (\(\dot{x} = Ax\)), анализ Гессиана в оптимизации (второй порядок, седловые точки).

• • Рекомендательные системы**, обработка изображений (Karhunen–Loève transform), задачи оптимизации (квадратичные формы).

1. 1. 1. 9. Преимущества, ограничения и численные особенности <a name="limits"></a>

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

- Интуитивная интерпретация. - Эффективное представление симметричных положительно определённых матриц. - Ключ к пониманию многих алгоритмов ML.

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

- Только для квадратных матриц. - Неустойчивость для недиагонализируемых или плохо обусловленных матриц. - Дорого для очень больших \(n\).

Современные применения: глубокое обучение (анализ Hessians), графовые нейронные сети, квантовые вычисления, анализ больших данных.

1. 1. 1. 10. Литература <a name="refs"></a>

1. Gilbert Strang. *Linear Algebra and Learning from Data*. Wellesley-Cambridge Press, 2019. 2. Gilbert Strang. *Introduction to Linear Algebra*, 5th ed. 3. Roger A. Horn, Charles R. Johnson. *Matrix Analysis*, 2nd ed. Cambridge University Press, 2013. 4. Gene H. Golub, Charles F. Van Loan. *Matrix Computations*, 4th ed. Johns Hopkins, 2013. 5. Lloyd N. Trefethen, David Bau III. *Numerical Linear Algebra*. SIAM, 1997. 6. Sheldon Axler. *Linear Algebra Done Right*, 3rd ed. 7. Christopher M. Bishop. *Pattern Recognition and Machine Learning*. Springer, 2006. 8. Trevor Hastie, Robert Tibshirani, Jerome Friedman. *The Elements of Statistical Learning*, 2nd ed. Springer, 2009. 9. Kevin P. Murphy. *Probabilistic Machine Learning*. MIT Press, 2022.

• • См. также**: Линейная алгебра, Сингулярное разложение, Метод главных компонент, Спектральная кластеризация.