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?
fonte
Respostas:
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 × m B ( n + m ) × ( n + m )
O algoritmo iterativo mais simples é chamado de iteração de energia e é realmente muito simples:
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:
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:
svd
executa decomposição completa via LAPACK esvds
calcula um determinado número de vetores singulares via ARPACK e, na verdade, é apenas um invólucro para umaeigs
chamada 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 emB UMA UMA diretamente no sem nunca construir o e, assim, economizar espaço e tempo.B UMA
Também existe uma biblioteca Fortran para esses métodos, chamada PROPACK :
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.
fonte
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).
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.
fonte
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:
fonte