Wydajne obliczanie macierzy odwrotnej w R

21

Muszę obliczyć macierz odwrotnie i używam solvefunkcji. Chociaż działa dobrze na małych matrycach, solvezwykle działa bardzo wolno na dużych matrycach. Zastanawiałem się, czy jest jakaś inna funkcja lub kombinacja funkcji (poprzez SVD, QR, LU lub inne funkcje dekompozycji), które mogą dać mi szybsze wyniki.

r matrix-decomposition matrix-inverse jitendra
źródło
2
Czy możesz podać więcej informacji? Jakie są przybliżone wymiary? Czy matryca ma jakąś specjalną strukturę (symetria, rzadkość itp.)? Jaka jest twoja ilościowa definicja „wolnego”? I szybko"?
kardynał
Przybliżone wymiary są jak 2000 x 2000. Matryca nie ma żadnej specjalnej struktury. Cóż, solvemetoda zdecydowanie nie moja praca, ale chcę algorytm jest szybszy. Zastanawiam się więc, czy istnieje bardziej wydajna (w kontekście czasu) funkcja do obliczania odwrotności dla macierzy o tak dużych rozmiarach.
jitendra
1
Czy wypróbowałeś już jakieś inne sugestie na stronie pomocy solve? Oczywiście, przy braku specjalnej struktury, nie można uniknąć teoretycznych granic złożoności ogólnej inwersji macierzy.
kardynał
3
@Cardinal Sztuką jest dalsze badanie rzeczywistej aplikacji, ponieważ, jak wiadomo, w wielu przypadkach odwracanie matrycy jest niepotrzebne (i czasochłonne i podatne na błędy).
whuber
@whuber: To bardzo dobra uwaga. Przypuszczam, że czasami podchodzę do tych pytań trochę zbyt bezpośrednio.
kardynał

Odpowiedzi:

23

Czy próbowałeś, co kardynał zasugerował, i zbadałeś alternatywne metody obliczania odwrotności? Rozważmy konkretny przykład:

library(MASS)

k   <- 2000
rho <- .3

S       <- matrix(rep(rho, k*k), nrow=k)
diag(S) <- 1

dat <- mvrnorm(10000, mu=rep(0,k), Sigma=S) ### be patient!

R <- cor(dat)

system.time(RI1 <- solve(R))
system.time(RI2 <- chol2inv(chol(R)))
system.time(RI3 <- qr.solve(R))

all.equal(RI1, RI2)
all.equal(RI1, RI3)

Jest to przykład macierzy korelacji , dla której chcemy mieć odwrotność. Na moim laptopie (Core-i5 2,50 Ghz) zajmuje 8–9 sekund, zajmuje nieco ponad 4 sekundy i zajmuje 17–18 sekund (sugeruje się wielokrotne uruchomienie kodu, aby uzyskać stabilne wyniki).2000×2000solvechol2inv(chol())qr.solve()

Zatem odwrotność poprzez rozkład Choleskiego jest około dwa razy szybsza niż solve. Oczywiście mogą istnieć jeszcze szybsze sposoby. Właśnie odkryłem niektóre z najbardziej oczywistych tutaj. I jak już wspomniano w komentarzach, jeśli matryca ma specjalną strukturę, to prawdopodobnie można ją wykorzystać dla większej prędkości.

Wolfgang
źródło
Wielkie dzięki za to rozwiązanie. Ja przynajmniej znam jedną metodę, która może rozwiązać ją o połowę w porównaniu do solve:-)
jitendra
8
Dekompozycja Cholesky'ego jest dobrym wyborem dla macierzy kowariancji / korelacji, ale należy pamiętać, że ogólnie macierz musi być hermitowska (w przypadku prawdziwych macierzy, co oznacza symetryczność), dodatnią określoną macierz. To zużywa połowę pamięci wymaganej do dekompozycji LU.
Raxel,