Perhitungan invers matriks yang efisien dalam R

21

Saya perlu menghitung invers matriks dan telah menggunakan solvefungsi. Meskipun bekerja dengan baik pada matriks kecil, solvecenderung sangat lambat pada matriks besar. Saya bertanya-tanya apakah ada fungsi lain atau kombinasi fungsi (melalui SVD, QR, LU, atau fungsi dekomposisi lainnya) yang dapat memberi saya hasil lebih cepat.

jitendra
sumber
2
Bisakah Anda memberikan informasi lebih lanjut? Berapa perkiraan dimensi? Apakah matriks memiliki struktur khusus (simetri, sparsity, dll.)? Apa definisi kuantitatif Anda tentang "lambat"? Dan cepat"?
kardinal
Dimensi perkiraan seperti 2000x2000. Matriks tidak memiliki struktur khusus. Yah, solvemetode pasti berhasil, tetapi saya ingin algoritme lebih cepat. Jadi, saya hanya ingin tahu apakah ada fungsi (dalam konteks waktu) yang lebih efisien untuk menghitung invers untuk matriks ukuran besar.
jitendra
1
Sudahkah Anda mencoba saran lain di halaman bantuan solve? Tentu saja, tanpa struktur khusus, Anda tidak dapat melarikan diri dari batas kompleksitas teoretis pada inversi matriks umum.
kardinal
3
@ Cardinal Triknya adalah untuk menyelidiki lebih lanjut mengenai aplikasi yang sebenarnya, karena seperti yang Anda tahu, dalam banyak kasus pembalikan matriks tidak perlu (dan memakan waktu dan rawan kesalahan).
whuber
@whuber: Ini poin yang sangat bagus. Saya kira kadang-kadang saya mendekati pertanyaan-pertanyaan ini sedikit terlalu langsung.
kardinal

Jawaban:

23

Sudahkah Anda mencoba apa yang disarankan kardinal dan menjelajahi beberapa metode alternatif untuk menghitung invers? Mari kita perhatikan contoh spesifik:

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)

Jadi, ini adalah contoh dari matriks korelasi yang kami inginkan kebalikannya. Di laptop saya (Core-i5 2.50Ghz), membutuhkan waktu 8-9 detik, membutuhkan waktu lebih dari 4 detik, dan2000×2000solvechol2inv(chol())qr.solve() membutuhkan waktu 17-18 detik (beberapa kali menjalankan kode disarankan untuk mendapatkan hasil yang stabil).

Jadi kebalikannya melalui dekomposisi Choleski sekitar dua kali lebih cepat solve. Tentu saja mungkin ada cara yang lebih cepat untuk melakukan itu. Saya baru saja menjelajahi beberapa yang paling jelas di sini. Dan seperti yang telah disebutkan dalam komentar, jika matriks memiliki struktur khusus, maka ini mungkin dapat dimanfaatkan untuk kecepatan lebih.

Wolfgang
sumber
Terima kasih banyak atas solusi ini. Saya, setidaknya, tahu satu metode yang dapat menyelesaikannya separuh waktu dibandingkan dengan solve:-)
jitendra
8
Dekomposisi Cholesky adalah pilihan yang baik untuk matriks kovarians / korelasi tetapi perlu diingat bahwa secara umum matriks tersebut harus Hermitian (dalam kasus matriks nyata yang berarti simetris), matriks pasti positif. Itu menggunakan setengah dari memori yang diperlukan untuk dekomposisi LU.
Raxel