Berurusan dengan kebalikan dari matriks (kovarians) simetris positif yang pasti?

27

Dalam statistik dan berbagai aplikasinya, kita sering menghitung matriks kovarians , yang pasti positif (dalam kasus yang dipertimbangkan) dan simetris, untuk berbagai kegunaan. Terkadang, kita membutuhkan invers dari matriks ini untuk berbagai perhitungan (bentuk kuadratik dengan invers ini sebagai matriks pusat (saja), misalnya). Mengingat kualitas dari matriks ini, dan kegunaan yang dimaksudkan, saya bertanya-tanya:

Apa yang terbaik, dalam hal stabilitas numerik, cara untuk menghitung atau menggunakan (misalkan untuk bentuk kuadrat atau perkalian matriks-vektor secara umum) terbalik ini? Beberapa faktorisasi yang bisa berguna?

Benjamin Allévius
sumber

Jawaban:

14

Faktorisasi Cholesky C=RTR mengarah ke faktorisasi mirip Cholesky dari invers C1=SST dengan matriks segitiga atas S=R1 .

Dalam praktiknya, yang terbaik adalah menjaga faktor pembalikannya. Jika R jarang, maka biasanya lebih baik untuk menjaga S implisit, karena produk vektor-matriks y=C1x dapat dihitung dengan menyelesaikan dua sistem segitiga RTz=x dan Ry=z .

Arnold Neumaier
sumber
25

Faktorisasi Cholesky paling masuk akal untuk stabilitas dan kecepatan terbaik ketika Anda bekerja dengan matriks kovarians, karena matriks kovarians akan menjadi matriks simetris semi-pasti positif. Cholesky alami di sini. TAPI...

JIKA Anda bermaksud menghitung faktorisasi Cholesky, sebelum Anda menghitung matriks kovarians, bantulah diri Anda. Buat masalah stabil secara maksimal dengan menghitung faktorisasi QR matriks Anda. (A QR juga cepat.) Yaitu, jika Anda akan menghitung matriks kovarians sebagai

C=ATA

di mana memiliki kolom yang berarti dihilangkan, lalu perhatikan bahwa ketika Anda membentuk C , itu kuadrat nomor kondisi. Jadi yang lebih baik adalah membentuk faktor-faktor QR dari A daripada secara eksplisit menghitung faktorisasi Cholesky dari A TACA .ATA

A=QR

Karena Q adalah orthogonal,

C=(QR)TQR=RTQTQR=RTIR=RTR

Dengan demikian kita mendapatkan faktor Cholesky langsung dari faktorisasi QR, dalam bentuk . Jika Q -kurang QR faktorisasi tersedia, ini bahkan lebih baik karena Anda tidak perlu Q . Sebuah Q -kurang QR adalah hal yang cepat untuk menghitung, karena Q tidak pernah dihasilkan. Itu hanya menjadi urutan transformasi Householder. (Kolom diputar, Q- tanpa QR secara logis akan menjadi lebih stabil, dengan biaya beberapa pekerjaan tambahan untuk memilih pivot.)RTQQQQQ

Keutamaan besar menggunakan QR di sini adalah sangat stabil secara numerik pada masalah yang tidak menyenangkan. Sekali lagi, ini karena kita tidak pernah harus membentuk matriks kovarians secara langsung untuk menghitung faktor Cholesky. Segera setelah Anda membentuk produk , Anda kuadratkan nomor kondisi matriks. Secara efektif, Anda kehilangan informasi di bagian-bagian dari matriks di mana Anda awalnya memiliki sedikit informasi untuk memulai.ATA

Akhirnya, seperti yang ditunjukkan oleh respons lain, Anda bahkan tidak perlu menghitung dan menyimpan invers sama sekali, tetapi menggunakannya secara implisit dalam bentuk backsolves pada sistem segitiga.

pentavalentcarbon
sumber
5
Dan jika Anda perlu mengevaluasi bentuk kuadrat berdasarkan , maka Anda dapat melakukan ini secara stabil dengan menghitung x , C - 1 x = x , ( R T R ) - 1 x = R - T x 2 , yaitu, melakukan satu penggantian maju dan mengambil norma. C1x,C1x=x,(RTR)1x=RTx2
Christian Clason
3

Saya melakukan ini untuk pertama kalinya baru-baru ini, menggunakan saran dari mathSE.

SVD direkomendasikan oleh sebagian besar saya, tetapi saya memilih untuk kesederhanaan Cholesky:

Jika matriks , maka saya menguraikan M ke matriks segitiga L menggunakan Cholesky, sehingga M = L L . Saya kemudian menggunakan substitusi balik atau substitusi ke depan (tergantung pada apakah saya memilih L menjadi segitiga atas atau bawah), untuk membalikkan L , sehingga saya memiliki L - 1 . Dari sini, saya dapat dengan cepat menghitung M - 1 = ( L L ) - 1 = L - L - 1 .M=AAMLM=LLLL1M1=(LL)1=LL1


Dimulai dari:

, di mana M diketahui dan secara implisit simetris dan juga positif-pasti.M=AAM

Factorisation Cholesky:

, di mana L adalah persegi dan non-tunggalMLLL

Substitusi kembali:

, mungkin cara tercepat untuk membalikkan L (jangan mengutip saya tentang itu)LL1L

Perkalian:

M1=(LL)1=LL1

Notasi yang digunakan: Indeks yang lebih rendah adalah baris, indeks atas adalah kolom dan adalah transposes dari L - 1LL1


Algoritma Cholesky saya (mungkin dari Numerical Recipes atau Wikipedia)

Lij=MijMiMjMiiMiMi

Ini hampir dapat dilakukan di tempat (Anda hanya perlu penyimpanan sementara untuk elemen diagonal, akumulator dan beberapa iterator integer).


Algoritma back-substitusi saya (dari Numerical Recipes, periksa versinya karena saya mungkin telah membuat kesalahan dengan markup LaTeX)

(L1)ij={1/Liiif i=j(Li(LT)j)/Liiotherwise

LT

Mark K Cowan
sumber
2

Jika Anda tahu bahwa matriks memiliki kebalikan (yaitu, jika memang pasti positif) dan jika tidak terlalu besar, maka dekomposisi Cholesky memberikan cara yang tepat untuk menandai kebalikan dari matriks.

Wolfgang Bangerth
sumber