Разложение Холецкого

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

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

Текущая версия

Статья написана с использованием LLM DeepSeek-V3-0324 и проверена участником Nikita Elкhin 20:44, 18 июля 2026 (MSD)

Разложение Холецкого — представление симметричной положительно определённой матрицы $A$ в виде произведения нижней треугольной матрицы $L$ с вещественными положительными диагональными элементами на её транспонированную: $A = L L^{\top}.$ Метод назван в честь французского геодезиста и математика Андре-Луи Холецкого, предложившего его для решения систем нормальных уравнений. В машинном обучении разложение Холецкого является стандартным инструментом для работы с ковариационными матрицами, матрицами Грама и гессианами.

Определение и существование

Пусть $A \in \mathbb{R}^{n \times n}$ — симметричная положительно определённая матрица ( $A = A^{\top}$ и $x^{\top} A x > 0$ для любого ненулевого вектора $x \in \mathbb{R}^n$ ). Тогда существует единственная нижняя треугольная матрица $L \in \mathbb{R}^{n \times n}$ с положительными диагональными элементами $L_{ii} > 0$ , такая что $A = L L^{\top}.$ Это утверждение можно доказать по индукции, рассматривая блочное представление матрицы $A$ . Существование гарантировано положительной определённостью всех главных миноров, а единственность — фиксацией знака диагональных элементов^[1]^[1]. Для положительно полуопределённых матриц разложение Холецкого в вещественных числах может не существовать; на практике применяют регуляризацию, добавляя малое возмущение диагонали.

Алгоритм вычисления

Наиболее распространённый способ — построчная или столбцовая схема. Приведём столбцовый вариант (outer product formulation). Для $j = 1,\dots,n$ последовательно вычисляют диагональный элемент и элементы под ним: $L_{jj} = \sqrt{ A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 },$ $L_{ij} = \frac{1}{L_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} \right),\ i = j+1,\dots,n.$ Алгоритм требует около $\frac{1}{3}n^3$ операций умножения и столько же сложений, что вдвое экономнее LU-разложения симметричной матрицы^[1]. Память используется для хранения примерно $\frac{1}{2}n^2$ элементов нижнего треугольника, причём разложение может быть выполнено «на месте», замещая исходную матрицу.

Существует вариант $LDL^{\top}$ -разложения: $A = L D L^{\top}$ , где $L$ — нижняя треугольная с единичной диагональю, $D$ — диагональная матрица с положительными элементами. Он избегает извлечения квадратных корней и удобен для обновлений после изменения ранга. Холецкий получается как $L_{\text{chol}} = L D^{1/2}$ .

Свойства

Вычислительная сложность: $O(n^3/3)$ арифметических операций для плотной матрицы; для разреженных матриц с хорошей структурой может быть существенно меньше.

Устойчивость: для положительно определённых матриц разложение Холецкого обратно устойчиво без выбора главного элемента^[1]. Однако при плохой обусловленности ( $\kappa(A) \gg 1$ ) возможно появление численно отрицательных подкоренных выражений из-за ошибок округления. В таких случаях применяют диагональную регуляризацию или $LDL^{\top}$ .

Связь с другими разложениями: Холецкий можно рассматривать как частный случай LU-разложения для симметричной положительно определённой матрицы, где $U = L^{\top}$ .

Определитель: $\det A = (\det L)^2 = \prod_{i=1}^n L_{ii}^2$ . Логарифм определителя, часто используемый в функциях правдоподобия, вычисляется как $\log \det A = 2\sum_{i=1}^n \log L_{ii}$ .

Приложения в машинном обучении

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

Для решения $A x = b$ с уже вычисленным разложением $A = L L^{\top}$ выполняют прямую и обратную подстановки: $L y = b$ прямой ход, $L^{\top} x = y$ обратный ход. Каждый этап требует $O(n^2)$ операций. Это основной способ получения точного решения в задачах с SPD-матрицами, например, в ридж-регрессии.

Генерация многомерных нормальных векторов

Если $\Sigma = L L^{\top}$ — ковариационная матрица, то случайный вектор $z \sim \mathcal{N}(\mu, \Sigma)$ можно построить по формуле $z = \mu + L \varepsilon, \quad \varepsilon \sim \mathcal{N}(0, I).$ Такой подход повсеместно применяется при реализации гауссовских процессов, в байесовских нейронных сетях и методах Монте-Карло.

Вычисление определителя и логарифма определителя

Как указано выше, $\log \det A$ вычисляется через диагональ $L$ без построения самого определителя, что критично для оптимизации гиперпараметров в гауссовских процессах и байесовской линейной регрессии.

Гауссовские процессы

В гауссовских процессах (GP) ключевым объектом является ковариационная матрица $K + \sigma^2 I$ размера $N \times N$ , построенная по обучающей выборке. Она симметрична и положительно определена. Разложение Холецкого $K + \sigma^2 I = L L^{\top}$ позволяет:

эффективно вычислить логарифмическую маргинальную правдоподобность: $\log p(y|X) = -\frac{1}{2} y^{\top} \alpha - \sum_i \log L_{ii} - \frac{N}{2} \log 2\pi,$ где $\alpha = (K + \sigma^2 I)^{-1} y$ находится через две подстановки;

делать предсказания: среднее и дисперсию в новой точке получают, решая системы с тем же треугольным фактором^[1]. Для $N$ порядка нескольких тысяч разложение Холецкого остаётся стандартным инструментом (время $O(N^3)$ ). При больших $N$ переходят к разреженным или аппроксимирующим методам, но Холецкий часто используется на индуцирующих точках.

Ридж-регрессия и байесовская линейная регрессия

В ридж-регрессии оценка параметров сводится к решению системы $(X^{\top}X + \lambda I) w = X^{\top} y.$ Матрица системы является SPD для любого $\lambda > 0$ . Разложение Холецкого позволяет устойчиво находить $w$ даже при почти линейно зависимых признаках^[1]. В байесовской линейной регрессии с нормальным априорным распределением апостериорная ковариация $\Sigma_w$ также SPD, и её фактор Холецкого используется для генерации сэмплов и построения доверительных интервалов.

Метод Ньютона и оптимизация второго порядка

При обучении моделей (логистическая регрессия, SVM) часто используют метод Ньютона или его квазиньютоновские варианты. Шаг метода Ньютона требует решения системы $H p = -g,$ где $H$ — гессиан функции потерь. Если функция выпуклая, гессиан положительно полуопределён. На практике к нему добавляют регуляризацию $H + \mu I$ , делая его положительно определённым, и применяют разложение Холецкого^[1]. Это даёт быстрое и численно устойчивое направление спуска.

Метод опорных векторов и квадратичное программирование

В задаче обучения SVM с ядром решается двойственная задача квадратичного программирования: $\min_{\alpha} \frac{1}{2} \alpha^{\top} Q \alpha - e^{\top} \alpha,$ где $Q_{ij} = y_i y_j K(x_i, x_j)$ . Матрица $Q$ симметрична и положительно полуопределена; с добавлением регуляризации $Q + \lambda I$ становится SPD. Во многих решателях (например, в методах активного набора) для обновления рабочего множества используется разложение Холецкого.

Фильтр Калмана

В фильтре Калмана ковариационная матрица состояния $P$ должна оставаться симметричной и положительно определённой. Из-за ошибок округления стандартные уравнения могут нарушать это свойство. Квадратно-корневой фильтр Калмана использует разложение Холецкого $P = S S^{\top}$ и обновляет только треугольный фактор $S$ , что гарантирует положительную определённость и удвоенную точность.

Предобусловливание итерационных методов

В методах сопряжённых градиентов для ускорения сходимости часто применяют неполное разложение Холецкого (incomplete Cholesky) в качестве предобуславливателя. Оно сохраняет разреженную структуру, формируя матрицу $M = \tilde{L} \tilde{L}^{\top} \approx A$ , которая эффективно используется на каждом шаге.

Генерация выборок и вариационные методы

В вариационных автоэнкодерах и байесовских нейронных сетях иногда необходимо моделировать полную ковариационную структуру латентных переменных. Разложение Холецкого параметризует матрицу $\Sigma = L L^{\top}$ и позволяет легко вычислять плотность и градиенты по $L$ . Аналогично, в нормализующих потоках (normalizing flows) преобразования с нижнетреугольными матрицами дают удобные якобианы.

Ограничения и альтернативы

Разложение Холецкого требует, чтобы матрица была строго положительно определённой. При нарушении этого свойства (например, из-за коллинеарности признаков) стандартные алгоритмы завершаются ошибкой. В таких случаях применяют:

$LDL^{\top}$ -разложение с выбором главного элемента (pivoting) — работает для положительно полуопределённых матриц.

Сингулярное разложение (SVD) или QR-разложение — универсальны, но медленнее.

Итерационные методы (CG) с диагональным предобуславливателем, если требуется лишь приближённое решение.

Для очень больших $n$ (миллионы) кубическая сложность неприемлема. В таких ситуациях используют блочные, разреженные или свободные от матриц методы. Однако для задач с числом признаков до нескольких тысяч разложение Холецкого остаётся непревзойдённым по сочетанию простоты, устойчивости и скорости. При работе с плохо обусловленными или почти вырожденными матрицами в машинном обучении принято добавлять к диагонали небольшую константу, что одновременно стабилизирует разложение и соответствует небольшой регуляризации.

Литература

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A5%D0%BE%D0%BB%D0%B5%D1%86%D0%BA%D0%BE%D0%B3%D0%BE»

@@ Строка 1: / Строка 1: @@
-== Разложение Холецкого ==
+{{well|Статья написана с использованием LLM '''DeepSeek-V3-0324''' и проверена участником [[Участник:Nikita Elкhin|Nikita Elкhin]] 20:44, 18 июля 2026 (MSD)}}
 '''Разложение Холецкого''' — представление симметричной положительно определённой матрицы <tex>A</tex> в виде произведения нижней треугольной матрицы <tex>L</tex> с вещественными положительными диагональными элементами на её транспонированную:
@@ Строка 24: / Строка 24: @@
 === Свойства ===
-'''Вычислительная сложность''': <tex>O(n^3/3)</tex> флопов для плотной матрицы; для разреженных матриц с хорошей структурой может быть существенно меньше.
+'''Вычислительная сложность''': <tex>O(n^3/3)</tex> арифметических операций для плотной матрицы; для разреженных матриц с хорошей структурой может быть существенно меньше.
 '''Устойчивость''': для положительно определённых матриц разложение Холецкого обратно устойчиво без выбора главного элемента<ref>Trefethen L. N., Bau III D. Numerical Linear Algebra. — SIAM, 1997.</ref>. Однако при плохой обусловленности (<tex>\kappa(A) \gg 1</tex>) возможно появление численно отрицательных подкоренных выражений из-за ошибок округления. В таких случаях применяют диагональную регуляризацию или <tex>LDL^{\top}</tex>.
@@ Строка 32: / Строка 32: @@
 '''Определитель''': <tex>\det A = (\det L)^2 = \prod_{i=1}^n L_{ii}^2</tex>. Логарифм определителя, часто используемый в функциях правдоподобия, вычисляется как <tex>\log \det A = 2\sum_{i=1}^n \log L_{ii}</tex>.
-=== Базовые вычислительные применения ===
+=== Приложения в машинном обучении ===
 ==== Решение систем линейных уравнений ====
 Для решения <tex>A x = b</tex> с уже вычисленным разложением <tex>A = L L^{\top}</tex> выполняют прямую и обратную подстановки:
@@ Строка 46: / Строка 46: @@
 Как указано выше, <tex>\log \det A</tex> вычисляется через диагональ <tex>L</tex> без построения самого определителя, что критично для оптимизации гиперпараметров в гауссовских процессах и байесовской линейной регрессии.
-=== Приложения в машинном обучении ===
 ==== Гауссовские процессы ====
 В [[Гауссовский процесс|гауссовских процессах]] (GP) ключевым объектом является ковариационная матрица <tex>K + \sigma^2 I</tex> размера <tex>N \times N</tex>, построенная по обучающей выборке. Она симметрична и положительно определена. Разложение Холецкого <tex>K + \sigma^2 I = L L^{\top}</tex> позволяет:
@@ Строка 92: / Строка 91: @@
 Для очень больших <tex>n</tex> (миллионы) кубическая сложность неприемлема. В таких ситуациях используют блочные, разреженные или свободные от матриц методы. Однако для задач с числом признаков до нескольких тысяч разложение Холецкого остаётся непревзойдённым по сочетанию простоты, устойчивости и скорости. При работе с плохо обусловленными или почти вырожденными матрицами в машинном обучении принято добавлять к диагонали небольшую константу, что одновременно стабилизирует разложение и соответствует небольшой регуляризации.
-== Примечания ==
+== Литература ==
 <references />
-== Литература ==
-Golub G. H., Van Loan C. F. ''Matrix Computations''. — 4th ed. — Baltimore: Johns Hopkins University Press, 2013.
-Trefethen L. N., Bau III D. ''Numerical Linear Algebra''. — Philadelphia: SIAM, 1997.
-Rasmussen C. E., Williams C. K. I. ''Gaussian Processes for Machine Learning''. — Cambridge: MIT Press, 2006.
-Nocedal J., Wright S. J. ''Numerical Optimization''. — 2nd ed. — New York: Springer, 2006.
-Bishop C. M. ''Pattern Recognition and Machine Learning''. — New York: Springer, 2006