¿Cuáles son los algoritmos eficientes para calcular la descomposición de valores singulares (SVD)?

17

El artículo de Wikipedia sobre análisis de componentes principales establece que

Existen algoritmos eficientes para calcular la SVD de sin tener que formar la matriz , por lo que calcular la SVD es ahora la forma estándar de calcular un análisis de componentes principales a partir de una matriz de datos, a menos que solo se requiera un puñado de componentes.XXTX

¿Podría alguien decirme cuáles son los algoritmos eficientes de los que habla el artículo? No hay referencia dada (URL o cita a un artículo que propone esta forma de cálculo sería bueno).

pca algorithms svd numerics svd
fuente
44
Una búsqueda de Google en un algoritmo de descomposición de valores singulares hace un buen trabajo al resaltar información relevante.
whuber
1
¡No olvide eliminar la media antes de SVD para PCA!
Memming
¡Prueba Lanczos SVD!
ciri

Respuestas:

12

El principal caballo de trabajo detrás del cálculo de SVD es el algoritmo QR . Habiendo dicho que hay muchos algoritmos diferentes para el cálculo de la descomposición de valor singular de un genérico -by- N matriz A . Un gran esquema sobre el problema disponible aquí (de la documentación del MKL de Intel ) es el siguiente:MNAingrese la descripción de la imagen aquí

Como puede ver, dependiendo de su caso de uso, existen diferentes enfoques (las convenciones de nomenclatura de rutina se pueden encontrar aquí ). Esto se debe a que, por ejemplo, hay formas matriciales en las que una reducción de Householder puede ser más costosa que una rotación de Givens (por nombrar dos formas "obvias" de obtener QR). Una referencia estándar sobre el tema son los cálculos matriciales de Golub y Van Loan (sugeriría usar al menos la 3a edición). También he encontrado Å. Los métodos numéricos de Björck para problemas de mínimos cuadrados son un recurso muy bueno al respecto; Si bien SVD no es el foco principal del libro, ayuda a contextualizar el uso.

Si tengo que darle un consejo general al respecto , no intente escribir sus propios algoritmos SVD a menos que ya haya tomado con éxito un par de clases sobre álgebra lineal numérica y sepa lo que está haciendo. Sé que suena contra-intuitivo, pero realmente, hay una tonelada de cosas que pueden salir mal y terminas con (en el mejor de los casos) implementaciones subóptimas (si no está mal). Hay algunas suites gratuitas muy buenas sobre el tema (por ejemplo , Eigen , Armadillo y Trilinos, por nombrar algunas).

usεr11852 dice Reinstate Monic
fuente
XA
1
MNAXTX
2
Sí, me equivoqué: QR no está restringido a matrices cuadradas. +1, por cierto. Esta pregunta fue una de las preguntas sin respuesta más votadas con la etiqueta pca , por lo que es bueno ver que finalmente se responde.
ameba dice Reinstate Monica
Su respuesta no menciona una variedad completa de algoritmos iterativos. ¿Fue a propósito? Alguien hizo una pregunta sobre algoritmos SVD iterativos, vea ¿Qué algoritmos rápidos existen para calcular SVD truncado? , y publiqué una respuesta allí tratando de proporcionar una visión general. Quizás deberíamos al menos entrecruzar nuestras respuestas. Y sin duda sería genial si puedes expandir el tuyo discutiendo los algoritmos QR versus los algoritmos iterativos.
ameba dice Reinstate Monica
No, fue accidental. Sin embargo, respondiste tu propia pregunta en tu publicación; Las SVD truncadas son esencialmente descomposiciones propias truncadas (véase, por ejemplo, ARPACK ). Hay algunas diferencias finas pero están bien ; algunos programas (p. ej., MATLAB svds) van tan lejos como simplemente usar su función SVD truncada como envoltorio para sus rutinas truncadas de eigendecomposition ( eigs).
usεr11852 dice Reinstate Monic