Espectro aproximado de uma matriz grande

14

Quero calcular o espectro ( todos os autovalores) de uma grande matriz esparsa (centenas de milhares de linhas). Isto é difícil.

Estou disposto a aceitar uma aproximação. Existem métodos de aproximação para fazer isso?

Enquanto espero uma resposta geral para essa pergunta, também ficaria satisfeito com uma resposta no caso específico a seguir. Minha matriz é um Laplaciano Normalizado de um gráfico grande. Os autovalores estarão entre 0 e 2, com um grande número deles agrupados em torno de 1.

MRocklin
fonte
A matriz é esparsa ou densa?
Aron Ahmadia
A matriz é escassa. Eu editei a pergunta para refletir isso.
MRocklin
Por que você deseja todos os autovalores? Isso é quase universalmente uma coisa ruim a ser feita quando você tem uma matriz esparsa ou estruturada; portanto, é importante saber como planeja usá-la.
Jed Brown
O espectro de um gráfico laplaciano contém algumas informações importantes que eu gostaria de examinar. Eu não preciso de todos eles, só preciso saber aproximadamente onde eles estão.
22912 MRocklin

Respostas:

15

Se o seu gráfico não for direcionado (como suspeito), a matriz será simétrica e você não poderá fazer nada melhor que o algoritmo de Lanczsos (com re-regionalização seletiva, se necessário, para estabilidade). Como o espectro completo consiste em 100000 números, acho que você está interessado principalmente na densidade espectral.

Para obter uma densidade espectral aproximada, pegue o espectro do subespaço Krylov principal da dimensão 100 mais ou menos e substitua sua densidade discreta por uma versão suavizada.

O espectro líder de Krylov terá quase resolvido autovalores bem isolados (caso existam), aproxima-se dos autovalores no final do espectro não-isolado e é um tanto aleatório no meio, com uma distribuição cuja função de distribuição cumulativa se assemelha à do espectro verdadeiro . Ele convergiria para ele na aritmética exata se a dimensão aumentar. (Se o seu operador fosse de dimensão infinita, esse ainda seria o caso e você obteria a integral da verdadeira função de densidade espectral no espectro contínuo.)

Arnold Neumaier
fonte
O espectro do principal subespaço de Krylov não será apenas os 100 maiores valores próprios? Também estou interessado na distribuição dos autovalores moderados e menores.
MRocklin
1
@Rocklin: Não. Aumentei minha resposta para dar mais detalhes.
Arnold Neumaier
4

Se você pensa bem em coisas que não são autovalores, mas funções que, em certo sentido, ainda lhe dizem algo sobre o espectro, acho que você deveria conferir alguns dos trabalhos de Mark Embree na Rice University.

Wolfgang Bangerth
fonte
2

Aqui está mais uma maneira de caracterizar o espectro.

Dado um problema de autovalor (suponha A simétrico real e autovalores separados; embora o último provavelmente não seja necessário), vamos tentar estimar a densidade espectral manchada S ( ω ) = k π - 1 σUMAvk=λkvkUMA Depois declicaremhttp://dx.doi.org/10.1016/0377-0427(96)00018-0em uma pesquisa bibliográfica, sabemos que um O estimador de Monte Carlo para o traço é S(ω)=σ

S(ω)=kπ-1σσ2+(λk-ω)2=σπTr[σ2+(ω-UMA)2]-1
onde cada entrada do vector aleatórioZcontém tanto+1ou-1com uma probabilidade de 0,5 para cada. Para dadosσeω, o produto inverso [σ2+(ω-A)2]-1
S(ω)=σπzT[σ2+(ω-UMA)2]-1z
z+1-1σω[σ2+(ω-UMA)2]-1zpode ser calculado, por exemplo, com o método de gradiente conjugado ou LU esparsa em também para matrizes grandes. Na prática, parece que a solução de CG não precisa ser muito precisa, e nem muitos vetores são necessários para calcular a média. Isso pode depender do problema. para minimizar o preenchimento. Isso permite estimar S ( ω )[ω+Euσ-UMA]-1[ω-Euσ-UMA]-1S(ω)

O acima exposto parece pesar partes do espectro de maneira mais uniforme do que uma densidade espectral de Krylov manchada da mesma forma --- experimente diag (espaço interno (0, 1, 150000)) --- embora talvez haja uma maneira de corrigir isso. Isso é um pouco semelhante à abordagem pseudoespectral, mas o resultado indica o número (manchado) de autovalores na vizinhança até o ponto ω , em vez da distância inversa ao valor próprio mais próximo.

ω

pv.
fonte
0

Veja o artigo "Sobre Decomposição Espectral Aproximada com Base em Amostragem", de Sanjiv Kumar, Mehryar Mohri e Ameet Talwalkar (ICML 2009.). Ele usa amostragem de colunas da sua matriz.

Como sua matriz é simétrica, faça o seguinte:

Seja A sua matriz n * n. Você deseja reduzir o cálculo dos valores próprios de uma matriz n * n para o cálculo dos valores próprios de uma matriz k * k. Primeiro, escolha seu valor de k. Digamos que você escolha k = 500, pois é possível calcular facilmente os autovalores de uma matriz 500 * 500. Em seguida, escolha aleatoriamente k colunas da matriz A. Contrate a matriz B que mantém apenas essas colunas e as linhas correspondentes.

B = A (x, x) para um conjunto aleatório de índices k x

B é agora matriz ak * k. Calcule os autovalores de B e multiplique-os por (n / k). Agora você tem k valores que são aproximadamente distribuídos como os n autovalores de A. Observe que você obtém apenas valores de k, não n, mas a distribuição deles estará correta (até o fato de serem uma aproximação).

Jérôme Kunegis
fonte
-1

Você sempre pode usar os limites do teorema do círculo de Gershgorin para aproximar os valores próprios.

Se os termos fora da diagonal forem pequenos, a própria diagonal é uma boa aproximação do espectro. Caso contrário, se você terminar com uma aproximação do espaço próprio (por outros métodos), poderá tentar expressar as entradas diagonais neste sistema. Isso levará a uma matriz com termos fora da diagonal menores e a nova diagonal será uma melhor aproximação do espectro.

FKaria
fonte
Gerschgoring não dá proximaximações, mas limites de erro, então é irrelevante aqui. Além disso, usar seu método em uma matriz esparsa exigiria uma matriz densa de vetor próprio, que é impossível de armazenar para o problema dos OPs.
Arnold Neumaier
Como eu disse, a diagonal é ela mesma uma aproximação do espectro com os limites de erro dados pelo teorema do círculo de Gershgorin, é claro que os limites de erro de Gershgorin não são aproximações. A diagonal será uma boa aproximação se os termos fora da diagonal forem pequenos, o que acredito ser o caso, já que o OP disse que a matriz é esparsa.
FKaria
5
A maioria das matrizes esparsas que surgem na prática possui alguns elementos fora da diagonal significativos em cada linha e coluna, o que torna as aproximações muito pobres na diagonal (por exemplo, para um laplaciano de um gráfico regular, a diagonal é constante) e o erro é inútil.
Arnold Neumaier