Berulang “solver” untuk

Saya tidak bisa membayangkan saya orang pertama yang memikirkan masalah berikut, jadi saya akan puas dengan referensi (tapi jawaban yang lengkap dan terperinci selalu dihargai):

Katakanlah Anda memiliki kepastian positif simetris . dianggap sangat besar, jadi menahan dalam memori tidak mungkin. Anda dapat, bagaimanapun, mengevaluasi , untuk setiap . Dengan beberapa , Anda ingin mencari . $\Sigma \in \mathbb{R}^{n \times n}$ $n$ $\Sigma$ $\Sigma x$ $x \in \mathbb{R}^{n}$ $x \in \mathbb{R}^{n}$ $x^t\Sigma^{-1}x$

Solusi pertama yang muncul di pikiran adalah menemukan menggunakan (katakanlah) gradien konjugat. Namun, ini tampaknya agak sia-sia - Anda mencari skalar dan dalam prosesnya Anda menemukan vektor raksasa di . Tampaknya lebih masuk akal untuk menemukan metode untuk menghitung skalar secara langsung (yaitu tanpa melewati ). Saya mencari metode semacam ini. $\Sigma^{-1}x$ $\mathbb{R}^{n}$ $\Sigma^{-1}x$

linear-algebra numerical-analysis iterative-method Yair Daon
sumber

Apakah matriks Anda timbul dari

untuk beberapa "singkat & lebar" persegi panjang

Σ = A^{T} A

$\Sigma = A^TA$

A

$A$

GeoMatt22

@ GeoMatt22 sayangnya tidak. Tetapi katakanlah itu terjadi - apa yang akan Anda sarankan dalam kasus itu?

Yair Daon

Yair, saya hanya berpikir jika ada beberapa matriks yang lebih kecil untuk bekerja dengan ... tidak yakin itu akan membantu. Sudahkah Anda mencoba googling "matrix mahalanobis distance" atau yang serupa? Maaf tidak bisa membantu lagi!

GeoMatt22

Terima kasih @ GeoMatt22, saya tidak dapat menemukan apa pun secara online.

Yair Daon

Jawaban:

Saya rasa saya belum pernah mendengar metode apa pun yang melakukan apa yang Anda inginkan tanpa benar-benar menyelesaikan . $y=\Sigma^{-1}x$

Satu-satunya alternatif yang bisa saya tawarkan adalah jika Anda tahu sesuatu tentang vektor eigen dan -nilai . Katakanlah Anda tahu bahwa mereka adalah , maka Anda dapat mewakili mana kolom adalah , dan adalah matriks diagonal dengan nilai eigen pada diagonal. Akibatnya, Anda memiliki dan Anda mendapatkan bahwa $\Sigma$ $\lambda_i,v_i$ $\Sigma=V^T L V$ $V$ $v_i$ $L$ $\Sigma^{-1}=V^T L^{-1} V$ Ini tentu saja mengharuskan Anda untuk menyimpansemuanilai eigen, yaitu, matriks penuh. Tetapi, jika Anda mengetahui bahwa hanya beberapa nilai eigen dari yang kecil, ucapkan pertama, dan sisanya sangat besar sehingga Anda dapat mengabaikan semua istilah dengan untuk , maka Anda dapat memperkirakan

x^{T} Σ^{- 1} x = x^{T} V^{T} L^{- 1} V x = \sum_{i} λ_{i}^{- 1} (v_{i}^{T} x)^{2} .

$x^T \Sigma^{-1} x = x^T V^T L^{-1} V x = \sum_i \lambda_i^{-1} (v_i^T x)^2.$

V

$V$

Σ

$\Sigma$

m

$m$

λ_{i}^{- 1}

$\lambda^{-1}_i$

i > m

$i>m$

Hal ini kemudian hanya mengharuskan Anda untuk menyimpan

vektor, bukan semua

vektor eigen.

x^{T} Σ^{- 1} x = \sum_{i = 1}^{n} λ_{i}^{- 1} (v_{i}^{T} x)^{2} \approx \sum_{i = 1}^{m} λ_{i}^{- 1} (v_{i}^{T} x)^{2} .

$x^T \Sigma^{-1} x = \sum_{i=1}^n \lambda_i^{-1} (v_i^T x)^2 \approx \sum_{i=1}^m \lambda_i^{-1} (v_i^T x)^2.$

m

$m$

n

$n$

$y=\Sigma^{-1}x$

Wolfgang Bangerth
sumber

m

$m$

x^{T} Σ^{- 1} x

$x^T\Sigma^{-1}x$

Bisakah Anda menyarankan metode itu?

Yair Daon

Ada banyak atau sedikit pemecah nilai eigen di sekitar. ARPACK dan SLEPc berbasis PETSc mungkin adalah yang paling banyak digunakan.

Wolfgang Bangerth

m

$m$

n \times n

$n \times n$