Вычисление определителя итеративно вычисляемой матрицы

[Arastas]

Добрый день,

Есть матрица $A(k) \in \mathbb{R}^{n\times n}$, которая обновляется на каждом шаге как

$$A(k+1) = A(k) + v(k)\,v^\top(k),$$

где $v(k)\in\mathbb{R}^n$ и $A(0) = A_0$ -- положительно определенная. Очевидно, что для всех $k$ матрица $A(k)$ остается положительно определенной.

Мне нужно на каждом шаге вычислять определеитель: $d(k):=\det(A(k))$. Я ищу способ как это делать с наименьшими затратами и желательно с использованием ранее вычисленных значений. В частности, используя Matrix determinant lemma, получится

$$d(k+1) = \left(1+v^\top(k)A^{-1}(k)v(k)\right)d(k),$$

что уже гораздо лучше, чем полностью вычислять определитель на каждом шаге. Но для этого требуется хранить и обновлять значения обратной матрицы на прошлом шаге (формула Sherman–Morrison?), что тоже затратно. Может есть какие-то более эффективные способы?

И связанный вопрос - есть ли какие-то способы итеративно находить сопряженную матрицу к $A(k)$? Так кажется, что оба вопроса должны как-то увязываться в итеративном SVD разложении, если оно есть, но я пока ничего такого не нашёл.

[svv]

Arastas в сообщении #1430859 писал(а):

Но для этого требуется хранить и обновлять значения обратной матрицы на прошлом шаге (формула Sherman–Morrison?), что тоже затратно.

Думаю, тут дела обстоят чуть веселее: $v^\top A^{-1} v= v^\top x$, где вектор $x$ является решением системы уравнений $Ax=v$.
Ну, а решать систему легче, чем обращать матрицу.

[Евгений Машеров]

Разложить матрицу методом Холецкого (квадратного корня) $A=L^TL$, определитель будет равен квадрату произведения диагональных элементов матрицы L, при прибавлении $vv^T$ корректировать по формулам из https://en.wikipedia.org/wiki/Cholesky_ ... omposition

function [L] = cholupdate(L, x)
    n = length(x);
    for k = 1:n
        r = sqrt(L(k, k)^2 + x(k)^2);
        c = r / L(k, k);
        s = x(k) / L(k, k);
        L(k, k) = r;
        if k < n
            L((k+1):n, k) = (L((k+1):n, k) + s * x((k+1):n)) / c;
            x((k+1):n) = c * x((k+1):n) - s * L((k+1):n, k);
        end
    end
end

[Arastas]

Евгений Машеров в сообщении #1430873 писал(а):

Разложить матрицу методом Холецкого (квадратного корня)

Супер, спасибо! Выглядит многообщеающе, буду пробовать.

Евгений Машеров в сообщении #1430873 писал(а):

при прибавлении $vv^T$ корректировать по формулам

А не знаете, есть ли подобные корректировки для SVD?

[Евгений Машеров]

Не встречал, и подозреваю, что их и нет. Вообще я бы в Алберта заглянул бы, "Регрессия, псевдоинверсия и рекуррентное оценивание".

[Евгений Машеров]

Проявление пустого любопытства - зачем нужен определитель?

[Arastas]

Евгений Машеров в сообщении #1430984 писал(а):

Проявление пустого любопытства - зачем нужен определитель?

Там задача вида $y(k) = d(k)\theta+\nu(k)$, где $\nu(k)$ - помеха, $y(k)$ - измерение, а $d(k)$ -- тот самый определитель известной матрицы $A(k)$. Надо оценить неизвестный постоянный параметр $\theta$.

[Евгений Машеров]

Не совсем понял, что понимается под сопряжённой матрицей. Если эрмитово-сопряжённая, то расчёт несколько тривиален (особенно если вспомнить, что матрица действительная и симметричная). Если что-то другое, то что?
Что до итеративного уточнения SVD-разложения - такой красивой схемы, как для $L^TL$, боюсь, не будет. Но в силу симметричности матрицы её сингулярное разложение совпадает с собственным (вообще говоря, с точностью до знака, но у нас неотрицательно определённая).
$A=C^T\Lambda C$
и тогда $A+v^Tv=C^T\Lambda C+v^Tv=C^T(\Lambda+Cv^TvC^T)C$
Величина в круглых скобках может быть достаточно близкой к диагональной, чтобы приведение к диагональному виду вращениями (метод Якоби) потребовало не столь большого числа итераций (ну, то есть теоретически бесконечного, но достижение заданной точности наступает достаточно скоро)
$\Lambda+Cv^TvC^T=Q^T\Lambda_1 Q$
$C_1=QC$
$A+v^Tv=C^T_1\Lambda_1 C_1$
Оправдан ли такой пересчёт - не вем.

[Евгений Машеров]

И всё-таки, если не секрет, что выражает определитель? Как-то редкий зверёк в практических задачах, хотя вот в статистике иногда всплывает...