4.3: Descomposición del Valor Singular

Antes de discutir la descomposición del valor singular de las matrices, comenzamos con algunos hechos y definiciones de la matriz.

Algunos datos de Matrix:

• Una matriz\(U \in C^{n \times n}\) es unitaria si\(U^{\prime}U = UU^{\prime}= I\). Aquí, como en Matlab, el superíndice\(^{\prime}\) denota el complejo conjugado (entrada por entrada) de la transposición, que también se denomina transposición hermitiana o transposición conjugada.
• Una matriz\(U \in R^{n \times n}\) es ortogonal si\(U^{T}U = UU^{T}= I\), donde el superíndice\(^{T}\) denota la transposición.
• Propiedad: Si\(U\) es unitario, entonces\(\|U x\|_{2}=\|x\|_{2}\).
• Si\(S = S^{\prime}\) (es decir, es\(S\) igual a su transposición hermitiana, en cuyo caso decimos que\(S\) es hermitiana), entonces existe una matriz unitaria tal que\(U^{\prime}SU= {[diagonal matrix].}^{1}\)
• Para cualquier matriz\(A\), ambas\(A^{\prime}A\) y\(AA^{\prime}\) son hermitianas, y así siempre pueden ser diagonalizadas por matrices unitarias.
• Para cualquier matriz\(A\), los valores propios de\(A^{\prime}A\) y\(AA^{\prime}\) son siempre reales y no negativos (probados fácilmente por contradicción).

Teorema 4.1 (Descomposición del Valor Singular, o SVD)

Dada cualquier matriz\(A \in C^{n \times n}\), se\(A\) puede escribir como

\[A=\stackrel{m \times m}{U} \ \stackrel{m \times n}{\Sigma} \ \stackrel{n \times n}{V^{\prime}}, \ \tag{4.14}\]

donde\(U^{\prime}U =I\),\(V^{\prime}V =I\)

\ [\ Sigma=\ left [\ begin {array} {cccc}
\ sigma_ {1} & & &\\
&\ ddots & & 0\\
& & &\ sigma_ {r} &\
\ hline & & & &\\
& 0 & & 0
\ end {array}\ derecha]\\ tag {4.15}\]

y\($\sigma_{i}=\sqrt{i \text { th nonzero eigenvalue of } A^{\prime} A}$\). Los\($\sigma_{i}\) son denominados los valores singulares de\(A\), y están dispuestos en orden de magnitud descendente, es decir,

\[\sigma_{1} \geq \sigma_{2} \geq \cdots \geq \sigma_{r}>0\nonumber\]

Prueba

Vamos a probar este teorema para el caso\(rank(A) = m\); el caso general involucra muy poco más de lo que se requiere para este caso. La matriz\(AA^{\prime}\) es hermitiana, y por lo tanto puede ser diagonalizada por una matriz unitaria\ (U\ in C^ {m\ times m}\, de manera que

\[U \Lambda_{1} U^{\prime}=A A^{\prime}.\nonumber \]

Tenga en cuenta que\(\Lambda_{1}=\operatorname{diag}\left(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}\right)\) tiene entradas diagonales positivas reales\(\Lambda_{i}\) debido al hecho de que\(AA^{\prime}\) es positivo definido. Podemos escribir\(\Lambda_{1}=\Sigma_{1}^{2}=\operatorname{diag}\left(\sigma_{1}^{2}, \sigma_{2}^{2}, \ldots, \sigma_{m}^{2}\right)\). Definir\(V_{1}^{\prime} \in C^{m \times n}\) tiene filas ortonormales como se puede apreciar a partir del siguiente cálculo:\(V_{1}^{\prime} V_{1}=\Sigma_{1}^{-1} U^{\prime} A A^{\prime} U \Sigma_{1}^{-1}=I\). Elija la matriz\(V_{2}^{\prime}\) de tal manera que

está en\(C^{n \times n}\) n y unitario. Definir la\(m \times n\) matriz\(\Sigma=\left[\Sigma_{1} \mid 0\right].\) Esto implica que

\[\Sigma V^{\prime}=\Sigma_{1} V_{1}^{\prime}=U^{\prime} A\nonumber\]

En otras palabras, tenemos\(A = U \Sigma V^{\prime}\)

Ejemplo 4.2

Para la matriz A dada al inicio de esta conferencia, la SVD -computada fácilmente en Matlab por escrito\([u, s, v] = svd(A)\) - es

\ [A=\ left (\ begin {array} {cc}
.7068 & .7075\\
.7075 & .-7068
\ end {array}\ right)\ left (\ begin {array} {cc}
200.1 & 0\\
0 & 0.1
\ end {array}\ right)\ left (\ begin {array} {cc}
.7075 & .7068\\
-.7068 & .7075
\ end {array}\ derecha)\\ tag {4.16}\]

Solución

Observaciones:

i)\ [\ begin {alineado}
A A^ {\ prime} &=U\ Sigma V^ {\ prime} V\ Sigma^ {T} U^ {\ prime}\\
&=U\ Sigma\ Sigma^ {T} U^ {\ prime}
\ end {alineado}\ nonumber\]

\ [=U\ left [\ begin {array} {ccc|c}
\ sigma_ {1} ^ {2} & & &\\
&\ ddots & & & 0\\
& &\ sigma_ {r} ^ {2} &\
\ hline & & & & &\\ 0
& & & 0
\ end {array}\ derecha] U^ {\ prime}\\\ etiqueta 4.17} \]

que nos dice U diagonaliza\(AA^{\prime}\);

ii)\ [\ begin {alineado}
A^ {\ prime} A &=V\ Sigma^ {T} U^ {\ prime} U\ Sigma V^ {\ prime}\\
&=V\ Sigma^ {T}\ Sigma V^ {\ prime}
\ end {alineado}\ nonumber\]

\ [=V\ izquierda [\ begin {array} {ccc|c}
\ sigma_ {1} ^ {2} & & &\\
&\ ddots & & 0\\
& & &\ sigma_ {r} ^ {2} &\
\ hline & & & & &\\ 0
& & & 0
\ end {array}\ derecha] V^ {\ prime}\\\ etiqueta 4.18} \]

que nos dice V diagonaliza\(AA^{\prime}\);

iii) Si\(U\) y\(V\) se expresan en términos de sus columnas, es decir,

\ [\ begin {array} {l}
U=\ left [\ begin {array} {llll}
u_ {1} & u_ {2} &\ dots & u_ {m}
\ end {array}\ right]\ end {array}\ nonumber\]

y

\ [\ begin {array} {l}
V=\ left [\ begin {array} {llll}
v_ {1} & v_ {2} &\ dots & v_ {n}
\ end {array}\ right]\ end {array}\ nonumber\]

entonces

\[A=\sum_{i=1}^{r} \sigma_{i} u_{i} v_{i}^{\prime}\ \tag{4.19}\]

que es otra forma de escribir el SVD. \(u_{i}\)Se denominan vectores singulares izquierdos de\(A\), y los\(v_{i}\) son sus vectores singulares derechos. De esto vemos que alternativamente podemos interpretar\(Ax\) como

\[A x=\sum_{i=1}^{r} \sigma_{i} u_{i} \underbrace{\left(v_{i}^{\prime} x\right)}_{\text {projection }},\ \tag{4.20}\]

que es una suma ponderada del\(u_{i}\), donde los pesos son los productos de los valores singulares y las proyecciones de\(x\) sobre el\(v_{i}\).

La observación (iii) nos dice que\(\mathcal{R} a(A)=\operatorname{span}\left\{u_{1}, \ldots u_{r}\right\}\) (porque\(A x=\sum_{i=1}^{r} c_{i} u_{i}\) - donde\(c_{i}\) están los pesos escalares). Dado que las columnas de\(U\) son independientes,\(\operatorname{dim}\mathcal{R} a(A)=r=rank(A)\), y\(\left\{u_{1}, \ldots u_{r}\right\}\) constituyen una base para el espacio de rango de\(A\). El espacio nulo de\(A\) viene dado por\ (\ left\ {v_ {r+1},\ ldots v_ {n}\ right\}\. Para ver esto:

\ [\ begin {alineado}
U\ Sigma V^ {\ prime} x=0 &\ Longleftrightarrow\ Sigma V^ {\ prime} x=0\
\\ Longleftrightarrow &\ left [\ begin {array} {c}
\ sigma_ {1} v_ {1} ^ {\ prime} x
\\ vdots\
\ sigma_ {r} v_ r} ^ {\ prime} x
\ end {array}\ derecha] =0\
\ Longleftrightarrow & v_ {i} ^ {\ prime} x=0,\ quad i=1,\ ldots, r\\
\ Longleftrightarrow & x\ in\ nombreoperador {span}\ izquierda\ {v_ {r+1},\ ldots, v_ {n}\ derecha\}
\ final {alineado}\ nonumber\]

Ejemplo 4.3

Una aplicación de la descomposición de valores singulares es a la solución de un sistema de ecuaciones algebraicas. Supongamos que\(A\) es una matriz\(m \times n\) compleja y\(b\) es un vector en\(C^{m}\). Supongamos que el rango de\(A\) es igual a\(k\), con\(k < m\). Estamos buscando una solución del sistema lineal\(Ax = b\). Al aplicar el procedimiento de descomposición de valores singulares a\(A\), obtenemos

\ [\ begin {aligned}
A &=U\ Sigma V^ {\ prime}\\
&=U\ izquierda [\ begin {array} {c|c}
\ Sigma_ {1} & 0\\
0 & 0
\ end {array}\ derecha] V^ {\ prime}
\ end {alineado}\ nonumber\]

donde\(\Sigma_{1}\) es una matriz diagonal\(k \times k\) no singular. Expresaremos las matrices unitarias\(U\) y\(V\) columnwise como

\ [\ begin {array} {l}
U=\ left [\ begin {array} {llll}
u_ {1} & u_ {2} &\ dots & u_ {m}
\ end {array}\ right]\
V=\ left [\ begin {array} {llll}
v_ {1} & v_ {2} &\ dots & v_ {n}
\ end {array}\ derecha]
\ end { matriz}\ nonumber\]

Solución

Una condición necesaria y suficiente para la solvabilidad de este sistema de ecuaciones es que\(u^{\prime}_{i}b=0\) para todos\(i\) satisfactorios\(k < i \leq m\). De lo contrario, el sistema de ecuaciones es inconsistente. Esta condición significa que el vector\(b\) debe ser ortogonal a las últimas\(m - k\) columnas de\(U\). Por lo tanto, el sistema de ecuaciones lineales puede escribirse como

\ [\ left [\ begin {array} {c|l}
\ Sigma_ {1} & 0\\
\ hline &\\\
0 & 0
\ end {array}\ derecha] V^ {\ prime} x=U^ {\ prime} b\ nonumber\]

\ [\ left [\ begin {array} {c|l}
\ Sigma_ {1} & 0\\
\ hline &\\\
0 & 0
\ end {array}\ derecha] V^ {\ prime} x=\ left [\ begin {array} {c}
u_ {1} ^ {\ prime} b\\
u_ {2} ^ {\ prime} b
\\ vdots\
\ vdots\\
u_ {m} ^ {\ prime} b
\ end {array}\ right] =\ left [\ begin {array} {c}
u_ {1} ^ {\ prime} b\
\\ vdots\\
u_ {k} ^ {\ prime} b\\
0\
\ vdots\\
0
\ end {array}\ derecha]\ nonumber\]

Usando la ecuación anterior y la invertibilidad de\(\Sigma_{1}\), podemos reescribir el sistema de ecuaciones como

\ [\ left [\ begin {array} {c}
v_ {1} ^ {\ prime}\\
v_ {2} ^ {\ prime}\\
\ vdots\\
vdots\\ v_ {k} ^ {
\ prime}\ end {array}\ right] x=\ left [\ begin {array} {c}
\ frac {1} {\ sigma_ {1}} u_ {1} {\ prime} b\
\\ frac {1} {\ sigma_ {2}} u_ {2} ^ {\ prime} b \\
\ cdots\\
\ frac {1} {\ sigma_ {k}} u_ {k} ^ {\ prime} b
\ end {array}\ derecha]\ nonumber\]

Al usar el hecho de que

\ [\ left [\ begin {array} {c}
v_ {1} ^ {\ prime}\\
v_ {2} ^ {\ prime}\\
\ vdots\\
vdots\\ v_ {k} ^ {
\ prime}\ end {array}\ derecha]\ left [\ begin {array} {llll}
v_ {1} & v_ {2} &\ ldots & v_ {k}
\ end {array}\ right] =I\ nonumber\]

obtenemos una solución de la forma

\[x=\sum_{i=1}^{k} \frac{1}{\sigma_{i}} u_{i}^{\prime} b v_{i}\nonumber\]

A partir de las observaciones que se hicieron anteriormente, sabemos que los vectores\(v_{k+1}, v_{k+2}, \dots, v_{n}\) abarcan el núcleo de\(A\), y por lo tanto una solución general del sistema de ecuaciones lineales viene dada por

\[x=\sum_{i=1}^{k} \frac{1}{\sigma_{i}}\left(u_{i}^{\prime} b\right) v_{i}+\sum_{i=k+1}^{n} \beta_{i} v_{i}\nonumber\]

donde los coeficientes\(\beta_{i}\), con\(i\) en el intervalo\(k+1 \leq i \leq n\), son números complejos arbitrarios.