¿Cómo calcular SVD de una enorme matriz dispersa?

26

¿Cuál es la mejor manera de calcular la descomposición de valores singulares (SVD) de una matriz positiva muy grande (65M x 3.4M) donde los datos son extremadamente escasos?

Menos del 0.1% de la matriz no es cero. Necesito una forma que:

  • cabe en la memoria (sé que existen métodos en línea)
  • se computará en un tiempo razonable: 3,4 días
  • será lo suficientemente preciso, sin embargo, la precisión no es mi principal preocupación y me gustaría poder controlar la cantidad de recursos que le dedico.

Sería genial tener una biblioteca Haskell, Python, C # etc. que lo implemente. No estoy usando mathlab o R pero si es necesario puedo ir con R.

svd numerics Sonia
fuente
3
¿Cuanta memoria tienes? 0.1% de 65M * 3.4M sigue siendo 221e9 valores distintos de cero. Si usa 4 bytes por valor, eso sigue siendo más de 55 gb, suponiendo que no haya sobrecarga, por lo que la escasez aún no resuelve el problema ... ¿Necesita cargar todo el conjunto en la memoria de una vez?
Bitwise
Debería haber sido más preciso. No más de 250-500mb con un entero de 32 bits. Probablemente mucho menos, pero la dimensionalidad es el problema tal como lo entiendo. Tengo una máquina de 16GB.
Sonia
¿Qué tal esto? quora.com/…
Bitwise
Esta página web enlaza con una biblioteca de Python que implementa "un algoritmo SVD rápido, incremental, de baja memoria y matriz grande": en.wikipedia.org/wiki/Latent_semantic_analysis
Bitwise
Consulte también stats.stackexchange.com/questions/2806 .
ameba dice Reinstate Monica

Respuestas:

21

Si cabe en la memoria, construya una matriz dispersa en R usando el paquete Matrix e intente irlba para la SVD. Puede especificar cuántos vectores singulares desea en el resultado, que es otra forma de limitar el cálculo.

Esa es una matriz bastante grande, pero he tenido muy buenos resultados con este método en el pasado. irlbaes bastante vanguardista. Utiliza el algoritmo de bi-diagonalización Lanczos reiniciado implícitamente .

Puede analizar el conjunto de datos de premios de netflix (480,189 filas por 17,770 columnas, 100,480,507 entradas distintas de cero) en milisegundos. Su conjunto de datos es ~ 200,000 veces más grande que el conjunto de datos de Netflix, por lo que lleva mucho más tiempo que eso. Puede ser razonable esperar que pueda hacer el cálculo en un par de días.

Zach
fuente
la matriz de datos se adapta a la memoria, ¿irlba también manejará la descomposición de manera eficiente en la memoria?
Sonia
@Sonia: irlba es muy eficiente con la memoria: calcula una solución aproximada, puede limitar el número de vectores singulares y fue diseñado para trabajar en matrices dispersas. Hasta donde yo sé, es tan rápido como vas a obtener para calcular SVD parciales.
Zach
@Sonia: ¡Buena suerte!
Zach
Le di una prueba de memoria ... Calcularé una forma de bloque de triángulo antes de ejecutarlo.
Sonia
@Sonia ¿lo tienes almacenado como escaso Matrix? Intente limitar el número de valores singulares que calcula ... ¿tal vez solo mire los 10 principales?
Zach