Como calcular SVD de uma enorme matriz esparsa?

26

Qual é a melhor maneira de calcular a decomposição de valor singular (SVD) de uma matriz positiva muito grande (65M x 3,4M) em que os dados são extremamente escassos?

Menos de 0,1% da matriz é diferente de zero. Eu preciso de uma maneira que:

  • caberá na memória (eu sei que existem métodos online)
  • será calculado em um prazo razoável: 3,4 dias
  • será preciso o suficiente, no entanto, a precisão não é minha principal preocupação e eu gostaria de poder controlar a quantidade de recursos investidos nele.

Seria ótimo ter uma biblioteca Haskell, Python, C # etc. que a implementa. Eu não estou usando mathlab ou R, mas se necessário eu posso ir com R.

svd numerics Sonia
fonte
3
Quanta memória você tem? 0,1% de 65M * 3,4M ainda são 221e9 valores diferentes de zero. Se você usar 4 bytes por valor, isso ainda é superior a 55 gb, assumindo nenhuma sobrecarga, para que a dispersão ainda não resolva o problema ... Você precisa carregar todo o conjunto na memória de uma só vez?
Bitwise
Eu deveria ter sido mais preciso. Não mais que 250-500mb com número inteiro de 32 bits. Provavelmente muito menos, mas a dimensionalidade é o problema que eu entendo. Eu tenho uma máquina de 16GB.
Sonia
Que tal agora? Quora.com/…
Bitwise
Esta página links para uma biblioteca Python que implementa "um rápido, incremental, de pouca memória, o algoritmo SVD grande matriz": en.wikipedia.org/wiki/Latent_semantic_analysis
Bitwise
Consulte também stats.stackexchange.com/questions/2806 .
Ameba diz Reinstate Monica

Respostas:

21

Se ele se encaixar na memória, construa uma matriz esparsa em R usando o pacote Matrix e tente irlba para o SVD. Você pode especificar quantos vetores singulares deseja no resultado, que é outra maneira de limitar o cálculo.

Essa é uma matriz bastante grande, mas tive bons resultados com esse método no passado. irlbaé bastante state-of-the-art. Ele usa o algoritmo de bi-diagonalização Lanczos implicitamente reiniciado .

Ele pode percorrer o conjunto de dados do prêmio netflix (480.189 linhas por 17.770 colunas, 100.480.507 entradas diferentes de zero) em milissegundos. Seu conjunto de dados é ~ 200.000 vezes maior que o conjunto de dados da Netflix; portanto, leva muito mais tempo que isso. Pode ser razoável esperar que ele faça o cálculo em alguns dias.

Zach
fonte
a matriz de dados se encaixa na memória, a irlba também lidará com a decomposição de maneira eficiente na memória?
Sonia
@Sonia: irlba é muito eficiente em termos de memória: calcula uma solução aproximada, você pode limitar o número de vetores singulares e foi projetado para trabalhar em matrizes esparsas. Até onde eu sei, é o mais rápido possível para calcular SVDs parciais.
Zach
@Sonia: Boa sorte!
Zach
Dei uma tentativa de memória ... Vou calcular um bloco de triângulo antes de executá-lo.
Sonia
@Sonia, você a armazenou como esparsa Matrix? Tente limitar o número de valores singulares que você calcula ... talvez apenas veja o top 10?
Zach