Тождество Вудбери и формула Шермана-Моррисона: алгебра обновлений

Формула Шермана-Моррисона: обновление первого ранга

Рассмотрим матрицу A, обратная матрица которой A^(-1) уже известна (мы вычислили ее ранее). Внезапно мы вносим в матрицу A микроскопическое изменение (возмущение первого ранга), прибавляя к ней матрицу, полученную внешним произведением вектора-столбца u на вектор-строку v^T. Новая матрица имеет вид (A + u*v^T). Американские статистики Джек Шерман и Уинфред Моррисон доказали, что обратную матрицу для этой новой суммы можно найти без единой операции гауссова исключения. Формула гласит: (A + u*v^T)^(-1) = A^(-1) - (A^(-1)*u * v^T*A^(-1)) / (1 + v^T*A^(-1)*u). В этой формуле выполняются только простейшие умножения векторов на уже известную матрицу A^(-1), что требует всего O(n^2) операций (квадратичное время вместо кубического). Это радикальное ускорение делает алгоритмы обработки сигналов пригодными для работы в режиме реального времени.

Тождество Вудбери: обновление старших рангов

Формула Шермана-Моррисона работает только для возмущений ранга 1 (добавление одного вектора). Макс Вудбери обобщил эту теорему на случай добавления целой матрицы возмущений (ранга k). Пусть мы изменяем матрицу A, прибавляя к ней матричное произведение U*C*V. Тождество Вудбери дает аналитическую формулу для обратной матрицы суммы: (A + UCV)^(-1) = A^(-1) - A^(-1)*U * (C^(-1) + V*A^(-1)*U)^(-1) * V*A^(-1). Главная магия этой формулы заключается в центральной части: нам все еще нужно вычислить обратную матрицу, но это матрица (C^(-1) + V*A^(-1)*U) размера k на k. Если мы корректируем огромную матрицу 10000x10000, добавляя к ней блок размером 10x10 (k=10), то тождество Вудбери заменяет неподъемную задачу обращения матрицы 10000x10000 на тривиальную задачу обращения крошечной матрицы 10x10, что выполняется мгновенно.

Применение в Рекурсивном методе наименьших квадратов (RLS)

Самое знаменитое применение формулы Шермана-Моррисона — алгоритм Рекурсивного Метода Наименьших Квадратов (Recursive Least Squares, RLS) в теории адаптивного управления и машинного обучения. Когда мы подгоняем прямую под облако точек, мы решаем нормальное уравнение с матрицей (X^T * X). Когда поступает новая экспериментальная точка (новый вектор признаков x), матрица (X^T * X) обновляется ровно на величину (x * x^T) — это и есть возмущение ранга 1. Благодаря Шерману-Моррисону, алгоритм RLS мгновенно пересчитывает обратную ковариационную матрицу и выдает новые, уточненные весовые коэффициенты регрессии. Модель самообучается на лету с каждым новым наблюдением, не храня в памяти всю историческую базу данных.

Фильтр Калмана: слияние предсказания и измерений

Тождество Вудбери является математическим сердцем Фильтра Калмана — алгоритма, управляющего автопилотами самолетов, дронов и космических ракет. На этапе коррекции (обновления) фильтр Калмана сливает воедино прогноз математической модели и зашумленные данные с GPS и гироскопов. Для вычисления оптимального коэффициента доверия (Gain Калмана) алгоритму требуется вычислить обратную матрицу ковариации невязок (S = H*P*H^T + R). Вывод канонических уравнений фильтра Калмана (и переход от информационной формы к ковариационной) осуществляется алгебраическим тождеством Вудбери. Оно обеспечивает математическое доказательство того, что добавление новой информации от датчиков строго (и вычислительно эффективно) уменьшает неопределенность (дисперсию) всей динамической системы в многомерном пространстве.