"Solver" iterativo para

9

Não consigo imaginar que sou o primeiro a pensar no seguinte problema, por isso ficarei satisfeito com uma referência (mas sempre é apreciada uma resposta completa e detalhada):

Digamos que você tenha um simétrica definida positiva . n é pensado como muito grande, então segurando Σ na memória é impossível. Você pode, no entanto, avaliar Σ x , para qualquer x R n . Dado algum x R n , você gostaria de encontrar x t Σ - 1 x .ΣRn×nnΣΣxxRnxRnxtΣ1x

A primeira solução que vem à mente é encontrar usando (digamos) gradientes conjugados. No entanto, isso parece um pouco inútil - você procura um escalar e, no processo, encontra um vetor gigantesco em R n . Parece fazer mais sentido criar um método para calcular diretamente o escalar (ou seja, sem passar por Σ - 1 x ). Eu estou procurando por esse tipo de método.Σ1xRnΣ1x

Yair Daon
fonte
2
A sua matriz surgir a partir de para alguns "curta e ampla" rectangular A ? Σ=ATAUMA
GeoMatt22
@ GeoMatt22 infelizmente não. Mas digamos que sim - o que você sugeriria nesse caso?
Yair Daon
11
Yair, eu estava pensando se existe alguma matriz menor com a qual trabalhar ... não tenho certeza se isso ajudaria. Você já tentou pesquisar no Google "distância dos mahalanobis sem matriz" ou semelhante? Desculpe por não ser de mais ajuda!
GeoMatt22
Obrigado @ GeoMatt22, não consegui encontrar nada online.
Yair Daon

Respostas:

2

Acho que nunca ouvi falar de nenhum método que faça o que você deseja, sem resolver .y=Σ-1 1x

A única alternativa que posso oferecer é se você soubesse algo sobre os autovetores e valores de . Diga que sabia que eles são λ i , v i , pode representar Σ = V T L V em que as colunas de V são o v i , e L é uma matriz diagonal com os valores próprios na diagonal. Conseqüentemente, você tem que Σ - 1 = V T L - 1 V e obtém que x T Σ - 1 x =ΣλEu,vEuΣ=VTeuVVvEueuΣ-1 1=VTeu-1 1V Este seria, evidentemente exigem que você para armazenartodos osvalores próprios, ou seja, uma matriz completa V . Mas, se você soube que apenas alguns dos autovalores de Σ são pequenos, digamos o primeiro m , e o restante é tão grande que você pode negligenciar todos os termos com λ - 1 i para i > m , então você pode aproximar

xTΣ-1 1x=xTVTeu-1 1Vx=EuλEu-1 1(vEuTx)2.
VΣmλEu-1 1Eu>m Isso exige apenas que você armazenemvetores, em vez de todos osnvetores próprios.
xTΣ-1 1x=Eu=1 1nλEu-1 1(vEuTx)2Eu=1 1mλEu-1 1(vEuTx)2.
mn

Obviamente, na prática, muitas vezes é igualmente ou mais difícil calcular os valores próprios e os vetores próprios, em comparação com a solução simples de várias vezes.y=Σ-1 1x

Wolfgang Bangerth
fonte
m
xTΣ1x
Você pode sugerir um método então?
Yair Daon
Existem muitos solucionadores de autovalores em abundância ou esparsos. ARPACK e SLEPc baseado em PETSc são provavelmente os mais amplamente utilizados.
Wolfgang Bangerth
mn×n