2 개의 정방 행렬 A와 B를가집니다. A는 대칭이고 B는 대칭적인 양의 definite입니다. $ trace (A.B^{- 1}) $를 계산하고 싶습니다. 지금은 B의 Cholesky 분해를 계산하고, $ A = C.B $라는 방정식에서 C를 풀고 대각선 요소를 합산합니다.A와 B가 주어진 Trace (AB^{- 1})의 효율적인 계산
보다 효율적인 방법이 있습니까?
Eigen을 사용하려고합니다. 행렬이 희소 한 경우 구현을 제공 할 수 있습니까 (A는 종종 대각선 일 수 있고 B는 대개 대각선입니다).
B가 부족한 경우가 효율적일 수있다 (즉, O B 좋은 조건 수를 가정하면 (N)는() Conjugate Gradient 코드 위키에 주어진 샘플)
B x_i = a_i
에 x_i 대한 해결하기. a_i을 A의 열 벡터로 사용하면 O (n^2) 행렬 B^{-1} A이됩니다. 그런 다음 대각선 요소를 합하여 추적을 얻을 수 있습니다. 일반적으로, 고유 값의 전체 집합을 얻는 것보다 희소 역 곱셈을하는 것이 더 쉽습니다. 비교를 위해 Cholesky decomposition은 O (n^3)입니다. () Cholesky에 대한 Darren Engwirda의 의견은입니다. 당신은 단지 추적에 대한 근사치를해야하는 경우
, 당신은 실제로 q 확률 벡터 r 이상
r^T (A B^{-1}) r
을 평균하여 O (Q n을)의 비용을 줄일 수 있습니다. 보통 q << n. 이것은 <...>가 r의 분포에 걸쳐 평균을 나타낸다 여기서 랜덤 r 벡터의 성분
< r_i r_j > = \delta_{ij}
을 만족하도록 제공 공정한 추정치이다. 예를 들어, 구성 요소 r_i은 단위 분산으로 분산 된 독립 가우스 분포 일 수 있습니다. 또는 + -1에서 균등하게 선택할 수 있습니다. 일반적으로 추적은 O (n)와 같고 추적 추정의 오차는 O (sqrt (n/q))와 같기 때문에 상대 오차는 O (sqrt (1/nq))로 비례합니다.
답변 해 주셔서 감사합니다. r로 평균을 어떻게합니까? 당신이 작성한 것으로부터 A.B^{- 1}을 계산할 필요가있는 것처럼 보입니다. 이것은 아마도 당신이 말하고자하는 것이 아닙니다. – yannick
아마도 Kipton은 먼저 B x = r을 풀고 r^T A x를 계산하여 r^T A B^{- 1} r을 계산해야 함을 의미합니다. 그러나 나는 확률 론적 접근을 위해 O (n)의 비용을 얻는 방법을 보지 못한다 : 비용 O (n)을 갖는 n 개의 시스템을 각각 해결하면 O (n^2)의 비용이 발생한다. 아마도 무작위 벡터의 수는 n = size보다 작을 수 있습니다. –
@Jitse, 네, 오타를 찾은 것에 대해 감사드립니다. –
일반화 된 고유 값을 계산하는 것이 더 효율적이면 일반화 된 고유 값 A*v = lambda* B *v을 계산 한 다음 모든 람다를 요약 할 수 있습니다.
저는 C++ 태그가 실제로 여기에 속해 있다고 생각합니다. 질문은 Eigen, C++ 행렬 조작 라이브러리를 사용하는 구현에 관한 것이기 때문에 여기에 속합니다. –
긍정적 인 semidefinite 또는 긍정적 인 definite입니까? –
@DavidZaslavsky 태그를 제거했습니다. – yannick