Autovetores de um pequeno ajuste de norma

10

Eu tenho um conjunto de dados que está mudando lentamente e preciso acompanhar os autovetores / autovalores de sua matriz de covariância.

Estou usando scipy.linalg.eigh, mas é muito caro e não usa o fato de eu já ter uma decomposição que é apenas um pouco incorreta.

Alguém pode sugerir uma abordagem melhor para lidar com esse problema?

Yaroslav Bulatov
fonte
11
Qual é o tamanho dos seus dados? Você precisa do sistema eletrônico completo ou apenas de alguns dos maiores valores próprios? Você precisa deles exatamente, ou seria uma aproximação?
CFH
Preciso de um sistema completo. Eu encontrei um algoritmo para atualizar inversa de uma matriz após pequena atualização de norma, usando a interpretação de regressão da matriz inversa de covariância, então assumi que algo semelhante deveria existir para vetores próprios.
Yaroslav Bulatov
O que você faz com essa composição completa? Pode haver um atalho melhor que não passe por ele ... E reitero a pergunta de cfh: "quão grande"?
Federico Poloni 29/04
Eu tenho recursos de 8k e milhões de pontos de dados, então a covariância é aproximada. Isso é para implementar esse algoritmo. Gradiente actualização depende de valores próprios da matriz de covariância determinado, e esta matriz de covariância muda em cada passo
laroslav Bulatov

Respostas:

5

Uma abordagem ingênua é usar a solução de autovalor de sua matriz como o palpite inicial de um resolvedor de iterativos para a matriz A ( t + δ t ) . Você pode usar o QR se precisar de todo o espectro ou o método de energia de outra forma. Entretanto, essa não é uma abordagem totalmente robusta, pois os autovalores de uma matriz não estão necessariamente próximos de uma matriz quase vizinha (1) , especialmente se estiver mal condicionada (2) .A(t)A(t+δt)

Um método de rastreamento de subespaço é aparentemente mais útil (3) . Um trecho de (4) :

O cálculo iterativo de um par de eigen extremo (máximo ou mínimo) (valor próprio e vetor próprio) pode remontar a 1966 [72]. Em 1980, Thompson propôs um algoritmo adaptativo do tipo LMS para estimar o vetor próprio, que corresponde ao menor valor próprio da matriz de covariância da amostra, e forneceu o algoritmo de rastreamento adaptativo do ângulo / frequência combinado com o estimador harmônico de Pisarenko [14]. Sarkar et al. [73] usaram o algoritmo de gradiente conjugado para rastrear a variação do vetor próprio de extremo valor que corresponde ao menor valor próprio da matriz de covariância do sinal que muda lentamente e provou sua convergência muito mais rápida que o algoritmo do tipo LMS de Thompson. Esses métodos foram usados ​​apenas para rastrear um único valor extremo e um vetor próprio com aplicação limitada, mas depois foram estendidos para os métodos de rastreamento e atualização do subespaço próprio. Em 1990, Comon e Golub [6] propuseram o método de Lanczos para rastrear o valor singular extremo e o vetor singular, que é um método comum projetado originalmente para determinar algum problema simétrico grande e esparso de eigen. [74].Ax=kx

[6]: Comon, P., & Golub, GH (1990). Rastreando alguns valores e vetores singulares extremos no processamento de sinais. In Processing of the IEEE (pp. 1327–1343).

[14]: Thompson, PA (1980). Uma técnica de análise espectral adaptativa para frequência imparcial

[72]: Bradbury, WW, & Fletcher, R. (1966). Novos métodos iterativos para soluções do problema próprio. Matemática Numérica, 9 (9), 259–266.

[73]: Sarkar, TK, Dianat, SA, Chen, H. e Brule, JD (1986). Estimação espectral adaptativa pelo método do gradiente conjugado. Transações IEEE sobre Processamento Acústico, de Fala e de Sinais, 34 (2), 272–284.

[74]: Golub, GH, e Van Load, CF (1989). Computação matricial (2ª ed.). Baltimore: The John Hopkins University Press.

Devo também mencionar que soluções para matrizes simétricas, como o que você deve resolver devido ao seu uso scipy.linalg.eigh, são um pouco baratas. Se você estiver interessado apenas em alguns autovalores, também poderá encontrar melhorias de velocidade no seu método. O método Arnoldi é frequentemente usado em tais situações.

Spencer Bryngelson
fonte
11
agradecimentos para o ponteiro, o algoritmo QR parece ser um bom ponto de partida
Yaroslav Bulatov
AA+λI
ps: linalg.eigh em uma matriz de 4k por 4k está demorando cerca de 20 segundos (ele usa apenas núcleo único por algum motivo). Eu preciso cerca de 0,25 segundo por atualização
Yaroslav Bulatov
7

t0O(N3)O(kN2)Nk

Aqui estão algumas referências relevantes:

Composição adaptativa de Eigend de matrizes de covariância de dados com base em perturbações de primeira ordem (Champagne, IEEE TSP 42 (10) 1994)

Atualização recursiva da decomposição de autovalores de uma matriz de covariância (Yu, IEEE TSP, 39 (5) 1991)

Análise on-line de componentes principais em alta dimensão: qual algoritmo escolher? (Cardot e Degras)

Um algoritmo estável e rápido para atualizar a decomposição de valor singular (Gu e Eisenstadt, 1994)

GoHokies
fonte
infelizmente não tenho pequenas atualizações de classificação, tenho pequenas atualizações de norma de classificação completa
Yaroslav Bulatov
@YaroslavBulatov Não estou ciente de um algoritmo eficiente que possa lidar com atualizações de classificação completa de normas pequenas - o melhor que pude encontrar foi essa referência , mas não parece muito promissor. É claro que existe uma grande quantidade de literatura sobre perturbação de autovalores que você pode querer examinar (veja a outra resposta).
GoHokies