Quais algoritmos rápidos existem para calcular SVD truncado?

14

Possivelmente fora do tópico aqui, mas já existem várias ( uma , duas ) questões relacionadas.

Pesquisando na literatura (ou uma pesquisa no Google por algoritmos SVD truncados) aparece muitos artigos que usam SVDs truncados de várias maneiras e afirmam (frustrantemente, muitas vezes sem citação) que existem algoritmos rápidos para computá-lo, mas ninguém parece estar apontando para quais são esses algoritmos.

A única coisa que posso encontrar é um algoritmo aleatório único , usado na biblioteca redSVD .

O que eu gostaria de ver é um conjunto de algoritmos exatos e inexatos, adequados para entender como os sistemas funcionam (mas não necessariamente para realmente implementá-los, é claro!).

Alguém tem uma boa referência para esse tipo de coisa?

John Doucette
fonte
Se eu quiser armazenar bem os dados, uso uma árvore b (ou árvore rb) no hash (pense em ram). Se eu tivesse uma árvore b para os dados, poderia, em O (log (n)), quantificar amostra de quantis e tal. Aposto que com dados grandes, essa amostragem poderia ser usada para calcular uma aproximação esparsa decente das matrizes de svd em pouco tempo. Você também pode procurar "sensor compactado", que é uma abordagem muito estatística para extrema compactação de dados.
EngrStudent - Restabelece Monica
Com SVD truncado, você quer dizer que está interessado apenas em encontrar vários vetores / valores singulares principais, em oposição a todos eles?
Ameba diz Reinstate Monica
@amoeba Sim, essa é a ideia.
John Doucette

Respostas:

16

De um modo geral, existem duas abordagens para calcular decomposições de autovalores ou valores singulares. Uma abordagem é diagonalizar a matriz e isso essencialmente produz a decomposição de todo o valor próprio / valor singular (todo o espectro de valor próprio) ao mesmo tempo, veja algumas visões gerais aqui: Quais são os algoritmos eficientes para calcular a decomposição de valor singular (SVD)? A alternativa é usar um algoritmo iterativo que produz um (ou vários) vetores próprios por vez. As iterações podem ser interrompidas após o número desejado de vetores próprios ter sido calculado.

Eu não acho que existem algoritmos iterativos especificamente para SVD. Isto é porque se pode calcular SVD de um matriz B , efectuando uma eigendecomposition de um simétrica quadrado ( n + m ) x ( n + m ) de matriz Um = ( 0 B B 0 ) . Portanto, em vez de perguntar o que algoritmos de computação truncada SVD, você deve estar se perguntando o que iterativa algoritmos de computação eigendecomposition: algoritmo para truncada SVD iterativo algoritmo para eigendecomposition .n×mB(n+m)×(n+m)

UMA=(0 0BB0 0).
algoritmo para SVD truncadoalgoritmo iterativo para composição automática.

O algoritmo iterativo mais simples é chamado de iteração de energia e é realmente muito simples:

  1. Inicialize aleatório .x
  2. Atualizar .xUMAx
  3. Normalize .xx/__x__
  4. Vá para a etapa 2, a menos que esteja convergindo.

Todos os algoritmos mais complexos são baseados na idéia de iteração de energia, mas ficam bastante sofisticados. A matemática necessária é dada pelos subespaços de Krylov . Os algoritmos são iteração de Arnoldi (para matrizes quadradas não simétricas), iteração de Lanczos (para matrizes quadradas simétricas) e variações dos mesmos, como, por exemplo, "método Lanczos reiniciado implicitamente" e outros enfeites.

Você pode encontrar isso descrito em, por exemplo, os seguintes livros:

  1. Golub e Van Loan, Matrix Computations
  2. Trefethen & Bau, Álgebra Linear Numérica
  3. Demmel, Álgebra Linear Numérica Aplicada
  4. Saad, métodos numéricos para grandes problemas de autovalor

Todas as linguagens de programação razoáveis ​​e pacotes estatísticos (Matlab, R, Python numpy, o nome dele) usam as mesmas bibliotecas Fortran para executar decomposições de valor próprio / singular. Esses são LAPACK e o ARPACK . ARPACK significa ARnoldi PACKage, e é sobre iterações de Arnoldi / Lanczos. Por exemplo, no Matlab, existem duas funções para o SVD: svdexecuta decomposição completa via LAPACK e svdscalcula um determinado número de vetores singulares via ARPACK e, na verdade, é apenas um invólucro para uma eigschamada na matriz "de tamanho quadrado".

Atualizar

Acontece que existem variantes do algoritmo de Lanczos que são especificamente adaptadas para executar SVD de uma matriz retangular sem construir explicitamente uma matriz quadrada primeiro. O termo central aqui é bidiagonalização de Lanczos ; pelo que entendi, é essencialmente um truque para executar todas as etapas das iterações de Lanczos emBUMAUMA diretamente no sem nunca construir o e, assim, economizar espaço e tempo.BUMA

Também existe uma biblioteca Fortran para esses métodos, chamada PROPACK :

O pacote de software PROPACK contém um conjunto de funções para calcular a decomposição de valor singular de matrizes grandes e esparsas ou estruturadas. As rotinas SVD são baseadas no algoritmo de bidiagonalização de Lanczos com re-regionalização parcial (BPRO).

No entanto, o PROPACK parece ser muito menos padrão que o ARPACK e não é suportado nativamente nas linguagens de programação padrão. Foi escrito por Rasmus Larsen, que possui um grande artigo de 90 páginas sobre o texto de Lanczos bidiagonalização, com re - regionalização parcial, com o que parece uma boa visão geral. Graças a @MichaelGrant através deste tópico SE da Computational Science .

Entre os trabalhos mais recentes, o mais popular parece ser Baglama & Reichel, 2005, aumentado implicitamente reiniciado os métodos de bidiagonalização de Lanczos , que provavelmente está em torno do estado da arte. Obrigado a @Dougal por fornecer este link nos comentários.

Atualização 2

De fato, há uma abordagem totalmente diferente descrita em detalhes no documento de visão geral que você citou: Halko et al. 2009, Encontrando estrutura com aleatoriedade: algoritmos probabilísticos para a construção de decomposições matriciais aproximadas . Não sei o suficiente para comentar.

ameba diz Restabelecer Monica
fonte
Observe que existem métodos de iteração específicos para SVD; eg Métodos de Bidiagonalização de Lanczos Implicitamente Aumentados , J. Baglama e L. Reichel, SIAM J. Sci. Comput. 2005. (Eu não li o papel para saber se é fundamentalmente diferente da abordagem de valores próprios que você deu, só sei que pessoas como esse método.)
Dougal
1
Obrigado pelo link, @Dougal. Devo dizer que realmente não conheço bem nenhum desses métodos, por isso não posso comentar sobre isso. Seria ótimo se alguém com mais conhecimento explicasse a relação entre vários métodos iterativos. Até onde eu entendi, o método Lanczos de baunilha é para calcular autovalores de uma matriz quadrada e não para SVD; "Lanczos implicitamente reiniciado aumentado" deve estar intimamente relacionado a ele, mas você está certo - parece estar diretamente relacionado ao SVD. Não tenho certeza de como tudo se encaixa. Atualizarei minha resposta se alguma vez eu olhar mais de perto.
Ameba diz Reinstate Monica
1
@ Dougal, fiz algumas leituras superficiais e fiz uma atualização.
Ameba diz Reinstate Monica
@amoeba "SVD truncado" no contexto de mínimos quadrados regularizados seria essencialmente o mesmo que "regressão de componentes principais" ?
GeoMatt22 /
1
@amoeba Você pode comentar sobre a implementação aleatória de SVD do Facebook , algumas pessoas parecem dizer que ela está entre as soluções mais rápidas possíveis no momento. Seria ótimo se você pudesse editar para comentar também sobre isso.
Tim
4

Eu apenas tropecei no tópico através de SVDs rápidos no Google, então estou tentando descobrir as coisas sozinho, mas talvez você deva procurar a aproximação cruzada adaptativa (ACA).

MM=Eu=0 0kvocêEuVEuTN×NO(N)

Novamente, isso depende do seu problema, se isso funcionar. Em muitos casos, eu pessoalmente encontro, o ACA é uma ferramenta numérica muito útil.

Nota: eu queria escrever isso como um comentário, mas como acabei de criar essa conta, não tenho reputação suficiente para comentários ... Mas a publicação funciona.

oli
fonte
2

Aqui está uma técnica que usei com sucesso no passado para calcular um SVD truncado (no conjunto de dados da Netflix). É retirado deste artigo . Em uma configuração de filtragem colaborativa, devo observar que a maioria dos valores está faltando e o objetivo é prevê-los . Portanto, para usar SVD truncado para resolver esse problema, é necessário usar uma técnica que funcione sob essa condição. Uma breve descrição:

  1. Antes de fazer qualquer coisa, ajuste um modelo simples (por exemplo, média global + valores constantes de coluna e linha), e somente depois de fazer isso você deverá usar o SVD truncado para ajustar os resíduos.
  2. Inicialize um vetor aleatório de comprimento k (em que é a classificação que você está truncando) para cada linha e coluna (para cada filme e usuário no caso Netflix).
  3. Mantenha os vetores de linha fixos e atualize os vetores de coluna para minimizar o erro nas entradas conhecidas na matriz. O procedimento é fornecido no código matlab no documento.
  4. Mantenha os vetores de coluna fixos e atualize os vetores de linha de maneira análoga.
  5. Repita 3 e 4 até convergir ou obter bons resultados.
Stumpy Joe Pete
fonte