«Solveur» itératif pour

9

Je ne peux pas imaginer que je suis le premier à penser au problème suivant, donc je serai satisfait d'une référence (mais une réponse complète et détaillée est toujours appréciée):

Disons que vous avez une symétrique définie positive . n est considéré comme très grand, donc garder Σ en mémoire est impossible. Vous pouvez cependant évaluer Σ x , pour tout x R n . Étant donné un certain x R n , vous aimeriez trouver x t Σ - 1 x .ΣRn×nnΣΣxxRnxRnxtΣ1x

La première solution qui vient à l'esprit est de trouver utilisant (disons) des gradients conjugués. Cependant, cela semble quelque peu inutile - vous cherchez un scalaire et dans le processus, vous trouvez un vecteur gigantesque dans R n . Il semble plus logique de trouver une méthode pour calculer directement le scalaire (c'est-à-dire sans passer par Σ - 1 x ). Je recherche ce genre de méthode.Σ1xRnΣ1x

Yair Daon
la source
2
Votre matrice provient-elle de pour un A rectangulaire "court et large" ? Σ=ATAA
GeoMatt22
@ GeoMatt22 malheureusement pas. Mais disons que c'est le cas - que suggéreriez-vous dans ce cas?
Yair Daon
1
Yair, je pensais juste s'il y avait une matrice plus petite avec laquelle travailler ... pas sûr que ça aiderait de toute façon. Avez-vous essayé de googler "distance de mahalanobis sans matrice" ou similaire? Désolé de ne pas vous être plus utile!
GeoMatt22
Merci @ GeoMatt22, je n'ai rien trouvé en ligne.
Yair Daon

Réponses:

2

Je ne pense pas avoir entendu parler d'une méthode qui fasse ce que vous voulez sans réellement résoudre .y=Σ1x

La seule alternative que je peux offrir est si vous saviez quelque chose sur les vecteurs propres et les valeurs de . Supposons que vous saviez qu'ils sont λ i , v i , alors vous pouvez représenter Σ = V T L V où les colonnes de V sont les v i , et L est une matrice diagonale avec les valeurs propres sur la diagonale. Par conséquent, vous avez que Σ - 1 = V T L - 1 V et vous obtenez que x T Σ - 1 x =Σλi,viΣ=VTLVVviLΣ1=VTL1V Cela nécessiterait bien sûr que vous stockieztoutes lesvaleurs propres, c'est-à-dire une matrice V complète. Mais, s'il vous arrivait de savoir que seules quelques-unes des valeurs propres de Σ sont petites, disons le premier m , et le reste est si grand que vous pouvez négliger tous les termes avec λ - 1 i pour i > m , alors vous pouvez approximer

xTΣ1x=xTVTL1Vx=iλi1(viTx)2.
VΣmλi1i>m Cela ne vous oblige alors qu'à stocker m vecteurs, au lieu de tous les n vecteurs propres.
xTΣ1x=i=1nλi1(viTx)2i=1mλi1(viTx)2.
mn

y=Σ1x

Wolfgang Bangerth
la source
m
xTΣ1x
Pouvez-vous suggérer une méthode alors?
Yair Daon
Il existe de nombreux solveurs de valeurs propres clairsemés. ARPACK et le SLEPc basé sur PETSc sont probablement les plus largement utilisés.
Wolfgang Bangerth
mn×n