¿Qué es una explicación intuitiva de la descomposición de valores singulares (SVD)?

Answer 1

Hay un poco de matemática al comienzo de esta publicación, pero también escribí un programa rápido de MATLAB que visualiza lo que SVD puede hacer a una imagen.

En el contexto del análisis de datos, la idea es utilizar una aproximación de rango reducido de un conjunto de datos para generalizar algunas de las propiedades / estructuras.

---

¿Qué es la descomposición del valor singular?

Para encontrar una SVD de A, debemos encontrar V, \ Sigma y U de manera que:

[matemáticas] A = U \ Sigma V ^ T [/ matemáticas]

1. [matemática] V [/ matemática] debe diagonalizar [matemática] A ^ TA [/ matemática]
1.1. [math] v_i [/ ​​math] son ​​vectores propios de [math] A ^ TA [/ math].

2. [matemática] \ Sigma [/ matemática] donde [matemática] \ Sigma_ {ii} [/ matemática] son ​​valores singulares de [matemática] A [/ matemática].
3. [matemática] U [/ matemática] debe diagonalizar [matemática] AA ^ T [/ matemática]
3.1 [math] u_i [/ ​​math] son ​​vectores propios de [math] AA ^ T [/ math].

Si [matemáticas] A [/ matemáticas] tiene rango [matemáticas] r [/ matemáticas] entonces:

1. [math] v_i \ cdots v_r [/ math] forma una base ortonormal para el rango de [math] A ^ T [/ math]
2. [math] u_i \ cdots u_r [/ math] forman una base ortonormal para el rango de [math] A [/ math]
3. El rango de [matemáticas] A [/ matemáticas] es igual al número de entradas distintas de cero de S. De la forma de esta factorización

Vemos que podemos expresar [matemática] A [/ matemática] de otra manera, se puede demostrar que [matemática] A [/ matemática] puede escribirse como una suma de matrices de Rango = 1.

[matemáticas] A = \ sum_ {i = 1} ^ r \ sigma_iu_iv_i ^ T [/ matemáticas]

Sabemos que por construcción [math] \ sigma_i [/ ​​math] decreciente monotónico, la importancia / peso del término [math] n ^ {th} [/ math] disminuye. Esto significa que la suma de [math] k <r [/ math] es una aproximación [math] \ hat {A} [/ math] de rango [math] k [/ math] para la matriz [math] A [/ matemáticas].

---

tl; dr

La descomposición de valores singulares trata esencialmente de reducir una matriz de rango [matemática] R [/ matemática] a una matriz de rango K.

Pero ¿qué significa esto?

Significa que podemos tomar una lista de vectores únicos [matemáticos] R [/ matemáticos] y aproximarlos como una combinación lineal de vectores únicos [matemáticos] K [/ matemáticos].

---

Tome este ejemplo, la imagen a continuación es una imagen hecha de 400 vectores de fila únicos.

SVD es mi algoritmo favorito, y Feynman es mi científico favorito.

¿Qué sucede si tomo el primer vector singular?

Tenga en cuenta que cada fila de píxeles es la misma … solo diferente ‘brillo’

Esencialmente, cada fila ahora se puede escribir como [math] R_i = c_i \ cdot SV_1 [/ math] donde [math] c_i [/ ​​math] es el factor de escala y [math] SV_1 [/ math] es el vector singular con El valor singular más alto (mayor contribución a los datos)

¿Qué sucede si tomo los primeros dos vectores singulares?

Ahora, cada fila se puede escribir como la suma de dos vectores

[matemáticas] R_i = c_i \ cdot SV_1 + b_i \ cdot SV_2 [/ matemáticas]

Donde [math] SV_2 [/ math] es el segundo vector singular más influyente.

k = 10

¿Puedes creerlo? ¡Con solo 10 vectores únicos, casi puedo distinguir la imagen!

k = 50

Ahí tienes.

Usando 50 valores únicos y obtienes una representación decente de cómo se ven 400 valores únicos.

---

Espacio vectorial de las cosas.

Piensa en otro ejemplo. Digamos que soy netflix. Y tengo 100 millones de usuarios y cada uno ha visto las mismas 500 películas.

Lo que puedo decir es que cada persona puede caracterizarse en base a [matemáticas] R ^ n [/ matemáticas] donde [matemáticas] n = 100 [/ matemáticas]. Entonces cada usuario está en el espacio vectorial de las películas.

¿Cómo razono sobre estos datos? No tenemos forma de ‘reducir’ la dimensión del espacio vectorial de las películas. ¿Cómo obtengo información?

Tal vez tomaré la SVD truncada en … k = 50.

¿Qué significa esto? Esto significa que voy a encontrar los mejores 50 vectores que podrían ser una buena representación de la matriz. Voy a encontrar los vectores singulares, lo que hago es matemáticamente la siguiente declaración.

Es un cambio de base de la base de la película a la primera base de vector singular k. La interpretación podría ser que cada usuario puede ser igual a

[matemáticas] usuario = \ Sigma ^ {50} c_i \ cdot SV_i [/ ​​matemáticas]

Donde SV son los vectores singulares.

Podemos considerar esos 50 valores singulares como ‘tipos de usuarios’. Podemos descubrir que [math] SV_3 [/ math] tiene calificaciones altas en películas deportivas mientras que [math] SV_2 [/ math] tiene calificaciones muy altas en películas de terror.

Esto nos permite considerar solo 50 tipos de usuarios y usar esos 50 para generalizar los 500 (tada, tiene reducción de dimensionalidad)

SV_1 = documentales
SV_2 = horror
SV_3 = deportes
…

Cuando miramos los valores singulares (en lugar de los vectores singulares) notamos que un usuario tiene los valores [0,4,2,0 ..]

Esto significa que user = [math] 4 \ cdot SV_2 + 2 \ cdot SV_3 +… [/ math]

Traducción: a este usuario le gustan las películas de terror y tal vez también ve deportes.

---

Podemos reescribir a las personas desde la base de la película al género de la película. Eso es matemático, también funciona bastante bien.

Otros ejemplos podrían ser desde la base de la palabra hasta la base del tema o la base de la ropa y la moda.

Answer 2

Mira las líneas en esta figura.

Estas son gráficas de cuatro vectores en 2D. Es difícil de ver, pero todos son ligeramente diferentes. A pesar de estas diferencias, podemos ver un patrón en ellas. Todos tienen aproximadamente el mismo ángulo desde el eje x. Estas líneas se pueden representar como vectores de columna. Por ejemplo, la línea de (0,0) a (1.1,1) está representada por el vector [1.1, 1]. Organice estos vectores como columnas en una matriz de 2 filas y 4 columnas y tome la SVD. Los valores singulares son aproximadamente 2.788 y 0.1084. Hay dos vectores singulares a la izquierda que corresponden a estos valores. Mira el primero, que es el que corresponde al primer valor singular 2.788:
Observe que esta línea es un vector unitario (es decir, longitud 1) que tiene un ángulo similar al de los cuatro vectores anteriores. El SVD ha extraído el patrón, es decir, ha tomado cuatro líneas bidimensionales con aproximadamente el mismo ángulo y las ha representado con una línea de un ángulo similar. Al establecer el primer valor singular mucho más grande que el segundo (es decir, 2.788> 0.1084), la SVD nos ha indicado que nuestros datos se encuentran principalmente a lo largo de esta línea con un poco de variación (esto puede hacerse más preciso al entrar en los detalles).

Ahora mira estas cuatro líneas:

Son similares a antes, solo que ahora dos de las líneas son aproximadamente ortogonales a las otras dos (es decir, en ángulos de 90 grados entre sí; los ángulos no se ven tan cerca de 90 grados visualmente como lo son en realidad, debido a la escala de los ejes). Haciendo lo mismo que arriba, el SVD nos da valores singulares de aproximadamente 2.073 y 1.976. Esta vez trazaremos ambos vectores singulares izquierdos en lugar de solo el primero:
Dado que los valores singulares son casi iguales en magnitud, la SVD nos indica que ambos vectores son igualmente importantes para representar una muestra en nuestros datos, por lo que no podemos aproximarnos con una sola línea. Esto tiene sentido: tenemos muestras en nuestros datos que están en ángulos de 90 grados con respecto a los otros datos y de magnitud similar, es decir, están aproximadamente tan lejos como los vectores de aproximadamente la misma magnitud pueden estar en términos de la distancia euclidiana.

Lo que hace la SVD es encontrar “patrones” en los datos. Esto es demasiado ambiguo, ya que “patrones” puede significar casi cualquier cosa, pero el ejemplo anterior da una idea de qué tipo de patrón está relacionado con la SVD (o al menos uno de los patrones más importantes). Es decir, trata de encontrar una línea que represente más estrechamente los datos (primer vector singular a la izquierda). Después de eso, agrega otra línea para formar un plano que representa más de cerca los datos. Si tiene datos de dimensiones superiores, esto continúa. Lo bien que esto funcione depende de algo como el “ángulo” entre sus muestras (las “muestras” se refieren a las cuatro líneas diferentes).

En dimensiones superiores, esto se visualiza de diferentes maneras, pero aún se puede ver. Por ejemplo, tomemos un conjunto particular de cuatro vectores de 32 dimensiones y grafiquemos cada uno de los 32 componentes en el eje y con el índice del vector en el eje x.
Al hacer lo mismo que antes, terminamos con una matriz de 32 filas y 4 columnas. Tomando la SVD, los valores singulares son aproximadamente 7.878, 0.3360, 0.2261 y 0.2044. Observe el primer valor grande seguido de valores más pequeños. Los primeros dos vectores singulares izquierdos, trazados de la misma manera que arriba, son

Observe cómo el primer vector singular izquierdo extrae el patrón que vemos en nuestros datos y el segundo vector singular izquierdo parece puntos aleatorios. El SVD está haciendo lo mismo que antes. El primer valor singular grande en comparación con los otros valores singulares nos dice que los datos se encuentran principalmente a lo largo del primer vector singular izquierdo.

Para un ejemplo de mayor dimensión con datos ortogonales, mire los siguientes vectores de datos:

El SVD da como resultado valores singulares 5.650, 5.547, 0.3671, 0.2464. Los primeros tres vectores singulares izquierdos son

Observe cuán regulares son los primeros dos vectores singulares izquierdos mientras que el último parece valores aleatorios nuevamente. Dado que los dos primeros valores singulares son aproximadamente iguales en magnitud y mucho más grandes que los demás, los datos estarán bastante cerca de un vector representado por una combinación lineal de los dos primeros.

Hay una variedad de formas de interpretar estos resultados, pero uno especialmente popular últimamente es el estadístico. El ángulo entre vectores se relaciona con la correlación de variables aleatorias. En particular, cuando las variables aleatorias se representan como vectores, entonces las variables correlacionadas son líneas con ángulos similares y las variables no correlacionadas son líneas que son casi ortogonales. Las variables aleatorias que están correlacionadas significan que conocer el valor de una te dice algo sobre la otra. Por ejemplo, la riqueza y la salud de una persona están correlacionadas, ya que las personas ricas pueden permitirse una mejor atención médica (entre otras razones). Las variables no correlacionadas son aquellas que no tienen relación. Por ejemplo, si lanzo una moneda y cae en la cabeza, esto no me dice nada acerca de quién ganará la medalla de oro olímpica en la carrera de 100 metros en 2016, por lo que estos dos eventos no están correlacionados. Entonces, una forma de interpretar intuitivamente la SVD es que identifica correlaciones en los datos. Esto es útil para todo tipo de cosas. Por ejemplo, digamos que el 99% de las personas que califican a Buffy the Vampire Slayer 5 estrellas en Neflix también califican a Firefly 5 estrellas. Ahora supongamos que un hombre ha calificado a Buffy the Vampire Slayer 5 estrellas pero no ha visto Firefly. Luego, el SVD se puede usar para determinar automáticamente que Netflix debería recomendar que este pobre hombre remedie su desafortunada situación y ya vea Firefly.

También hay ideas relacionadas con la “suavidad” de las funciones que muestran cómo la SVD es útil. Sin preocuparse por lo que significa “suavidad”, se puede demostrar que la SVD tiene valores singulares que disminuyen rápidamente para funciones altamente uniformes. Esto hace que la SVD sea útil para los algoritmos de compresión porque muchas funciones de la vida real son “fluidas”.

Esto pasa por alto muchas cosas y es más una serie de ejemplos que una explicación, pero espero que sea útil.

Answer 3

Las respuestas aquí hasta ahora son geniales. Sin embargo, creo que la pregunta original dice “intuitiva” y muchas de las respuestas aquí son complejas. Trataré de mover mis manos aquí para hacer las cosas más visuales. Una forma de entender el SVD es que encuentra una transformación de un elipsoide a la esfera de la unidad. En álgebra lineal estudiamos transformaciones lineales de sistemas de coordenadas. Tome cualquier base y piense en cada vector como un eje de una elipse de alta dimensión. Estos ejes no son necesariamente ortogonales, pero si pudiéramos encontrar una manera de “enderezarlos”, terminaríamos con una esfera. De forma ondulada, esto es esencialmente lo que SVD está haciendo.

[matemáticas] M = U \ Sigma V ^ {\ top} [/ matemáticas]

La descomposición anterior se puede interpretar como dos rotaciones intercaladas alrededor de una escala arbitraria de cada eje que induce un cizallamiento de la esfera de la unidad. Si invertimos esta transformación, deberíamos volver a la esfera de la unidad y la matriz de identidad:

[matemáticas] M ^ {- 1} = (U \ Sigma V ^ {\ top}) ^ {- 1} = V ^ {- \ top} \ Sigma ^ {- 1} U ^ {- 1} = V \ Sigma ^ {- 1} U ^ {\ top} [/ math]

Lo anterior se llama pseudoinverso de M y generaliza los inversos de matriz a matrices no cuadradas. Sería bueno poder hacer toda esta operación con una colección de vectores linealmente dependientes también, ya que nos permitiría resolver sistemas con restricciones excesivas. SVD nos permite limitar las operaciones, como ajustar modelos a datos del mundo real, lo que nos permite proporcionar más muestras que la dimensionalidad de los vectores de datos. Esto nos permite entrenar un modelo utilizando todos nuestros datos para encontrar el “mejor” ajuste en el sentido lineal de mínimos cuadrados. El SVD ha sido un caballo de batalla para las comunidades de visión artificial y aprendizaje automático durante mucho tiempo.

Wikipedia tiene una buena visualización de este proceso:

Answer 4

La respuesta de Vinod es completamente correcta. Permítanme probar un enfoque diferente que puede explicarlo para un lego más laico, como uno sin antecedentes de álgebra lineal.

Para eso, creo que solo es posible explicar la SVD apelando a una aplicación intuitiva de factorización matricial, como PCA. No sé si puede explicar la SVD como algo separado de NNMF sin el conocimiento de un especialista, pero puede describir algo para lo que se usa.

PCA puede ayudar a explicar las observaciones de muchas cosas en particular en términos de muy pocas cosas generales, y eso coincide con la cantidad de cosas en el mundo que funcionan, lo cual es útil. Si voy al estante de su CD, veré 100 álbumes diferentes, de un mundo de un millón de álbumes. Tal vez veo “A Love Supreme” de John Coltrane y “Kind of Blue” de Miles Davis. (Estos resultan ser famosos álbumes de jazz).

Sin embargo, no creo que describas tus preferencias musicales de esta manera, al enumerar 100 álbumes. Probablemente dirías “Me gusta el jazz”. Eso no solo es más eficiente de decir, sino que comunica más: es probable que tenga cierta afinidad por otros diez mil discos de Jazz.

Si realmente no pensáramos y ‘nos gusta’ las cosas en términos de géneros, sería mucho más difícil razonar sobre los gustos. Cada álbum sería una isla en sí mismo y hablaría poco sobre su preferencia por los demás. Pero, debido a que tenemos la idea subyacente de “Jazz”, de repente al saber que estos son álbumes de “Jazz”, tengo un mundo de conjeturas más informadas sobre su interés en otros álbumes de Jazz como el de Charles Mingus.

PCA está tratando de encontrar esas características subyacentes, “géneros” en el caso de la música. Encontrará el pequeño conjunto de características que mejor explican algunas entradas, como una lista de todos los CD propiedad de un grupo de oyentes. De estas asociaciones de álbum de usuario obtenemos dos salidas, asociaciones de características de usuario (es decir, cuánto me gusta Jazz, Rock, R&B) y asociaciones de características de elementos (es decir, cuánto es cada álbum un álbum de Jazz, un álbum de Rock). También obtenemos un tercer resultado que dice cuán relativamente importantes son estos para explicar los gustos.

A partir de ahí, puede hacer cosas útiles, entre las que se incluyen recomendaciones, llenar el estante de su CD, con álbumes que este modelo predice que le gustan. Puede comparar eficientemente la similitud de los álbumes / usuarios en términos de pocas características. Incluso puede decidir tirar o agregar géneros (mantener más / menos S) para crear un modelo de géneros más o menos matizado.

La SVD es la mayor parte de la maquinaria que permite lo anterior. Cómo funciona no es posible explicarlo al lego, ni puede ser útil explicarlo. Lo que hace (bueno, lo que hace PCA) definitivamente puede ser.

Answer 5

SVD significa Descomposición de valor singular. Es un método para descomposición / factorización de matrices. La forma más sencilla de visualizar y comprender cómo es útil SVD es pensar en términos de Análisis de componentes principales (PCA) / reducción de dimensionalidad.

Supongamos que desea reducir los datos X de n-dimensiones a k-dimensiones donde k

Aquí hay un método para hacer esto usando SVD: Como primer paso, realice la normalización media y el escalado de características en X. Luego, calcule una matriz de covarianza Sigma para X. En el paso de seguimiento, calcule SVD en Sigma para obtener sus vectores propios.

[U, S, V] = SVD (Sigma).

Algunas notas interesantes sobre el resultado de la factorización:
– Las columnas de la matriz U forman los vectores propios de Sigma.
– La matriz S es una matriz diagonal. Los valores de la diagonal se denominan valores propios y están en orden descendente.

La matriz U es una matriz nxn. Si reduce el número de vectores de columna a k (primera k), entonces ha obtenido el hiperplano k-dimensional en este ejemplo. Los valores de S le dan la cantidad de varianza retenida por esta reducción. Para ser precisos, la relación entre la suma de los valores k superiores a lo largo de la matriz S diagonal y la suma de todos los valores a lo largo de la matriz S diagonal da la cantidad de varianza.

Llamemos a la matriz U con vectores de columna reducidos como no reducidos. El conjunto de datos en la dimensión reducida se puede obtener como: transposición (no reducido) * X

Para un tratamiento completo en SVD, consulte este enlace: http://nimbledais.com/?p=57
Espero que esto ayude.

Answer 6

Imagina una galaxia espiral. Como éste:

Es un objeto 3D.

Ahora, quieres trazarlo para mí, mostrándolo en toda su forma. En una hoja de papel 2D.

Intuitivamente, para lograr esto, tratarías de presentarlo desde un ángulo que desenrolle su complejidad tanto como sea posible, dándome la mejor proyección de la galaxia. La “vista superior”, así:

Como en matemáticas tendemos a convertir todo en números, aquí hay un número para ti. La proyección A es mejor que la proyección B si se minimiza la distancia 3D “real” promedio de cada punto a su proyección.

Naturalmente, cuanto más se acerque a esta proyección “plana”, más se acercarán al “plano” de esta proyección los puntos.

Por lo tanto, esta proyección de “vista superior” va a lo largo de dos primeros vectores singulares.

---

Esta es la razón por la cual SVD se usa con frecuencia como el primer intento de reducción de dimensiones en problemas de minería de datos. Porque a menudo se pueden visualizar bien más de 1000 dimensiones en un espacio de dimensiones inferiores, a veces incluso en 2D o 3D. Entonces, los grupos pueden ser vistos por un ojo humano, sin maquinaria avanzada y / o imaginación.

---

Además, así es como se puede usar SVD para obtener la “dimensionalidad efectiva” de un conjunto de puntos. Un conjunto de estrellas en una galaxia espiral tendría una dimensionalidad ligeramente superior a dos; quizás alrededor de 2.25. Esto se debe a que dos dimensiones “ortogonales” transmiten mucha información sobre esas estrellas, mientras que la tercera no agrega tanta información.

En el caso de SVD, este aproximado de 2.25 sería la suma de (los tres) valores singulares (*).

(*) Si los datos se han normalizado en cada dimensión de entrada antes de aplicar SVD. Solía ​​hacer estos cálculos hace un tiempo, pero es probable que haya olvidado los detalles.

Answer 7

Veo que la mayoría de estas respuestas se centran en SVD como un medio de aproximación / reconstrucción de una matriz [math] \ mathbf {A} [/ math] como una suma de productos externos escalados. No hay problema allí, pero ¿qué pasa si queremos pensar en [math] \ mathbf {A} [/ math] como una transformación lineal? SVD nos da una idea de la función que es [math] \ mathbf {Ax}: \ mathcal {R} ^ n \ Rightarrow \ mathcal {R} ^ m [/ math], tanto que la relación ha sido coronada. Teorema del álgebra lineal . Con algo de matemática, obtendremos una intuición real.

SVD en una cáscara de nuez

Seamos precisos. Deje que [math] \ mathbf {A} [/ math] sea una matriz de rango r con m filas yn columnas. SVD nos dice:

[math] \ mathbf {A} = \ mathbf {U} \ boldsymbol {\ Sigma} \ mathbf {V} ^ T [/ math]

dónde:

1. [math] \ mathbf {U} [/ math] es una matriz cuadrada ortonormal m x m . Sus columnas son los vectores singulares izquierdos.
2. [math] \ boldsymbol {\ Sigma} [/ math] es una matriz diagonal m x n con r valores positivos que comienzan desde la parte superior izquierda. Estos son los valores singulares.
3. [math] \ mathbf {V} ^ T [/ math] es una matriz cuadrada ortonormal n x n . Las filas son los vectores singulares correctos.

¿Te sientes iluminado? Yo tampoco, pero llegaremos allí.

Un ejemplo y una analogía

Digamos que [math] \ mathbf {A} [/ math] tiene r = 3, m = 6 yn = 4. Puede visualizarlo así:

Parece que hay muchas dimensiones aquí ¿eh? ¿Por qué necesitamos 6 columnas lineales independientes de [math] \ mathbf {U} [/ math] para reconstruir las 4 columnas de [math] \ mathbf {A} [/ math]? Bueno, no lo hacemos: los vectores rojos no contribuirán nada porque finalmente se multiplican por cero. Sin embargo, estas dimensiones adicionales son útiles para contextualizar la operación de [math] \ mathbf {A} [/ math] dentro de los espacios de [math] \ mathcal {R} ^ 4 [/ math] y [math] \ mathcal {R } ^ 6 [/ matemáticas]. Observe que si [math] \ mathbf {U} [/ math] es ortogonal con lados de longitud 6, debe abarcar [math] \ mathcal {R} ^ 6 [/ math]. Del mismo modo, [math] \ mathbf {V} [/ math] debe abarcar [math] \ mathcal {R} ^ 4 [/ math]. Con eso, podemos representar cualquier [math] \ mathbf {x} [/ math] dado como [math] \ mathbf {Vc} [/ math]. Piense en el vector [math] \ mathbf {c} [/ math] como una receta para hacer [math] \ mathbf {x} [/ math] de los ingredientes que son [math] \ mathbf {V} [/ math columnas de]. Ahora, apliquemos nuestra función:

[math] \ mathbf {Ax} = \ mathbf {U} \ boldsymbol {\ Sigma} \ mathbf {V} ^ T \ mathbf {Vc} = \ mathbf {U} \ boldsymbol {\ Sigma} \ mathbf {c} [ /matemáticas]

que se parece a:

Mira eso. [math] \ boldsymbol {\ Sigma} \ mathbf {c} [/ math] es solo nuestra receta [math] \ mathbf {x} [/ math] escalada por elementos por los valores singulares, dejando solo 3 ( r ) no -valores cero. Con esta receta reajustada, la salida [math] \ mathbf {U} \ boldsymbol {\ Sigma} \ mathbf {c} [/ math] es solo nuestra receta aplicada, pero con los ingredientes como [math] \ mathbf {U} [ / math] ‘s columnas.

Lo diré de otra manera. [math] \ mathbf {Ax} [/ math] es una combinación lineal de los vectores singulares izquierdos (columnas de [math] \ mathbf {U} [/ math]) donde esa combinación está determinada por:

1. la receta para hacer [math] \ mathbf {x} [/ math] a partir de los vectores singulares derechos (columnas de [math] \ mathbf {V} [/ math]). Entonces, si [math] \ mathbf {x} [/ math] está formado por [math] \ mathbf {v} _2 [/ math], entonces la salida tendrá mucho [math] \ mathbf {u} _2 [/ matemáticas].
2. los 3 valores singulares, que escalan elementos de [math] \ mathbf {c} [/ math] y determinan cuáles no están triturados a cero.

Esa es la idea principal, pero es parte de una imagen más grande …

El teorema fundamental del álgebra lineal

Integrado en esto hay una conexión extremadamente importante: SVD nos dice cómo se relaciona el espacio de fila (todos los vectores que se podrían hacer con una combinación lineal de las filas de [math] \ mathbf {A} [/ math]) con el espacio de columna (todos vectores que podrías hacer con una combinación lineal de las columnas ). Específicamente, es ese número mágico 3: esto refleja la dimensión tanto del espacio de la columna como del espacio de la fila. En lo que se refiere a la salida de función [math] \ mathbf {Ax} [/ math], solo hay 3 dimensiones (las del espacio de fila) dentro de las 4 dimensiones que [math] \ mathbf {x} [/ math] vive por lo que los movimientos darán lugar a movimientos en la salida [math] \ mathbf {Ax} [/ math], que en consecuencia solo puede moverse en 3 dimensiones (las del espacio de la columna). Así que imagina que te di dos vectores [math] \ mathbf {x} _1 [/ math] y [math] \ mathbf {x} _2 [/ math] que tienen recetas [math] \ mathbf {c} _1 [/ math] y [math] \ mathbf {c} _2 [/ math], pero la única diferencia fue su carga para [math] \ mathbf {v} _4 [/ matemáticas]. Bueno, sus resultados [math] \ mathbf {Ax} _1 [/ math] y [math] \ mathbf {Ax} _2 [/ math] serían los mismos porque esa carga se multiplica por cero. ¡Esa dimensión no importa! De hecho, ese espacio (en este caso, la línea unidimensional a lo largo de [math] \ mathbf {v} _4 [/ math]) tiene un nombre: el espacio nulo de [math] \ mathbf {A} [/ math].

Ahora hemos contabilizado las 4 dimensiones donde vive [math] \ mathbf {x} [/ math]. Sería bueno tener en cuenta todas las dimensiones de [math] \ mathcal {R} ^ 6 [/ math] también. Por suerte, es fácil. Sabemos que la salida [math] \ mathbf {Ax} [/ math] debe ser una combinación lineal de las primeras 3 columnas (azules) de [math] \ mathbf {U} [/ math] (todo lo demás se multiplica por cero) y por lo tanto, solo puede moverse en 3 dimensiones. Las 3 dimensiones restantes se pueden considerar como el subespacio ‘inalcanzable’ de [math] \ mathcal {R} ^ 6 [/ math]: no podemos elegir ninguna [math] \ mathbf {x} [/ math] de modo que nuestra salida aterrizará en este espacio. Llamamos a esto el espacio nulo de [matemáticas] \ mathbf {A} ^ T [/ matemáticas] (Por una buena razón, lo prometo).

Por lo tanto, hemos tenido en cuenta todas las dimensiones de [math] \ mathcal {R} ^ 4 [/ math] y [math] \ mathcal {R} ^ 6 [/ math], con algunos subespacios con nombre. Vamos a revisarlos:

1. espacio nulo de [math] \ mathbf {A} [/ math], llámelo nulo ([math] \ mathbf {A} [/ math]) – subespacio de [math] \ mathcal {R} ^ 4 [/ math] donde los movimientos no hay diferencia en la salida [math] \ mathbf {Ax} [/ math]. Piense en ello como el espacio ‘No importa’.
2. espacio de columna de [math] \ mathbf {A} [/ math], llámelo col ([math] \ mathbf {A} [/ math]) – subespacio de [math] \ mathcal {R} ^ 6 [/ math] donde [math] \ mathbf {Axe} [/ math] podría aterrizar con un [math] \ mathbf {x} [/ math] elegido correctamente. Piense en ello como el espacio “accesible”.
3. espacio nulo de [math] \ mathbf {A} ^ T [/ math], llámelo nulo ([math] \ mathbf {A} ^ T [/ math]) – subespacio de [math] \ mathcal {R} ^ 6 [/ math] donde [math] \ mathbf {Axe} [/ math] nunca podría tocar. Piense en ello como el espacio ‘inalcanzable’.
4. espacio de fila de [math] \ mathbf {A} [/ math], que también es el espacio de columna de [math] \ mathbf {A} ^ T [/ math], así que llámelo col ([math] \ mathbf {A } ^ T [/ math]) – subespacio de [math] \ mathcal {R} ^ 4 [/ math] que impulsa la diferencia en [math] \ mathbf {Ax} [/ math]. Piense en ello como el espacio de ‘Asuntos’.

¿Comienza a ver algo de simetría aquí? Eso es intencional Pero primero, pensemos en esta relación gráficamente. Ayudará a pensar en [math] \ mathbf {x} [/ math] como compuesto de dos partes, lo que existe en col ([math] \ mathbf {A} ^ T [/ math]) (llamada it [math] \ mathbf {x} _r [/ math]) y lo que existe en nulo ([math] \ mathbf {A} [/ math]) (llámelo [math] \ mathbf {x} _n [/ math ]). Entonces tenemos [math] \ mathbf {x} = \ mathbf {x} _n + \ mathbf {x} _r [/ math].

Vemos que [math] \ mathbf {Ax} [/ math] y [math] \ mathbf {Ax} _r [/ math] se asignan al mismo punto. En otras palabras, solo la parte de [math] \ mathbf {x} [/ math] que reside en el espacio de la columna de [math] \ mathbf {A} ^ T [/ math] es importante para determinar su salida, ya que ‘ He visto anteriormente.

Pero, ¿qué pasa si consideramos un punto [math] \ mathbf {y} [/ math] en [math] \ mathcal {R} ^ 6 [/ math] y aplicamos [math] \ mathbf {A} ^ T [/ math] como una función para obtener [math] \ mathbf {A} ^ T \ mathbf {y} [/ math]? Bueno, todos estos subespacios permanecen y tenemos una relación familiar inversa:

Comparando estos dos gráficos, vemos la equivalencia:

1. El espacio ‘inalcanzable’ con multiplicación por [math] \ mathbf {A} [/ math] es el espacio ‘No importa’ para la multiplicación por [math] \ mathbf {A} ^ T [/ math] y viceversa.
2. El espacio ‘Materias’ para la multiplicación por [math] \ mathbf {A} [/ math] es el espacio ‘Accesible’ para la multiplicación [math] \ mathbf {A} ^ T [/ math] y viceversa.

Envolviendolo

SVD nos dice cómo descomponer una matriz en conjuntos de vectores ortonormales que abarcan [math] \ mathcal {R} ^ n [/ math] y [math] \ mathcal {R} ^ m [/ math]. Dependiendo de los valores singulares con los que estén emparejados, sabemos qué subespacio de [math] \ mathcal {R} ^ n [/ math] importa (y no importa) para conducir [math] \ mathbf {Ax} [/ math ] dentro del espacio accesible de [math] \ mathcal {R} ^ m [/ math]. Específicamente, [math] \ mathbf {Ax} [/ math] será una combinación lineal de los vectores de expansión del espacio ‘Alcanzable’ donde esa combinación depende de los valores singulares y la receta para hacer [math] \ mathbf {x} [/ math] de los vectores que abarcan el espacio ‘Matters’. Esa conexión obliga a que la dimensionalidad de estos espacios sea la misma. Considerar la multiplicación por [math] \ mathbf {A} ^ T [/ math] nos dice que podemos pensar en los espacios ‘Alcanzables’ como espacios ‘Importantes’ e ‘Inalcanzables’ como ‘No Importa’ si vemos desde una dirección diferente .

Answer 8

En lugar de repetir cosas, me gustaría dirigirlo a https://www.cs.cmu.edu/~venkatg/ … Es un capítulo del libro de Hopcroft y Kannan llamado Fundamentos de la ciencia de datos . Tiene quizás la explicación más intuitiva y prácticamente basada en la SVD que he leído, con una lista de todas las principales aplicaciones de SVD en el aprendizaje automático.

Answer 9

Jeremy Kun acaba de publicar un artículo de 2 partes sobre SVD: la primera parte explica la intuición y la segunda parte tiene todos los detalles sangrientos de todos los teoremas, pruebas y datos.

1. Descomposición del valor singular Parte 1: Perspectivas sobre álgebra lineal
2. Descomposición del valor singular Parte 2: teorema, prueba, algoritmo

Answer 10

Hay muy buenas respuestas a la pregunta original en este hilo. Una cosa que noté que no está aquí (al menos explícitamente) es exactamente por qué la SVD es importante.

Como han señalado otros, dada una matriz A, la descomposición dada por la SVD

[matemáticas] A = U \ Sigma V ^ T [/ matemáticas]

se puede truncar a una aproximación [matemática] \ hat {A} [/ matemática] de [matemática] A [/ matemática] dada por

[matemáticas] \ hat {A} = U_ {trunc} \ Sigma_ {trunc} {V_ {trunc}} ^ T [/ math]

donde [math] U_ {trunc} [/ math] y [math] V_ {trunc} [/ math] se han truncado para tener solo, digamos, [math] k [/ math] columnas y [math] \ Sigma_ { trunc} [/ math] tiene [math] k [/ math] columnas y filas.

Cuando se hace esto, la norma de Frobenius del error [matemáticas] \ | A- \ hat {A} \ | _ {F} [/ matemáticas] es la más pequeña posible para todas las opciones de [matemáticas] U_ {trunc} [/ math], [math] \ Sigma_ {trunc} [/ math] y [math] V_ {trunc} [/ math].

Ahora el punto clave: cuanto menor es k, menor es el número de parámetros necesarios en [matemática] U_ {trunc} [/ matemática], [matemática] \ Sigma_ {trunc} [/ matemática] y [matemática] V_ {trunc } [/ math], y cuanto menor sea el número de parámetros para aproximar [math] A [/ math]. Cuanto menor sea el número de parámetros en un modelo, mejor será la generalización, dada la misma métrica de rendimiento. En términos generales (sobre), el SVD es un algoritmo para dar la mejor aproximación de mínimos cuadrados posible a una matriz con rango k. La aproximación de truncar la SVD es la mejor aproximación posible desde el punto de vista de la norma de Frobenius para generalización.

Ahora, la norma de Frobenius es realmente la mejor medida de rendimiento cuando la distribución es gaussiana. Sin embargo, esta situación surge a menudo en la naturaleza debido al teorema del límite central. Como resultado, la SVD truncada es a menudo la primera y mejor opción para aproximar una matriz que tiene una buena generalización.

Answer 11

En mi opinión, la descomposición SVD es una proyección de una matriz dada en un espacio ortogonal.

En cierto sentido, es análogo a las transformaciones de Fourier o wavelet, pero la dimensión de Fourier y wavelet es infinita, mientras que la dimensión de SVD es finita.

La explicación física es cómo la “energía” que consiste en matriz se dispersa en varias dimensiones.

Los valores de coordenadas son los coeficientes de “energía” de la energía en varias dimensiones.

Es por eso que el resultado “La influencia de cualquier turbulencia o impacto en el elemento de la matriz debe ser pequeña en comparación con las características de la matriz”, porque cualquier cambio de impacto único difícilmente puede cambiar el ángulo del “vector” (matriz) en el espacio de alta dimensión, así la proyección no cambiará demasiado.

Answer 12

Imaginemos el ejemplo más simple en dos dimensiones. Se generaliza muy naturalmente a dimensiones superiores.

Supongamos que tenemos dos vectores bidimensionales, x₁ = ( x ₁ , y ₁ ) y x₂ = ( x₂ , y₂ ). Podemos ajustar una elipse con eje mayor, a , y eje menor, b , a estos dos vectores como se muestra en la figura. Pero para facilitarnos las cosas y ahorrar escritura, escribimos las ecuaciones usando álgebra matricial.

Podemos construir una elipse de cualquier tamaño y orientación estirando y girando un círculo unitario.

Sea x ‘= ( x ‘, y ‘) las coordenadas transformadas:

donde R es una matriz de rotación:

y M es una matriz diagonal que contiene los ejes mayor y menor:

Vamos a escribir esto término por término, tanto para el caso general:

donde m ᵢ es la iésima diagonal de la matriz, M , y para el caso de dos dimensiones:

Tenga en cuenta que la rotación es en el sentido de las agujas del reloj, opuesto al sentido habitual porque estamos pasando del sistema de coordenadas no transformado al transformado en lugar de al revés. Para la elipse resultante, el ángulo estará en el sentido habitual en sentido antihorario.

La ecuación para un círculo unitario es la siguiente:

Deseamos ajustar un conjunto de x ‘s, que recopilamos como las filas de una matriz, X :

La ecuación matricial resultante se da:

Esto es solo una reorganización de la ecuación (3). Si consideramos A como una colección de puntos, los valores singulares son los ejes de un elipsoide ajustado de mínimos cuadrados, mientras que V es su orientación. La matriz U es la proyección de cada uno de los puntos en A sobre los ejes.

Puedes aprender más aqui.

Answer 13

Fast svd solo calcula los valores positivos propios. Por lo tanto, son más rápidos. Además, funcionan bien ya que realiza la descomposición en la versión ‘gorda’ o ‘delgada’ de la matriz original.

Answer 14

Una matriz es una función lineal de R ^ m a R ^ n. Dada la bola unitaria en el dominio / espacio de entrada, existe una rotación (transformación ortonormal) en el espacio de entrada r1 y una en el espacio de salida r2 de modo que el espacio de entrada giratorio, aplicando la función y el espacio de salida giratorio, terminamos con un elipsoide alineado con los ejes de salida , cuyos semidiametros son valores singulares. Tenga en cuenta que cualquier matriz mapearía la bola unitaria en un elipsoide, pero las rotaciones permiten la alineación de los ejes y el orden de los semidiametros en el mismo orden de los ejes.

Answer 15

Todas las respuestas aquí se basan en la multiplicación de matrices. Hay una forma más geométrica de interpretar la SVD, que puede atraer más a los matemáticos.

Suponga que tiene una transformación lineal de un espacio de producto interno a otro, que podría ser de diferentes dimensiones (finitas). El SVD dice que puede encontrar una base ortogonal de cada espacio interno del producto, con respecto al cual la matriz de la transformación lineal es diagonal. Entonces, la transformación lineal lleva v1 a un múltiplo de w1, v2 a un múltiplo de w2, y así sucesivamente. (“Diagonal” tuvo que interpretarse adecuadamente cuando las dimensiones son desiguales, pero es exactamente lo que cabría esperar).

Como puede verificar interpretando esto en términos de matrices, es completamente equivalente a la SVD. Creo que aclara en cierta medida la geometría de la SVD, así como la naturaleza de cómo identificar las bases relevantes (o las matrices conjugadas), al menos si encuentra que la unión de una transformación lineal es más natural que la transposición de una matriz Al final, supongo que la única diferencia es si lo que se le da es más naturalmente una transformación lineal o más naturalmente una matriz.

Answer 16

Data Science Repo – Aprendizaje automático, estadísticas, etc.

Echa un vistazo a la teoría SVD de Dan Kalman.

Answer 17

He preparado el video para ayudar

Answer 18

La siguiente es la mejor explicación sobre SVD que pude encontrar: