¿Cómo se reordena la descomposición de valores singulares (SVD)?

Question

Podemos realizar la SVD ( $A=U\Sigma V^T$ ) de tal manera que las entradas diagonales de $\Sigma$ están en orden descendente.

Mi pregunta es, ¿cómo hacer este reordenamiento? ¿Puede alguien mostrarme los detalles?

Otra pregunta: ¿es el $A=U'\Sigma' V'^T$ ¿sigue siendo un SVD válido?

Answer 1

Hay varias explicaciones de la SVD por todas partes. Aquí hay una enlace a alguna explicación en este foro.

Aquí hay una construcción que consigue el ordenamiento tal como lo pediste.

Supongamos que $A$ es un $m\times n$ matriz en $\mathbb{C}$ . Utilizamos $A^*$ para denotar la transposición conjugada de $A$ (esto es un $n\times m$ matriz). En términos de operadores sobre $L(\mathbb{C}^m,\mathbb{C}^n)$ , $A^*$ es el operador que satisface $$y^*Ax=\langle Ax,y\rangle = \langle x,A^*y\rangle=(A^*y)^*x$$

• $A^*A$ es un $n\times n$ matriz y satisface $x^*A^*Ax=\langle Ax,Ax\rangle=\|Ax\|^2_2\geq0$ .
• Por hechos conocidos del álgebra lineal, $A^*A$ tiene $n$ -valores propios, todos reales y no negativos, que pueden ordenarse de forma decreciente como $\sigma^2_1\geq \sigma^2_2\geq\ldots\geq\sigma^2_n$ . Los vectores propios correspondientes a diferentes valores propios son ortogonales, por lo que podemos encontrar una base ortogonal para $\mathbb{C}^n$ consistente de vectores propios .
• Supongamos que $r=\operatorname{rank}(A^*A)$ . Entonces $r\leq (m,n)$ y así $\sigma^2_1\geq\ldots\geq\sigma^2_r>0=\sigma^2_{r+1}=\ldots\sigma^2_n$ .
• Elegimos los vectores propios $u_j$ tal que $$A^*Au_j=\sigma^2_j u_j,\quad 1\leq j\leq n$$ y $\langle u_i,u_j\rangle=u^*_ju_i=\delta_{ij}$ . Es decir $\{u_j:1\leq j\leq n\}$ para una base ortonormal de vectores propios.
• En particular $$ \|Au_j\|^2=\langle Au_j,Au_j\rangle =\langle u_j,A^*Au_j\rangle =\sigma^2_j\langle u_j,u_j\rangle =\sigma^2_j$$ y así, $Au_j>0$ para $1\leq j\leq r$ y $0$ de lo contrario.
• Definir $Q$ como el $n\times n$ matriz cuya $j$ -la fila es $u^*_j$ . Claramente $Q$ es una matriz ortogonal ya que $QQ^*=I_n$ lo que a su vez significa que $Q^*Q=I_n$ .
• Para $i=1,\ldots ,r$ definir $$v_i=\frac{1}{\sigma_i}Au_j$$
• Tenga en cuenta que si $1\leq i,j\leq r$ , $$\langle v_i,v_j\rangle =\frac{1}{\sigma_i\sigma_j}\langle Au_i,Au_j\rangle=\frac{1}{\sigma_i\sigma_j}\langle u_i,A^*Au_j\rangle =\frac{\sigma_j}{\sigma_i}\delta_{ij}=\delta_{ij}$$ Eso es, $\{v_j:1\leq j\leq r\}$ son vectores ortonormales en $\mathbb{C}^m$ .
• Completa $\{v_1,\ldots,v_r\}$ con vectores $\{v_{r+1},\ldots,v_m\}$ (si es necesario) para formar una base ortonormal para $\mathbb{C}^m$ . Definir $P$ como el $m\times m$ matriz cuya $i$ -la columna es $v_i$ . Claramente, $P$ es una matriz ortogonal para $P^*P=I_m$ y así $PP^*=I_m$
• Observe que $D:=P^*AQ^*$ es un $m\times n$ matriz con diagonal principal $(\sigma_1,\ldots,\sigma_r,0,\ldots,0)$ y ceros en todo lo demás, para $$(P^*AQ^*)_{ij}=v^*_iAu_j=\sigma_jv_iv_j=\sigma_j\delta_{ij}$$ para $1\leq j\leq r$ y $$(P^*AQ)_{ij}=v^*_iAu_j=\sigma_j v^*_iv_j=0=\sigma_j\delta_{ij}$$ para $j>r$ .
• Juntando las cosas, se obtiene $A=PDQ$ con el deseado ordenamiento decreciente en la diagonal principal de $D$ .

---

Algunos comentarios finos:

1. Matrices $Q$ y $P$ en la descomposición SVD de $A$ incluso cuando la diagonal principal de $D$ se ordena de forma decreciente, no son únicos (hay una opción para ordenar los vectores propios correspondientes a un valor propio de multiplicidad > 1, otra opción para completar una base ortonormal para construir $P$ y la multiplicación de vectores por escalas unitarias producirá también diferentes $Q$ s y $P$ s)

2. Si una determinada descomposición SVD $P,D,Q$ de $A$ se da, permutaciones en la diagonal principal de $D$ ( $\sigma_j$ y $\sigma_i$ se intercambian, da como resultado que se intercambien los $i$ -y $j$ -a filas de $Q$ y el $i$ -y $j$ -a las columnas de $P$ para mantener una identidad de la forma $A=(P')D'(Q')^*$ .

3. Existen algoritmos numéricos eficientes para encontrar la descomposición SVD ya implementados en muchas bibliotecas (BLAS, LAPACK, etc) que pueden ser portados a Fortran, C, C++, etc. Todos ellos, que yo sepa, producen un $m\times n$ diagonal $D$ matriz donde la diagonal principal está ordenada de forma decreciente.