Qual é o estado da arte atual em relação a algoritmos para a decomposição de valor singular?

12

Estou trabalhando em uma biblioteca de matriz somente de cabeçalho para fornecer um grau razoável de capacidade de álgebra linear em um pacote o mais simples possível e estou tentando pesquisar o que o estado da arte atual está re: computando o SVD de um matriz complexa.

Estou fazendo uma decomposição em duas fases, bidiagonalização seguida de cálculo de valor singular. No momento, estou usando o método de proprietário para a bidiagonalização (acredito que o LAPACK também use isso), e acho que é tão bom quanto é atualmente (a menos que alguém conheça um algoritmo para isso ..) . O(N2)

O cálculo do valor singular é o próximo na minha lista, e estou um pouco fora do circuito sobre quais são os algoritmos comuns para fazer isso. Li aqui que a pesquisa estava caminhando para um método de iteração inversa que garante ortogonalidade com complexidade . Eu estaria interessado em ouvir sobre esse ou outros avanços.O(N)

linear-algebra matrix svd gct
fonte
existe documento para sua biblioteca de matriz somente de cabeçalho (além do .h)? Adicione também a tag "svd".
Denis

Respostas:

7

"Algoritmos aleatórios" recentemente se tornaram bastante populares para svds parciais. Uma implementação apenas de cabeçalho pode ser baixada aqui: http://code.google.com/p/redsvd/

Uma revisão dos métodos atuais pode ser encontrada aqui: http://arxiv.org/abs/0909.4061

Para svds completos, não tenho certeza se você pode fazer melhor que o Household.

dranxo
fonte
Isso parece muito interessante, vou ter que dar uma olhada no trabalho de pesquisa, obrigado!
GCT
O OP está interessado em algoritmos para matrizes densas. Eu não acho que algoritmos aleatórios sejam competitivos nesse cenário, se eles funcionam.
Federico Poloni
Este post indicaram que os métodos randomizados funcionar muito bem em matrizes densas research.facebook.com/blog/294071574113354/fast-randomized-svd
dranxo
@dranxo Não há comparações de precisão nesse post, e os resultados do timing não parecem muito meticulosos. Além disso, algoritmos aleatórios são baseados na projeção + solução exata de um problema de pequena escala. Isso significa que o OP precisaria implementar um "método padrão" para o problema de pequena escala resultante.
Federico Poloni
Justo. Embora eu esteja um pouco confuso por que deveríamos pensar que esses métodos funcionam apenas em matrizes esparsas. Direto do resumo do artigo de Joel Tropp: "Para uma matriz de entrada densa, algoritmos aleatórios requerem operações de ponto flutuante O (mn log (k)) (flops) em contraste com O (mnk) para algoritmos clássicos". arxiv.org/pdf/0909.4061v2.pdf
dranxo
4

O(N)

(Eu queria fazer apenas alguns comentários, já que não tenho tempo para escrever detalhes, mas ficou muito grande para a caixa de comentários.)

LDL⊤UDU⊤

A parte "valor singular" do algoritmo, por outro lado, vem do algoritmo de diferença diferencial de quociente (deslocada) (dqd (s)) , que é o culminar de trabalhos anteriores de Fernando, Parlett , Demmel e Kahan (com inspiração Heinz Rutishauser).

Como você deve saber, os métodos SVD geralmente procedem primeiro à decomposição bidiagonal antes que os valores singulares sejam obtidos da matriz bidiagonal. Infelizmente, não estou muito atualizado sobre o melhor método atual para a decomposição bidiagonal do front-end; Por último, verifiquei que o método usual é começar com a decomposição QR com o pivô da coluna e depois aplicar transformações ortogonais apropriadamente ao fator triangular para finalmente obter a decomposição bidiagonal.

Entendo que tenho sido minucioso com os detalhes; Vou tentar aprofundar essa resposta assim que tiver acesso à minha biblioteca ...

JM
fonte
Matriz para a forma bi-diagonal, faça uma coluna e depois uma linha, repita a diagonal: use givens ou chefe de família para zerar a coluna até a diagonal e faça o mesmo para a linha até a super diagonal.
adam W
UAVUU⊤=IVV⊤=I