computando o SVD truncado, um valor / vetor singular por vez

11

Existe um algoritmo SVD truncado que calcula os valores singulares, um de cada vez?

Meu problema: gostaria de calcular os primeiros k valores singulares (e vetores singulares) de uma matriz densa grande M , mas não sei qual seria um valor apropriado de k . M é grande, portanto, por razões de eficiência, prefiro não avaliar o SVD completo apenas para interromper os menores SVs posteriormente.

Idealmente, haveria uma maneira de calcular os valores singulares σ1 1,σ2, serialmente, do maior ( σ1 1 ) ao menor ( σn ). Dessa forma, eu poderia simplesmente interromper a computação depois de calcular o k ésimo valor se σk/σ1 1 cair abaixo de algum limite.

Existe um algoritmo desse tipo (de preferência com uma implementação em Python)? Na minha pesquisa, apenas encontrei funções SVD truncadas que tomam k como parâmetro, forçando-o a adivinhar a priori.

SuperElectric
fonte
O seu M é quadrado ou retangular? Se retangular, você deseja os vetores singulares longos ou curtos? Ou seja, se M é (mxn) com m> n, você deseja (mxk) ou (kxn)?
Max Hutchinson
M é retangular, com muito mais linhas que colunas. Eu quero os vetores singulares curtos (ou seja, V, em M = U S V ^ T).
SuperElectric

Respostas:

6

Existem algumas opções disponíveis se você quiser uma fatoração de classificação k aproximada.

  1. Fatores QR fortemente reveladores de classificação
  2. Decomposição interpolativa (ID) e outras técnicas randomizadas.

__UMA-MNT__fator×σk+1 1(UMA): =ϵ

Uma fatoração aproximada da forma acima pode ser convertida em uma decomposição padrão como QR ou SVD usando técnicas padrão. Uma boa revisão está disponível no artigo de Halko, Martinsson e Tropp "Encontrando estrutura com aleatoriedade: algoritmos probabilísticos para construir decomposições aproximadas de matriz"

Em termos de software, uma interface para algoritmos de ID está disponível em scipy (scipy.linalg.interpolative) http://docs.scipy.org/doc/scipy-dev/reference/linalg.interpolative.html, que permite ao usuário especificar .ϵ

user2457602
fonte
2

(Editado, porque eu li mal a pergunta; você já sabe que existem rotinas disponíveis para calcular os primeiros valores singulares.)k

Se você excluir a abordagem de calcular todo o SVD, os algoritmos parciais de SVD se reduzirão ao uso de métodos iterativos para resolver um problema relacionado de autovalor hermitiano. Portanto, uma estratégia que você poderia adotar seria codificar manualmente esse tipo de coisa e continuar resolvendo o maior valor singular ainda não resolvido até que você queira parar, usando algo como uma estratégia de mudança e inversão. Pode haver maneiras elegantes de fazer esse tipo de coisa em pacotes sofisticados como o SLEPc .

Outra estratégia seria a seguinte:

  • Calcule o maior valor singular .s1 1
  • Defina a tolerância absoluta da rotina SVD esparsa como , onde é seu limite e é um fator de segurança para determinar quantos valores singulares possivelmente desejáveis calcular.τs1 1fτ0 0<f1 1
  • Chame a rotina esparsa de SVD.

Se a rotina SVD esparsa calcular um SVD fino (e não consigo ver por que não faria), essa estratégia fornecerá todos os valores singulares que você deseja (além de possivelmente alguns extras), porque valores abaixo da tolerância absoluta ser tratado como zero. Nesse caso, você pode usar scipy.sparse.linalg.svds , observando que é um parâmetro opcional e que não precisa especificá-lo a priori .k

Geoff Oxberry
fonte
Se você não especificar 'k' em scipy.sparse.linalg.svds, o padrão será k = 6, independentemente do parâmetro 'tol'. Não está claro se este é um bug, ou se 'tol' é suposto para se referir à precisão dos valores singulares computadorizada (em vez de seu tamanho)
Nick Alger