¿Descomposición matricial tipo SVD basada en cualquier base?

Question

Digamos que tengo un punto $\mathbf{x}$ en $n$ -espacio dimensional. Para cualquier base $(\mathbf{u}_1, ..., \mathbf{u}_n)$ , $\mathbf{x}$ puede escribirse como una combinación lineal de esta base.

$\mathbf{x} = x_1 \mathbf{u}_1 + x_2 \mathbf{u}_2 + ... + x_n \mathbf{u}_n$ donde cada $x_i$ es una proyección de $\mathbf{x}$ en $\mathbf{u}_i$ .

Ahora quiero generalizarlo a una matriz $\mathbf{X}$ en $\mathbb{R}^{m\times n}$ . La descomposición del valor singular (SVD) garantiza que cualquier matrx $\mathbf{X}$ de rango $r$ puede escribirse como $$\mathbf{X} = \sum_{i=1}^r \sigma_i \mathbf{u}_i \mathbf{v}^T_i$$ donde $\mathbf{u}_1, ..., \mathbf{u}_r\in\mathbb{R}^m$ son ortonormales (cada una tiene longitud 1 y cada par es ortogonal) y $\mathbf{v}_1, ..., \mathbf{v}_r\in\mathbb{R}^n$ también son ortonormales. Cada par $\mathbf{u}_i$ y $\mathbf{v}_i$ forman un par de vectores singulares izquierdo y derecho con valor singular $\sigma_i$ .

Tenga en cuenta que $\mathbf{u}_1, ..., \mathbf{u}_r$ no es el único conjunto vectorial ortonormal en $\mathbb{R}^m$ . De hecho, cualquier $r$ vectores recogidos de un ortonormal base $\mathbf{u}'_1, ..., \mathbf{u}'_m\in\mathbb{R}^m$ puede ser un candidato. Lo mismo ocurre con los vectores singulares de la derecha $\mathbf{v}_i$ 's.

Entonces la pregunta es, ¿puedo escribir la descomposición tipo SVD usando cada base ortonormal que no sean los vectores singulares izquierdo/derecho? (Entonces la SVD puede considerarse como un caso especial de esta composición que utiliza vectores singulares izquierdo/derecho). Es decir, ¿puedo escribir algo como $$\mathbf{X} = \sum_{i=1}^r \alpha_i \mathbf{s}_i \mathbf{t}^T_i$$ para todo vector ortonormal $\mathbf{s}_1, ..., \mathbf{s}_r\in\mathbb{R}^m$ y $\mathbf{t}_1, ..., \mathbf{t}_r\in\mathbb{R}^n$ ? Si eso es posible, ¿cómo puedo calcular tal $\alpha_i$ 's?

Answer 1

Las SVD son básicamente únicas si todos los valores singulares son diferentes. (Técnicamente, son únicas hasta los factores unitarios de los vectores singulares). En el caso de que algunos valores singulares sean iguales y la SVD no sea única, se puede hacer lo siguiente para comprobar si determinadas bases ortonormales conducen a una descomposición diagonal:

Dejemos que $\mathbf{S} = [\mathbf{s}_1 ... \mathbf{s}_r] \in \mathbb{R}^{m \times r}$ y $\mathbf{T} = [\mathbf{t}_1 ... \mathbf{t}_r] \in \mathbb{R}^{n \times r}$ con $\mathbf{S}^T\mathbf{S}=\mathbf{T}^T\mathbf{T}=\mathbf{I}_r$ . Calcula $\mathbf{A} = \mathbf{S}^T \mathbf{X} \mathbf{T}$ . Si $\mbox{rank}(\mathbf{X}) = r$ y $\mathbf{A}$ es no singular, entonces $\mathbf{X} = \mathbf{SAT}^T$ . En particular, si $\mathbf{A}$ es no singular y diagonal, entonces sus entradas diagonales son su $\alpha_i$ . Tenga en cuenta que esto sólo puede ser cierto si el $\mathbf{s}_i$ son vectores singulares izquierdos de $\mathbf{X}$ y $\mathbf{t}_i$ son los correspondientes vectores singulares derechos. En caso contrario, $\mathbf{A}$ es singular o no diagonal, y no es posible la descomposición.

La intuición es que $\mathbf{A}$ es no singular si los vectores $\mathbf{s}_i$ abarcan el espacio de las columnas de $\mathbf{X}$ y los vectores $\mathbf{t}_i$ abarcan su espacio de fila. Si esto es cierto, entonces $\mathbf{X} = \mathbf{SS}^T\mathbf{X}$ porque $\mathbf{SS}^T$ es sólo un proyector sobre el espacio de la columna. Asimismo, $\mathbf{X} = \mathbf{XTT}^T$ Así que $\mathbf{X} = \mathbf{SS}^T\mathbf{XTT}^T=\mathbf{SAT}^T$ . O, expresado como una suma de productos externos: $$ \mathbf{X} = \sum_{i=1}^r \sum_{j=1}^r a_{ij} \mathbf{s}_i \mathbf{t}_j^T $$ Es fácil ver (desde la independencia lineal) que si $\mathbf{S}$ y $\mathbf{T}$ son fijos, entonces los coeficientes en la descomposición anterior son únicos.

Por cierto, su afirmación "cualquier $r$ vectores escogidos de una base" debería ser "cualquier $r$ vectores recogidos de un ortonormal base". Si los vectores no son ortonormales, pero siguen siendo linealmente independientes, la fórmula se generaliza así: si $\mathbf{A} = (\mathbf{S}^T\mathbf{S})^{-1}\mathbf{S}^T \mathbf{X} \mathbf{T}(\mathbf{T}^T\mathbf{T})^{-1}$ y $\mbox{rank}(\mathbf{A})=\mbox{rank}(\mathbf{X})$ entonces $\mathbf{X}=\mathbf{SAT}^T$ .

Como nota, una idea realmente interesante de los últimos años es que se puede elegir $\mathbf{S}$ y $\mathbf{T}$ al azar y luego calcular la SVD de la matriz más pequeña $\mathbf{A}$ para calcular la SVD de $\mathbf{X}$ . Esto funciona porque si $\mathbf{A} = \mathbf{U\Sigma V}^T$ entonces $\mathbf{X} = \mathbf{\tilde{U}\Sigma \tilde{V}}^T$ , donde $\mathbf{\tilde{U}}=\mathbf{SU}$ y $\mathbf{\tilde{V}}=\mathbf{TV}$ . Si $r$ es mucho menor que $n$ o $m$ esto supone un gran ahorro computacional respecto al cálculo de la SVD de $\mathbf{X}$ directamente.

Answer 2

No, no se puede hacer esto para conjuntos ortonormales arbitrarios $s_i$ , $t_i$ . Para ver esto, defina una función $f$ de vectores no nulos por $f(z) = \frac{\lVert Xz \rVert}{\lVert z\rVert}$ , donde $\lVert z \rVert = \sqrt{\sum z_i^2}$ denota el $\ell^2$ -normas. El valor $f(z)$ mide la "ganancia" de $X$ en $z$ : el factor por el cual $X$ escala la magnitud del vector $z$ .

Supongamos que $X = \sum_{i=1}^r a_i s_i t_i'$ para los números reales $0\leq a_r\leq a_{r-1}\leq \cdots \leq a_1$ y conjuntos ortonormales de vectores columna $s_i$ y $t_i$ . Si descomponemos un vector $z$ en el ámbito de $f$ como $z = \sum c_i t_i$ entonces la ortonormalidad de las bases $s_i$ y $t_i$ da \[ f(z) = \frac{{lVert{suma c_i a_i s_i\rVert}{lVert{suma c_i t_i\rVert} = \frac{sqrt{suma a_i^2 c_i^2}{sqrt{suma c_i^2}. \] Dado que $0\leq a_i \leq a_1$ para todos $i$ por suposición, \[ f(z) = \frac{{sqrt{suma a_i^2 c_i^2}}{sqrt{suma c_i^2} \leq{frac{sqrt{suma a_1^2 c_i^2}}{sqrt{suma c_i^2} = \frac{a_1\sqrt{suma c_i^2}}{sqrt{suma c_i^2}} = a_1. \] Este límite superior se alcanza en $z = t_1$ porque $f(t_i) = a_i$ para todos $i$ .

La función $f$ se definió en términos de la matriz $X$ y no la descomposición $X = \sum_{i=1}^r a_i s_i t_i'$ por lo que esto demuestra que hay restricciones en la elección de $a_1$ y $t_1$ . En particular $a_1$ debe ser el valor máximo de $f$ y $t_1$ debe ser un maximizador de $f$ . Un argumento similar utilizando $A'$ en lugar de ello, produce restricciones en $s_1$ .

Si $a_1>a_2$ entonces la desigualdad anterior es ajustada si y sólo si $c_i = 0$ para todos $i\neq 1$ . En este caso los únicos maximizadores de $f$ son múltiplos escalares de $t_1$ . Desde $t_1$ tiene norma unitaria, el análisis anterior determina $t_1$ hasta la firma (o fase en el caso complejo).

En general, si $a_1 = \cdots = a_k > a_{k+1}$ para algunos $k$ entonces la desigualdad es estricta exactamente cuando $c_i = 0$ para $i>k$ . Es decir, los maximizadores de $f$ son los elementos no nulos del tramo de $t_1,\ldots, t_k$ . Por lo tanto, el análisis anterior sólo restringe $t_1$ para mentir en este lapso.

De hecho, podríamos sustituir $t_1,\ldots, t_k$ por cualquier conjunto ortonormal $\tilde{t}_1,\ldots,\tilde{t}_k$ con el mismo lapso y reemplazar $s_1,\ldots, s_k$ por $\tilde{s}_i = \frac{X\tilde{t}_i}{a_i}$ para obtener otra descomposición $X = \sum_{i=1}^r a_i \tilde{s}_i \tilde{t}_i'$ . Por lo tanto, en los casos en que hay valores singulares repetidos, tenemos algunos grados de libertad en la elección de la base ortonormal.

Restringir la acción de $X$ al subespacio ortogonal a $t_1,\ldots,t_k$ y repitiendo este argumento te dice lo que $a_{k+1}$ , $t_{k+1}$ y $s_{k+1}$ tiene que ser, y así sucesivamente. Al final, todos $a_i$ están predeterminados por $X$ y $t_i$ está predeterminado hasta la firma a menos que $a_i = a_{i-1}$ o $a_i = a_{i+1}$ .

Este tipo de razonamiento ofrece una forma de desarrollar la definición y las propiedades del SVD. Pruebe a buscar en Google "SVD variational characterization" ( variacional significa que tiene que ver con maximizar $f$ ) para saber más.