Iterativer "Löser" für

Ich kann mir nicht vorstellen, dass ich der Erste bin, der über das folgende Problem nachdenkt, daher bin ich mit einer Referenz zufrieden (aber eine vollständige, detaillierte Antwort wird immer geschätzt):

Sagen Sie bitte eine symmetrische , positiv definite haben . n wird als sehr groß angesehen, so dass es unmöglich ist , Σ im Speicher zu halten. Sie können jedoch Σ x für jedes x ∈ R n auswerten . Bei einigen x ∈ R n möchten Sie x t Σ - 1 x finden .$\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$

Die erste Lösung, die mir in den Sinn kommt, besteht darin, Verwendung von (sagen wir) konjugierten Gradienten zu finden. Dies scheint jedoch etwas verschwenderisch zu sein - Sie suchen einen Skalar und finden dabei einen gigantischen Vektor in R n . Es erscheint sinnvoller, eine Methode zur direkten Berechnung des Skalars zu entwickeln (dh ohne Σ - 1 x zu durchlaufen ). Ich suche nach dieser Art von Methode.$\Sigma^{-1}x$$\mathbb{R}^{n}$$\Sigma^{-1}x$

Ich glaube nicht, dass ich von einer Methode gehört habe, die das tut, was Sie wollen, ohne es tatsächlich zu lösen .$y=\Sigma^{-1}x$

Die einzige Alternative, die ich anbieten kann, ist, wenn Sie etwas über die Eigenvektoren und -werte von wissen . Angenommen, Sie wussten, dass sie λ i , v i sind , dann können Sie Σ = V T L V darstellen, wobei die Spalten von V die v i sind und L eine Diagonalmatrix mit den Eigenwerten auf der Diagonale ist. Folglich haben Sie Σ - 1 = V T L - 1 V und Sie erhalten x T Σ - 1 x $\Sigma$$\lambda_i,v_i$$\Sigma=V^T L V$$V$$v_i$$L$$\Sigma^{-1}=V^T L^{-1} V$ Dies würde natürlich erfordern speichernalleEigenwerte, dh eine vollständige Matrix V . Wenn Sie jedoch zufällig wissen, dass nur einige der Eigenwerte von Σ klein sind, sagen Sie das erste m , und der Rest ist so groß, dass Sie alle Terme mit λ - 1vernachlässigen können

$$x^T \Sigma^{-1} x = x^T V^T L^{-1} V x = \sum_i \lambda_i^{-1} (v_i^T x)^2.$$ $V$$\Sigma$$m$ füri>m, können Sie sich annähern $\lambda^{-1}_i$$i>m$ Dies erfordert dann nur, dass Sie m Vektoren anstelle aller n Eigenvektorenspeichern. $$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$$n$

In der Praxis ist es natürlich oft gleich oder schwieriger, die Eigenwerte und Eigenvektoren zu berechnen, als einfach zu lösen$y=\Sigma^{-1}x$