Específicamente, la descomposición en valores singulares de una matriz compleja es una factorización de la forma donde es una matriz unitaria compleja , es una matriz diagonal rectangular con números reales no negativos en la diagonal, es una matriz unitaria compleja matriz, y es la transpuesta conjugada de . Esta descomposición siempre existe para cualquier matriz compleja. Si es real, entonces se puede garantizar que y sean matrices ortogonales reales; en tales contextos, la SVD a menudo se denota
Las entradas diagonales de están determinadas únicamente por y se conocen como valores singulares de . El número de valores singulares distintos de cero es igual al rango de . Las columnas de y las columnas de se denominan vectores singulares izquierdos y vectores singulares derechos de , respectivamente. Forman dos conjuntos de bases ortonormales y y si se ordenan de modo que los valores singulares con valor cero estén todos en las columnas (o filas) con el número más alto, la descomposición del valor singular se puede escribir como
donde esta el rango de
El SVD no es único, sin embargo siempre es posible elegir la descomposición de modo que los valores singulares estén en orden descendente. En este caso, (pero no y ) está determinado únicamente por
El término a veces se refiere al SVD compacto , una descomposición similar en la que es una diagonal cuadrada de tamaño donde es el rango de y tiene solo valores singulares distintos de cero. En esta variante, es una matriz semiunitaria y es una matriz semiunitaria , tal que
En el caso especial en el que es una matriz cuadrada real , las matrices y pueden elegirse para que sean matrices reales también. En ese caso, "unitario" es lo mismo que " ortogonal ". Luego, interpretando tanto las matrices unitarias como la matriz diagonal, resumida aquí como como una transformación lineal del espacio las matrices y representan rotaciones o reflexión del espacio, mientras que representa el escalamiento de cada coordenada por el factor Así, la descomposición SVD descompone cualquier transformación lineal de en una composición de tres transformaciones geométricas : una rotación o reflexión ( ), seguida de un escalado coordenada por coordenada ( ), seguido de otra rotación o reflexión ( ).
En particular, si tiene un determinante positivo, entonces y pueden elegirse para que sean ambas rotaciones con reflexiones o ambas rotaciones sin reflexiones. [ cita necesaria ] Si el determinante es negativo, exactamente uno de ellos tendrá un reflejo. Si el determinante es cero, cada uno puede elegirse independientemente como de cualquier tipo.
Si la matriz es real pero no cuadrada, es decir, con , se puede interpretar como una transformación lineal de a Entonces y pueden elegirse como rotaciones/reflexiones de y respectivamente; y además de escalar las primeras coordenadas, también extiende el vector con ceros, es decir, elimina las coordenadas finales, para convertir en
Valores singulares como semiejes de una elipse o elipsoide
Como se muestra en la figura, los valores singulares se pueden interpretar como la magnitud de los semiejes de una elipse en 2D. Este concepto se puede generalizar al espacio euclidiano de dimensiones , considerando los valores singulares de cualquier matriz cuadrada como la magnitud del semieje de un elipsoide de dimensiones . De manera similar, los valores singulares de cualquier matriz se pueden ver como la magnitud del semieje de un -elipsoide dimensional en -espacio dimensional , por ejemplo, como una elipse en un plano 2D (inclinado) en un espacio 3D. Los valores singulares codifican la magnitud del semieje, mientras que los vectores singulares codifican la dirección. Consulte a continuación para obtener más detalles.
las columnas deUd.yVson bases ortonormales
Dado que y son unitarios, las columnas de cada uno de ellos forman un conjunto de vectores ortonormales , que pueden considerarse como vectores base . La matriz asigna el vector base al vector unitario estirado Según la definición de una matriz unitaria, lo mismo es cierto para sus transpuestas conjugadas y excepto que se pierde la interpretación geométrica de los valores singulares a medida que se extiende . En resumen, las columnas de y son bases ortonormales . Cuando es una matriz hermitiana semidefinida positiva , y son iguales a la matriz unitaria utilizada para diagonalizar Sin embargo, cuando no es semidefinida positiva y hermitiana pero aún es diagonalizable , su descomposición propia y su descomposición en valores singulares son distintos.
Relación con los cuatro subespacios fundamentales
Las primeras columnas de son una base del espacio de columnas de .
Las últimas columnas de son una base del espacio nulo de .
Las primeras columnas de son una base del espacio de columnas de (el espacio de filas de en el caso real).
Las últimas columnas de son una base del espacio nulo de .
Significado geométrico
Debido a que y son unitarios, sabemos que las columnas de producen una base ortonormal de y las columnas de producen una base ortonormal de (con respecto a los productos escalares estándar en estos espacios).
tiene una descripción particularmente simple con respecto a estas bases ortonormales: tenemos
donde es la -ésima entrada diagonal de y para
El contenido geométrico del teorema SVD se puede resumir de la siguiente manera: para cada aplicación lineal se pueden encontrar bases ortonormales de y tales que asigna el -ésimo vector de base de a un no- múltiplo negativo del -ésimo vector de base de y envía los vectores de base sobrantes a cero. Con respecto a estas bases, el mapa está, por tanto, representado por una matriz diagonal con entradas diagonales reales no negativas.
Para obtener una idea más visual de los valores singulares y la factorización SVD, al menos cuando se trabaja en espacios vectoriales reales, considere la esfera de radio uno en El mapa lineal asigna esta esfera a un elipsoide en distinto de cero los valores singulares son simplemente las longitudes de los semiejes de este elipsoide. Especialmente cuando y todos los valores singulares son distintos y distintos de cero, el SVD del mapa lineal puede analizarse fácilmente como una sucesión de tres movimientos consecutivos: considere el elipsoide y específicamente sus ejes; luego considere las direcciones en enviadas por sobre estos ejes. Estas direcciones resultan ser mutuamente ortogonales. Aplica primero una isometría enviando estas direcciones a los ejes de coordenadas de En un segundo movimiento, aplica un endomorfismo diagonalizado a lo largo de los ejes de coordenadas y estirándolo o encogiéndolo en cada dirección, usando las longitudes de los semiejes de como estiramiento coeficientes. La composición luego envía la unidad-esfera sobre un elipsoide isométrico para Para definir el tercer y último movimiento, aplique una isometría a este elipsoide para obtener Como se puede comprobar fácilmente, la composición coincide con
Ejemplo
Considere la matriz
Una descomposición en valores singulares de esta matriz viene dada por
La matriz de escala es cero fuera de la diagonal (cursiva gris) y un elemento de la diagonal es cero (negrita roja, negrita azul claro en modo oscuro). Además, debido a que las matrices y son unitarias , al multiplicarlas por sus respectivas transpuestas conjugadas se obtienen matrices identidad , como se muestra a continuación. En este caso, debido a que y tienen valores reales, cada una es una matriz ortogonal .
Esta particular descomposición de valores singulares no es única. Elegir tal que
También es una descomposición válida en valores singulares.
SVD y descomposición espectral.
Valores singulares, vectores singulares y su relación con el SVD
Un número real no negativo es un valor singular para si y sólo si existen vectores unitarios de longitud en y en tales que
Los vectores y se llaman vectores singular izquierdo y singular derecho para respectivamente.
En cualquier descomposición de valores singulares
las entradas diagonales de son iguales a los valores singulares de Las primeras columnas de y son, respectivamente, vectores singulares izquierdo y derecho para los valores singulares correspondientes. En consecuencia, el teorema anterior implica que:
Una matriz tiene como máximo valores singulares distintos.
Siempre es posible encontrar una base unitaria para con un subconjunto de vectores de base que abarquen los vectores singulares izquierdos de cada valor singular de
Siempre es posible encontrar una base unitaria para con un subconjunto de vectores de base que abarquen los vectores singulares derechos de cada valor singular de
Un valor singular para el cual podemos encontrar dos vectores singulares izquierdo (o derecho) que sean linealmente independientes se llama degenerado . Si y son dos vectores singulares por la izquierda que corresponden al valor singular σ, entonces cualquier combinación lineal normalizada de los dos vectores también es un vector singular por la izquierda correspondiente al valor singular σ. Una afirmación similar es cierta para los vectores singulares derechos. El número de vectores singulares izquierdo y derecho independientes coincide, y estos vectores singulares aparecen en las mismas columnas de y correspondientes a elementos diagonales de todos con el mismo valor
Como excepción, los vectores singulares izquierdo y derecho de valor singular 0 comprenden todos los vectores unitarios en cokernel y kernel , respectivamente, de que, según el teorema de rango-nulidad, no pueden tener la misma dimensión si Incluso si todos los valores singulares son distintos de cero, si entonces el cokernel no es trivial, en cuyo caso se rellena con vectores ortogonales del cokernel. Por el contrario, si entonces se rellena con vectores ortogonales del núcleo. Sin embargo, si el valor singular de existe, las columnas adicionales de o ya aparecen como vectores singulares izquierdo o derecho.
Los valores singulares no degenerados siempre tienen vectores singulares izquierdo y derecho únicos, hasta la multiplicación por un factor de fase unitaria (para el caso real hasta un signo). En consecuencia, si todos los valores singulares de una matriz cuadrada son no degenerados y distintos de cero, entonces su descomposición en valores singulares es única, hasta la multiplicación de una columna de por un factor de fase unitaria y la multiplicación simultánea del correspondiente columna de por el mismo factor de fase unitaria. En general, el SVD es único hasta transformaciones unitarias arbitrarias aplicadas uniformemente a los vectores columna de y que abarcan los subespacios de cada valor singular, y hasta transformaciones unitarias arbitrarias en vectores de y que abarcan el núcleo y cokernel, respectivamente, de
Relación con la descomposición de valores propios
La descomposición en valores singulares es muy general en el sentido de que se puede aplicar a cualquier matriz , mientras que la descomposición en valores propios solo se puede aplicar a matrices cuadradas diagonalizables . Sin embargo, las dos descomposiciones están relacionadas.
Si tiene SVD se cumplen las dos relaciones siguientes:
Los lados derechos de estas relaciones describen las descomposiciones de valores propios de los lados izquierdos. Como consecuencia:
Las columnas de (denominadas vectores singulares derechos) son vectores propios de
Las columnas de (denominadas vectores singulares izquierdos) son vectores propios de
Los elementos distintos de cero de (valores singulares distintos de cero) son las raíces cuadradas de los valores propios distintos de cero de o
En el caso especial de ser una matriz normal y, por tanto , también cuadrada, el teorema espectral garantiza que se puede diagonalizar unitariamente utilizando una base de vectores propios y , por lo tanto , descomponerse como para alguna matriz unitaria y matriz diagonal . con elementos complejos a lo largo de la diagonal. Cuando es semidefinido positivo , serán números reales no negativos, de modo que la descomposición también es una descomposición en valor singular. De lo contrario, se puede reformular como un SVD moviendo la fase de cada a su correspondiente o . La conexión natural del SVD con matrices no normales es a través del teorema de descomposición polar : donde es semidefinida positiva y normal, y es unitaria.
Por lo tanto, a excepción de las matrices semidefinidas positivas, la descomposición de valores propios y la SVD de , aunque están relacionadas, difieren: la descomposición de valores propios es donde no es necesariamente unitaria y no es necesariamente semidefinida positiva, mientras que la SVD es donde es diagonal y semidefinida positiva, y y son matrices unitarias que no están necesariamente relacionadas excepto a través de la matriz Si bien solo las matrices cuadradas no defectuosas tienen una descomposición de valores propios, cualquier matriz tiene una SVD.
Aplicaciones de la SVD
Pseudoinverso
La descomposición en valores singulares se puede utilizar para calcular la pseudoinversa de una matriz. La pseudoinversa de la matriz con descomposición en valores singulares es,
donde está el pseudoinverso de , que se forma reemplazando cada entrada diagonal distinta de cero por su recíproco y transponiendo la matriz resultante. La pseudoinversa es una forma de resolver problemas de mínimos cuadrados lineales .
Resolver ecuaciones lineales homogéneas.
Un conjunto de ecuaciones lineales homogéneas se puede escribir como para una matriz y un vector . Una situación típica es que se conoce y se debe determinar un valor distinto de cero que satisfaga la ecuación. Tal pertenece al espacio nulo de y a veces se le llama vector nulo (derecho) de . El vector se puede caracterizar como un vector singular derecho correspondiente a un valor singular de que es cero. Esta observación significa que si es una matriz cuadrada y no tiene un valor singular evanescente, la ecuación no tiene un valor distinto de cero como solución. También significa que si hay varios valores singulares que desaparecen, cualquier combinación lineal de los vectores singulares correctos correspondientes es una solución válida. De manera análoga a la definición de un vector nulo (derecho), un distinto de cero que satisface con que denota la transpuesta conjugada de se llama vector nulo izquierdo de
Minimización de mínimos cuadrados totales
Un problema de mínimos cuadrados totales busca el vector que minimiza la norma 2 de un vector bajo la restricción. La solución resulta ser el vector singular derecho de correspondiente al valor singular más pequeño.
Rango, espacio nulo y rango
Otra aplicación del SVD es que proporciona una representación explícita del rango y el espacio nulo de una matriz Los vectores singulares derechos correspondientes a valores singulares evanescentes de abarcan el espacio nulo de y los vectores singulares izquierdos correspondientes a los valores singulares distintos de cero de abarcan el rango de Por ejemplo, en el ejemplo anterior, el espacio nulo está abarcado por la última fila de y el rango está abarcado por las primeras tres columnas de
Como consecuencia, el rango de es igual al número de valores singulares distintos de cero, que es el mismo que el número de elementos diagonales distintos de cero en . En álgebra lineal numérica, los valores singulares se pueden utilizar para determinar el rango efectivo de una matriz, ya que el error de redondeo puede conducir a valores singulares pequeños pero distintos de cero en una matriz con rango deficiente. Se supone que los valores singulares más allá de una brecha significativa son numéricamente equivalentes a cero.
Aproximación matricial de bajo rango
Algunas aplicaciones prácticas necesitan resolver el problema de aproximar una matriz con otra matriz , llamada truncada, que tiene un rango específico . En el caso de que la aproximación se base en minimizar la norma de Frobenius de la diferencia entre y bajo la restricción de que resulta que la solución está dada por el SVD de es decir
donde es la misma matriz excepto que contiene solo los valores singulares más grandes (los otros valores singulares se reemplazan por cero). Esto se conoce como teorema de Eckart-Young , como lo demostraron esos dos autores en 1936 (aunque más tarde se descubrió que lo conocían autores anteriores; véase Stewart 1993).
Modelos separables
Se puede considerar que el SVD descompone una matriz en una suma ordenada y ponderada de matrices separables. Por separable, queremos decir que una matriz se puede escribir como un producto externo de dos vectores o, en coordenadas, Específicamente, la matriz se puede descomponer como,
Aquí y son las -ésimas columnas de las matrices SVD correspondientes, son los valores singulares ordenados y cada es separable. El SVD se puede utilizar para encontrar la descomposición de un filtro de procesamiento de imágenes en filtros horizontales y verticales separables. Tenga en cuenta que el número de distinto de cero es exactamente el rango de la matriz. [ cita necesaria ] Los modelos separables a menudo surgen en sistemas biológicos, y la factorización SVD es útil para analizar dichos sistemas. Por ejemplo, los campos receptivos de algunas células simples del área visual V1 pueden describirse bien [1] mediante un filtro de Gabor en el dominio espacial multiplicado por una función de modulación en el dominio del tiempo. Por lo tanto, dado un filtro lineal evaluado mediante, por ejemplo, correlación inversa , se pueden reorganizar las dos dimensiones espaciales en una dimensión, produciendo así un filtro bidimensional (espacio, tiempo) que se puede descomponer mediante SVD. La primera columna de en la factorización SVD es entonces un Gabor, mientras que la primera columna de representa la modulación del tiempo (o viceversa). Entonces se puede definir un índice de separabilidad
que es la fracción de la potencia en la matriz M que corresponde a la primera matriz separable en la descomposición. [2]
Matriz ortogonal más cercana
Es posible utilizar el SVD de una matriz cuadrada para determinar la matriz ortogonal más cercana a La cercanía del ajuste se mide mediante la norma de Frobenius de La solución es el producto [3] Esto intuitivamente hace tiene sentido porque una matriz ortogonal tendría la descomposición donde es la matriz identidad, de modo que si entonces el producto equivale a reemplazar los valores singulares por unos. De manera equivalente, la solución es la matriz unitaria de la descomposición polar en cualquier orden de estiramiento y rotación, como se describió anteriormente.
Un problema similar, con aplicaciones interesantes en el análisis de formas , es el problema de Procrustes ortogonal , que consiste en encontrar una matriz ortogonal que se corresponda más estrechamente con Específicamente,
donde denota la norma de Frobenius.
Este problema equivale a encontrar la matriz ortogonal más cercana a una matriz dada .
El algoritmo de Kabsch
El algoritmo de Kabsch (llamado problema de Wahba en otros campos) utiliza SVD para calcular la rotación óptima (con respecto a la minimización de mínimos cuadrados) que alineará un conjunto de puntos con un conjunto de puntos correspondiente. Se utiliza, entre otras aplicaciones, para comparar las estructuras de las moléculas.
En el cálculo numérico general que involucra sistemas lineales o linealizados, existe una constante universal que caracteriza la regularidad o singularidad de un problema, que es el "número de condición" del sistema . A menudo controla la tasa de error o la tasa de convergencia de un esquema computacional determinado en dichos sistemas. [10] [11]
La SVD también desempeña un papel crucial en el campo de la información cuántica , en una forma a menudo denominada descomposición de Schmidt . A través de él, los estados de dos sistemas cuánticos se descomponen naturalmente, proporcionando una condición necesaria y suficiente para que se entrelacen : si el rango de la matriz es mayor que uno.
Una aplicación de SVD a matrices bastante grandes es la predicción numérica del tiempo , donde los métodos de Lanczos se utilizan para estimar las pocas perturbaciones de crecimiento más rápido lineal en la predicción numérica central del tiempo durante un período de tiempo inicial determinado; es decir, los vectores singulares correspondientes a los valores singulares más grandes del propagador linealizado para el clima global durante ese intervalo de tiempo. Los vectores singulares de salida en este caso son sistemas meteorológicos completos. Luego, estas perturbaciones se analizan a través del modelo no lineal completo para generar un pronóstico conjunto , que da una idea de parte de la incertidumbre que debería permitirse en torno a la predicción central actual.
SVD también se ha aplicado al modelado de orden reducido. El objetivo del modelado de orden reducido es reducir el número de grados de libertad en un sistema complejo que se va a modelar. SVD se combinó con funciones de base radial para interpolar soluciones a problemas de flujo inestable tridimensionales. [12]
Curiosamente, SVD se ha utilizado para mejorar el modelado de formas de ondas gravitacionales mediante el interferómetro de ondas gravitacionales aLIGO. [13] SVD puede ayudar a aumentar la precisión y la velocidad de la generación de formas de onda para respaldar las búsquedas de ondas gravitacionales y actualizar dos modelos de formas de onda diferentes.
La descomposición de valores singulares se utiliza en los sistemas de recomendación para predecir las calificaciones de los artículos de las personas. [14] Se han desarrollado algoritmos distribuidos con el fin de calcular el SVD en grupos de máquinas de productos básicos. [15]
En astrodinámica , el SVD y sus variantes se utilizan como una opción para determinar direcciones de maniobra adecuadas para el diseño de trayectorias de transferencia [18] y el mantenimiento de estaciones orbitales . [19]
Prueba de existencia
Un valor propio de una matriz se caracteriza por la relación algebraica Cuando es hermitiano , también está disponible una caracterización variacional. Sea una matriz simétrica real . Definir
para algún número real El símbolo nabla, , es el operador del (diferenciación con respecto a ). Usando la simetría de obtenemos
Por lo tanto entonces es un vector propio de longitud unitaria de Para cada vector propio de longitud unitaria de su valor propio es entonces es el valor propio más grande de El mismo cálculo realizado en el complemento ortogonal de da el siguiente valor propio más grande y así sucesivamente. El complejo caso hermitiano es similar; allí hay una función de valor real de variables reales.
Los valores singulares son similares en que pueden describirse algebraicamente o a partir de principios variacionales. Aunque, a diferencia del caso de valores propios, ya no se requiere la hermiticidad o simetría de .
Esta sección presenta estos dos argumentos a favor de la existencia de la descomposición en valores singulares.
Basado en el teorema espectral
Sea una matriz compleja. Dado que es semidefinida positiva y hermitiana, según el teorema espectral , existe una matriz unitaria tal que
donde es diagonal y definida positiva, de dimensión , con el número de valores propios distintos de cero de (que se puede demostrar que verifica ). Tenga en cuenta que aquí, por definición, se trata de una matriz cuya -ésima columna es el -ésimo vector propio de , correspondiente al valor propio . Además, la -ésima columna de , para , es un vector propio de con valor propio . Esto se puede expresar escribiendo como , donde las columnas de y por lo tanto contienen los vectores propios de correspondientes a valores propios distintos de cero y cero, respectivamente. Usando esta reescritura de , la ecuación se convierte en:
Esto implica que
Además, la segunda ecuación implica . [20] Finalmente, la unicidad de se traduce, en términos de y , en las siguientes condiciones:
donde los subíndices de las matrices identidad se utilizan para señalar que son de diferentes dimensiones.
Definamos ahora
Entonces,
ya que esto también puede verse como una consecuencia inmediata del hecho de que . Esto es equivalente a la observación de que si es el conjunto de vectores propios de correspondiente a valores propios que no desaparecen , entonces es un conjunto de vectores ortogonales y es un conjunto (generalmente no completo) de vectores ortonormales . Esto coincide con el formalismo matricial utilizado anteriormente que denota con la matriz cuyas columnas son , con la matriz cuyas columnas son los vectores propios de con valor propio que desaparece y la matriz cuyas columnas son los vectores .
Vemos que este es casi el resultado deseado, excepto que y en general no son unitarios, ya que es posible que no sean cuadrados. Sin embargo, sí sabemos que el número de filas de no es menor que el número de columnas, ya que las dimensiones de no son mayores que y . Además, desde
las columnas son ortonormales y se pueden extender a una base ortonormal. Esto significa que podemos elegir uno que sea unitario.
Para ya tenemos para hacerlo unitario. Ahora, define
donde se agregan o eliminan filas de cero adicionales para que el número de filas de cero sea igual al número de columnas de y, por lo tanto, las dimensiones generales de igual a . Entonces
cual es el resultado deseado:
Observe que el argumento podría comenzar diagonalizando en lugar de (esto muestra directamente que y tienen los mismos valores propios distintos de cero).
Basado en caracterización variacional.
Los valores singulares también se pueden caracterizar como los máximos de considerados como una función de y sobre subespacios particulares. Los vectores singulares son los valores de y donde se alcanzan estos máximos.
Sea una matriz con entradas reales. Sea la esfera unitaria en , y defina
Considere la función restringida a Dado que tanto como son conjuntos compactos , su producto también es compacto. Además, dado que es continuo, alcanza un valor máximo para al menos un par de vectores en y en Este valor máximo se denota y los vectores correspondientes se denotan y Dado que es el valor más grande de y no debe ser negativo. Si fuera negativo, cambiar el signo de o lo haría positivo y, por lo tanto, más grande.
Declaración. y son vectores singulares izquierdo y derecho de con el valor singular correspondiente
Prueba. De manera similar al caso de los valores propios, se supone que los dos vectores satisfacen la ecuación multiplicadora de Lagrange:
Después de un poco de álgebra, esto se convierte en
Multiplicando la primera ecuación de la izquierda por y la segunda ecuación de la izquierda por y teniendo en cuenta da
Al conectar esto al par de ecuaciones anteriores, tenemos
Esto prueba la afirmación.
Se pueden encontrar más vectores singulares y valores singulares maximizando sobre normalizado y que son ortogonales a y respectivamente.
El paso de real a complejo es similar al caso de valores propios.
Calculando la SVD
Algoritmo de Jacobi unilateral
El algoritmo de Jacobi unilateral es un algoritmo iterativo, [21]
donde una matriz se transforma iterativamente en una matriz con columnas ortogonales. La iteración elemental se da como una rotación de Jacobi ,
donde el ángulo de la matriz de rotación de Jacobi se elige de manera que después de la rotación las columnas con números se vuelvan ortogonales. Los índices se barren cíclicamente, donde es el número de columnas.
Una vez que el algoritmo ha convergido, la descomposición del valor singular se recupera de la siguiente manera: la matriz es la acumulación de matrices de rotación de Jacobi, la matriz se obtiene normalizando las columnas de la matriz transformada y los valores singulares se dan como las normas de las columnas. de la matriz transformada .
Algoritmo de Jacobi de dos caras
El algoritmo SVD de Jacobi de dos caras, una generalización del algoritmo de valores propios de Jacobi , es un algoritmo iterativo en el que una matriz cuadrada se transforma iterativamente en una matriz diagonal. Si la matriz no es cuadrada, primero se realiza la descomposición QR y luego se aplica el algoritmo a la matriz. La iteración elemental pone a cero un par de elementos fuera de la diagonal aplicando primero una rotación de Givens para simetrizar el par de elementos y luego aplicando una transformación de Jacobi para ponerlos a cero.
donde está la matriz de rotación de Givens con el ángulo elegido de manera que el par dado de elementos fuera de la diagonal se vuelvan iguales después de la rotación, y dónde está la matriz de transformación de Jacobi que pone a cero estos elementos fuera de la diagonal. Las iteraciones se desarrollan exactamente como en el algoritmo de valores propios de Jacobi: mediante barridos cíclicos sobre todos los elementos fuera de la diagonal.
Una vez que el algoritmo ha convergido, la matriz diagonal resultante contiene los valores singulares. Las matrices y se acumulan de la siguiente manera: , .
Enfoque numérico
La descomposición del valor singular se puede calcular utilizando las siguientes observaciones:
Los vectores singulares derechos de son un conjunto de vectores propios ortonormales de .
Los valores singulares distintos de cero de (que se encuentran en las entradas diagonales de ) son las raíces cuadradas de los valores propios distintos de cero de y .
El SVD de una matriz normalmente se calcula mediante un procedimiento de dos pasos. En el primer paso, la matriz se reduce a una matriz bidiagonal . Esto requiere orden operaciones de punto flotante (flop), asumiendo que El segundo paso es calcular el SVD de la matriz bidiagonal. Este paso sólo se puede realizar con un método iterativo (como con los algoritmos de valores propios ). Sin embargo, en la práctica basta con calcular el SVD con cierta precisión, como la máquina épsilon . Si esta precisión se considera constante, entonces el segundo paso requiere iteraciones, cada una de las cuales cuesta fracasos. Por lo tanto, el primer paso es más caro y el costo total es de fracasos (Trefethen y Bau III 1997, Conferencia 31).
El primer paso se puede realizar utilizando reflexiones de Householder por un costo de flops, suponiendo que solo se necesitan los valores singulares y no los vectores singulares. Si es mucho mayor que entonces es ventajoso reducir primero la matriz a una matriz triangular con la descomposición QR y luego usar reflexiones de Householder para reducir aún más la matriz a forma bidiagonal; el costo combinado es de fracasos (Trefethen y Bau III 1997, Conferencia 31).
El segundo paso se puede realizar mediante una variante del algoritmo QR para el cálculo de valores propios, que fue descrito por primera vez por Golub y Kahan (1965). La subrutina LAPACK DBDSQR [22] implementa este método iterativo, con algunas modificaciones para cubrir el caso donde los valores singulares son muy pequeños (Demmel & Kahan 1990). Junto con un primer paso que utiliza reflexiones de Householder y, si corresponde, descomposición QR, esto forma la rutina DGESVD [23] para el cálculo de la descomposición del valor singular.
El mismo algoritmo se implementa en la Biblioteca Científica GNU (GSL). El GSL también ofrece un método alternativo que utiliza una ortogonalización de Jacobi unilateral en el paso 2 (GSL Team 2007). Este método calcula el SVD de la matriz bidiagonal resolviendo una secuencia de problemas de SVD, similar a cómo el algoritmo de valores propios de Jacobi resuelve una secuencia de métodos de valores propios (Golub & Van Loan 1996, §8.6.3). Otro método más para el paso 2 utiliza la idea de algoritmos de valores propios de divide y vencerás (Trefethen y Bau III 1997, Conferencia 31).
Existe una forma alternativa que no utiliza explícitamente la descomposición de valores propios. [24] Por lo general, el problema de valores singulares de una matriz se convierte en un problema de valores propios simétrico equivalente como o
Los enfoques que utilizan descomposiciones de valores propios se basan en el algoritmo QR , que está bien desarrollado para ser estable y rápido. Tenga en cuenta que los valores singulares son reales y que los vectores singulares derecho e izquierdo no son necesarios para formar transformaciones de similitud. Se puede alternar iterativamente entre la descomposición QR y la descomposición LQ para encontrar las matrices hermitianas diagonales reales . La descomposición QR da y la descomposición LQ de da Por lo tanto, en cada iteración, actualizamos y repetimos las ortogonalizaciones. Finalmente, [ se necesita aclaración ] esta iteración entre la descomposición QR y la descomposición LQ produce matrices singulares unitarias izquierda y derecha. Este enfoque no puede acelerarse fácilmente, como puede hacerlo el algoritmo QR con cambios espectrales o deflación. Esto se debe a que el método de desplazamiento no se define fácilmente sin utilizar transformaciones de similitud. Sin embargo, este enfoque iterativo es muy sencillo de implementar, por lo que es una buena opción cuando la velocidad no importa. Este método también proporciona información sobre cómo las transformaciones puramente ortogonales/unitarias pueden obtener la SVD.
Resultado analítico del 2 × 2 SVD
Los valores singulares de una matriz se pueden encontrar analíticamente. Sea la matriz
donde están los números complejos que parametrizan la matriz, es la matriz identidad, y denotan las matrices de Pauli . Entonces sus dos valores singulares están dados por
SVD reducidas
En aplicaciones es bastante inusual que se requiera el SVD completo, incluida una descomposición unitaria completa del espacio nulo de la matriz. En cambio, suele ser suficiente (además de más rápido y más económico para el almacenamiento) calcular una versión reducida del SVD. Para una matriz de rango se puede distinguir lo siguiente :
SVD delgada
La SVD delgada, o de tamaño económico, de una matriz viene dada por [25]
donde las matrices y contienen solo las primeras columnas de y y contienen solo los primeros valores singulares de La matriz es así diagonal, diagonal, diagonal,, diagonal,, diagonal,, diagonal, diagonal, y es
El SVD delgado utiliza significativamente menos espacio y tiempo de cálculo si La primera etapa en su cálculo suele ser una descomposición QR de , lo que puede hacer que el cálculo sea significativamente más rápido en este caso.
SVD compacto
El SVD compacto de una matriz viene dado por
Solo se calculan los vectores de columna de y los vectores de fila de correspondientes a los valores singulares distintos de cero . Los vectores restantes de y no se calculan. Esto es más rápido y económico que el SVD delgado si La matriz es es diagonal y es
SVD truncada
En muchas aplicaciones, el número de valores singulares distintos de cero es grande, lo que hace que incluso el SVD compacto sea poco práctico de calcular. En tales casos, es posible que sea necesario truncar los valores singulares más pequeños para calcular solo valores singulares distintos de cero. La SVD truncada ya no es una descomposición exacta de la matriz original sino que proporciona la aproximación óptima de una matriz de rango bajo mediante cualquier matriz de rango fijo
donde la matriz es es diagonal y es Solo se calculan los vectores de columna de y los vectores de fila de correspondientes a los valores singulares más grandes . Esto puede ser mucho más rápido y económico que el SVD compacto si , pero requiere un conjunto de herramientas de solucionador numérico completamente diferente.
En aplicaciones que requieren una aproximación a la inversa de Moore-Penrose de la matriz son de interés los valores singulares más pequeños de , que son más difíciles de calcular en comparación con los más grandes.
La suma de los valores singulares más grandes de es una norma matricial , la norma Ky Fan de [27]
La primera de las normas de Ky Fan, la norma Ky Fan 1, es la misma que la norma del operador de como operador lineal con respecto a las normas euclidianas de y En otras palabras, la norma Ky Fan 1- norma es la norma del operador inducida por el producto interno euclidiano estándar. Por esta razón, también se le llama operador 2-norma. Se puede verificar fácilmente la relación entre la norma Ky Fan 1 y los valores singulares. Es cierto en general, para un operador acotado en espacios de Hilbert (posiblemente de dimensión infinita)
Pero, en el caso de la matriz, es una matriz normal , también lo es el valor propio más grande de , es decir, el valor singular más grande de
La última de las normas de Ky Fan, la suma de todos los valores singulares, es la norma de traza (también conocida como 'norma nuclear'), definida por (los valores propios de son los cuadrados de los valores singulares).
Norma de Hilbert-Schmidt
Los valores singulares están relacionados con otra norma sobre el espacio de operadores. Considere el producto interno de Hilbert-Schmidt en las matrices , definido por
Entonces la norma inducida es
Dado que la traza es invariante bajo equivalencia unitaria, esto muestra
donde son los valores singulares de Esto se llama norma de Frobenius , norma Schatten 2 o norma Hilbert-Schmidt de El cálculo directo muestra que la norma de Frobenius de coincide con:
Además, la norma de Frobenius y la norma de traza (la norma nuclear) son casos especiales de la norma de Schatten .
Variaciones y generalizaciones.
SVD invariante de escala
Los valores singulares de una matriz están definidos de forma única y son invariantes con respecto a las transformaciones unitarias izquierda y/o derecha de En otras palabras, los valores singulares de para matrices unitarias y son iguales al singular valores de Esta es una propiedad importante para aplicaciones en las que es necesario preservar las distancias euclidianas y la invariancia con respecto a las rotaciones.
El SVD invariante de escala, o SI-SVD, [28] es análogo al SVD convencional excepto que sus valores singulares determinados de forma única son invariantes con respecto a las transformaciones diagonales de En otras palabras, los valores singulares de para invertibles las matrices diagonales y son iguales a los valores singulares de . Esta es una propiedad importante para aplicaciones en las que se necesita invariancia en la elección de unidades de variables (por ejemplo, unidades métricas versus imperiales).
Operadores acotados en espacios de Hilbert
La factorización se puede extender a un operador acotado en un espacio de Hilbert separable Es decir, para cualquier operador acotado existe una isometría parcial un unitario un espacio de medida y un medible no negativo tal que
Esto se puede demostrar imitando el argumento algebraico lineal para el caso matricial anterior. es la única raíz cuadrada positiva de dada por el cálculo funcional de Borel para operadores autoadjuntos . La razón por la que no necesita ser unitario es que, a diferencia del caso de dimensión finita, dada una isometría con núcleo no trivial, no se puede encontrar un adecuado tal que
es un operador unitario.
En cuanto a las matrices, la factorización de valores singulares equivale a la descomposición polar de los operadores: simplemente podemos escribir
y observe que sigue siendo una isometría parcial mientras que es positiva.
Valores singulares y operadores compactos.
La noción de valores singulares y vectores singulares izquierdo/derecho se puede extender al operador compacto en el espacio de Hilbert, ya que tienen un espectro discreto. Si es compacto, todo distinto de cero en su espectro es un valor propio. Además, un operador autoadjunto compacto puede diagonalizarse mediante sus vectores propios. Si es compacto, también lo es . Aplicando el resultado de la diagonalización, la imagen unitaria de su raíz cuadrada positiva tiene un conjunto de vectores propios ortonormales correspondientes a valores propios estrictamente positivos . Para cualquier en
donde la serie converge en la topología normal en Observe cómo esto se parece a la expresión del caso de dimensión finita. se denominan valores singulares de (resp. ) pueden considerarse los vectores singular izquierdo (resp. singular derecho) de
Los operadores compactos en un espacio de Hilbert son el cierre de operadores de rango finito en la topología de operador uniforme. La expresión de la serie anterior da una representación explícita de este tipo. Una consecuencia inmediata de esto es:
Teorema. es compacto si y sólo si es compacto.
Historia
La descomposición del valor singular fue desarrollada originalmente por geómetras diferenciales , que deseaban determinar si una forma bilineal real podía igualarse a otra mediante transformaciones ortogonales independientes de los dos espacios en los que actúa. Eugenio Beltrami y Camille Jordan descubrieron de forma independiente, en 1873 y 1874 respectivamente, que los valores singulares de las formas bilineales, representados como una matriz, forman un conjunto completo de invariantes para formas bilineales bajo sustituciones ortogonales. James Joseph Sylvester también llegó a la descomposición de valores singulares para matrices cuadradas reales en 1889, aparentemente independientemente de Beltrami y Jordan. Sylvester llamó a los valores singulares los multiplicadores canónicos de la matriz El cuarto matemático en descubrir la descomposición de valores singulares de forma independiente es Autonne en 1915, quien llegó a ella mediante la descomposición polar . La primera prueba de la descomposición en valores singulares para matrices rectangulares y complejas parece ser la de Carl Eckart y Gale J. Young en 1936; [29] lo vieron como una generalización de la transformación del eje principal para matrices hermitianas .
En 1907, Erhard Schmidt definió un análogo de valores singulares para operadores integrales (que son compactos, bajo algunos supuestos técnicos débiles); parece que desconocía el trabajo paralelo sobre valores singulares de matrices finitas. Esta teoría fue desarrollada aún más por Émile Picard en 1910, quien es el primero en llamar a los números valores singulares (o en francés, valeurs singulières ).
^ DeAngelis, GC; Ohzawa, I.; Freeman, RD (octubre de 1995). "Dinámica del campo receptivo en las vías visuales centrales". Tendencias Neurociencias . 18 (10): 451–8. doi :10.1016/0166-2236(95)94496-R. PMID 8545912. S2CID 12827601.
^ Depireux, DA; Simón, JZ; Klein, DJ; Shamma, SA (marzo de 2001). "Caracterización del campo de respuesta espectro-temporal con ondas dinámicas en la corteza auditiva primaria del hurón". J. Neurofisiol . 85 (3): 1220–34. doi :10.1152/junio.2001.85.3.1220. PMID 11247991.
^ La descomposición de valores singulares en ortogonalización simétrica (Lowdin) y compresión de datos
^ Sahidullah, Maryland; Kinnunen, Tomi (marzo de 2016). "Características de variabilidad espectral local para la verificación de locutores". Procesamiento de señales digitales . 50 : 1–11. doi :10.1016/j.dsp.2015.10.011.
^ Mademlis, Ioannis; Tefas, Anastasio; Pitas, Ioannis (2018). "Prominencia de fotogramas de vídeo regularizados basados en SVD para resumen de vídeos de actividades no supervisadas". Conferencia internacional IEEE 2018 sobre acústica, habla y procesamiento de señales (ICASSP). IEEE. págs. 2691–2695. doi :10.1109/ICASSP.2018.8462274. ISBN978-1-5386-4658-8. S2CID 52286352 . Consultado el 19 de enero de 2023 .
^ O. Alter, PO Brown y D. Botstein (septiembre de 2000). "Descomposición de valores singulares para el modelado y procesamiento de datos de expresión de todo el genoma". PNAS . 97 (18): 10101–10106. Código bibliográfico : 2000PNAS...9710101A. doi : 10.1073/pnas.97.18.10101 . PMC 27718 . PMID 10963673.
^ O. Alterar; GH Golub (noviembre de 2004). "El análisis integrativo de datos a escala del genoma mediante el uso de proyección pseudoinversa predice una nueva correlación entre la replicación del ADN y la transcripción del ARN". PNAS . 101 (47): 16577–16582. Código bibliográfico : 2004PNAS..10116577A. doi : 10.1073/pnas.0406767101 . PMC 534520 . PMID 15545604.
^ O. Alterar; GH Golub (agosto de 2006). "La descomposición de valores singulares de la distribución de longitudes de ARNm a escala del genoma revela asimetría en la ampliación de la banda de electroforesis en gel de ARN". PNAS . 103 (32): 11828–11833. Código bibliográfico : 2006PNAS..10311828A. doi : 10.1073/pnas.0604756103 . PMC 1524674 . PMID 16877539.
^ Bertagnolli, Nuevo México; Drake, JA; Tennessee, JM; Alter, O. (noviembre de 2013). "SVD identifica funciones de distribución de longitud de transcripción a partir de datos de microarrays de ADN y revela fuerzas evolutivas que afectan globalmente el metabolismo de GBM". MÁS UNO . 8 (11): e78913. Código Bib : 2013PLoSO...878913B. doi : 10.1371/journal.pone.0078913 . PMC 3839928 . PMID 24282503. Resaltar.
^ Edelman, Alan (1992). "Sobre la distribución de un número de condición escalado" (PDF) . Matemáticas. comp . 58 (197): 185-190. Código Bib : 1992MaCom..58..185E. doi : 10.1090/S0025-5718-1992-1106966-2 .
^ Shen, Jianhong (Jackie) (2001). "Sobre los valores singulares de las matrices aleatorias gaussianas". Álg. lineal. Aplica . 326 (1–3): 1–14. doi : 10.1016/S0024-3795(00)00322-0 .
^ Walton, S.; Hassan, O.; Morgan, K. (2013). "Modelado de orden reducido para flujo de fluido inestable utilizando descomposición ortogonal adecuada y funciones de base radial". Modelado Matemático Aplicado . 37 (20–21): 8930–8945. doi : 10.1016/j.apm.2013.04.025 .
^ Setyawati, Y.; Ohme, F.; Khan, S. (2019). "Mejora del modelo de forma de onda gravitacional mediante calibración dinámica". Revisión física D. 99 (2): 024010. arXiv : 1810.07060 . Código Bib : 2019PhRvD..99b4010S. doi : 10.1103/PhysRevD.99.024010. S2CID 118935941.
^ Hadi Fanaee Tork; João Gama (septiembre de 2014). "Método del espacio propio para la detección de puntos críticos espaciotemporales". Sistemas expertos . 32 (3): 454–464. arXiv : 1406.3506 . Código Bib : 2014arXiv1406.3506F. doi :10.1111/exsy.12088. S2CID 15476557.
^ Hadi Fanaee Tork; João Gama (mayo de 2015). "EigenEvent: un algoritmo para la detección de eventos a partir de flujos de datos complejos en vigilancia sindrómica". Análisis inteligente de datos . 19 (3): 597–616. arXiv : 1406.3496 . doi :10.3233/IDA-150734. S2CID 17966555.
^ Muralidharan, Vivek; Howell, Kathleen (2023). "Direcciones de estiramiento en el espacio cislunar: Aplicaciones para diseño de salidas y transferencias". Astrodinámica . 7 (2): 153–178. Código Bib : 2023AsDyn...7..153M. doi :10.1007/s42064-022-0147-z. S2CID 252637213.
^ Muralidharan, Vivek; Howell, Kathleen (2022). "Aprovechando las direcciones de estiramiento para el mantenimiento de la posición en órbitas de halo Tierra-Luna". Avances en la investigación espacial . 69 (1): 620–646. Código Bib : 2022AdSpR..69..620M. doi :10.1016/j.asr.2021.10.028. S2CID 239490016.
^ Para ver esto, sólo tenemos que notarlo y recordarlo .
^ Rijk, PPM de (1989). "Un algoritmo de Jacobi unilateral para calcular la descomposición del valor singular en una computadora vectorial". SIAM J. Ciencias. Estadística. Computación . 10 : 359.
^ Demmel, James (2000). "Descomposiciones". Plantillas para la solución de problemas algebraicos de valores propios. Por Bai, Zhaojun; Demmel, James; Dongarra, Jack J.; Ruhe, Axel; van der Vorst, Henk A. Sociedad de Matemáticas Industriales y Aplicadas. doi :10.1137/1.9780898719581. ISBN978-0-89871-471-5.
^ Chicco, D; Masseroli, M (2015). "Paquete de software para búsqueda de similitudes y predicción de anotaciones de genes y proteínas". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 12 (4): 837–843. doi :10.1109/TCBB.2014.2382127. hdl : 11311/959408 . PMID 26357324. S2CID 14714823.
^ Fan, Kentucky (1951). "Propiedades máximas y desigualdades para los valores propios de operadores completamente continuos". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 37 (11): 760–766. Código bibliográfico : 1951PNAS...37..760F. doi : 10.1073/pnas.37.11.760 . PMC 1063464 . PMID 16578416.
^ Uhlmann, Jeffrey (2018), Una matriz inversa generalizada que es consistente con respecto a las transformaciones diagonales (PDF) , Revista SIAM sobre análisis matricial, vol. 239, págs. 781–800, archivado desde el original (PDF) el 17 de junio de 2019
^ Eckart, C .; Joven, G. (1936). "La aproximación de una matriz por otra de rango inferior". Psicometrika . 1 (3): 211–8. doi :10.1007/BF02288367. S2CID 10163399.
^ Hestenes, señor (1958). "Inversión de matrices por biortogonalización y resultados relacionados". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 6 (1): 51–90. doi :10.1137/0106005. JSTOR 2098862. SEÑOR 0092215.
^ (Golub y Kahan 1965)
^ Golub, GH ; Reinsch, C. (1970). "Descomposición de valores singulares y soluciones de mínimos cuadrados". Matemática numérica . 14 (5): 403–420. doi :10.1007/BF02163027. SEÑOR 1553974. S2CID 123532178.
Referencias
Banerjee, Sudipto; Roy, Anindya (2014), Álgebra lineal y análisis matricial para estadística , Textos de ciencia estadística (1.ª ed.), Chapman y Hall/CRC, ISBN 978-1420095388
Bisgard, James (2021). Análisis y álgebra lineal: descomposición y aplicaciones de valores singulares . Biblioteca de Matemáticas para Estudiantes (1ª ed.). AMS. ISBN 978-1-4704-6332-8.
Chicco, D; Masseroli, M (2015). "Paquete de software para búsqueda de similitudes y predicción de anotaciones de genes y proteínas". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 12 (4): 837–843. doi :10.1109/TCBB.2014.2382127. hdl : 11311/959408 . PMID 26357324. S2CID 14714823.
Trefethen, Lloyd N .; BauIII, David (1997). Álgebra lineal numérica . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 978-0-89871-361-9.
Demmel, James ; Kahan, William (1990). "Valores singulares precisos de matrices bidiagonales". Revista SIAM de Computación Científica y Estadística . 11 (5): 873–912. CiteSeerX 10.1.1.48.3740 . doi :10.1137/0911052.
Golub, Gene H .; Kahan, William (1965). "Cálculo de los valores singulares y pseudoinversos de una matriz". Revista de la Sociedad de Matemáticas Industriales y Aplicadas, Serie B: Análisis numérico . 2 (2): 205–224. Código Bib : 1965SJNA....2..205G. doi :10.1137/0702016. JSTOR 2949777.
Equipo GSL (2007). "§14.4 Descomposición de valores singulares". Biblioteca científica GNU. Manual de referencia .
Halldor, Bjornsson y Venegas, Silvia A. (1997). "Un manual para análisis de datos climáticos EOF y SVD". Universidad McGill, Informe CCGCR No. 97-1, Montreal, Québec, 52pp.
Hansen, ordenador personal (1987). "La SVD truncada como método de regularización". POCO . 27 (4): 534–553. doi :10.1007/BF01937276. S2CID 37591557.
Cuerno, Roger A.; Johnson, Charles R. (1985). "Sección 7.3". Análisis matricial . Prensa de la Universidad de Cambridge. ISBN 978-0-521-38632-6.
Cuerno, Roger A.; Johnson, Charles R. (1991). "Capítulo 3" . Temas de análisis matricial . Prensa de la Universidad de Cambridge. ISBN 978-0-521-46713-1.
Samet, H. (2006). Fundamentos de estructuras de datos métricas y multidimensionales . Morgan Kaufman. ISBN 978-0-12-369446-1.
Strang G. (1998). "Sección 6.7". Introducción al álgebra lineal (3ª ed.). Prensa de Wellesley-Cambridge. ISBN 978-0-9614088-5-5.
Stewart, GW (1993). "Sobre la historia temprana de la descomposición del valor singular". Revisión SIAM . 35 (4): 551–566. CiteSeerX 10.1.1.23.1831 . doi :10.1137/1035134. hdl : 1903/566. JSTOR 2132388.
Muro, Michael E.; Rechtsteiner, Andreas; Rocha, Luis M. (2003). "Descomposición de valores singulares y análisis de componentes principales". En DP Berrar; W. Dubitzky; M. Granzow (eds.). Un enfoque práctico para el análisis de datos de microarrays . Norwell, MA: Kluwer. págs. 91-109.
Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.6", Recetas numéricas: el arte de la informática científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8