¿Cuál es la solución para $X = AXA$ ?

Question

He dado una visión general $n \times d$ matriz $B$ y necesitamos calcular dos matrices de similitud $R \in \mathbb{R}^{n \times n}$ y $S \in \mathbb{R}^{d \times d}$ como sigue:

$R = BSB^\top$ y $S = B^\top RB$ .

Al insertar una ecuación en la otra se obtiene $S = B^\top B S B^\top B$ . Supongo que no siempre existe una solución. En este caso, estoy interesado en una solución aproximada que minimice $||S - B^\top B S B^\top B||_F$ .

¿Existe un nombre para este tipo de problema? Y ¿hay alguna forma eficiente de resolverlo (posiblemente utilizando algún algoritmo iterativo)?

Nota: La matriz cero satisfaría la ecuación anterior, pero necesito matrices de similitud, es decir, matrices simétricas para las que los elementos diagonales deben ser iguales a 1.

Answer 1

Dado $A$ es $d \times d$ y de valor real:

La fórmula $X = AXA$ puede reescribirse con $X$ reordenados como $\operatorname{vec}(X)$ un vector columna de $d^2$ elementos:

$$ \operatorname{vec}(X) = \left( A^T \otimes A \right) \operatorname{vec}(X) $$

... donde $\otimes$ es el Producto de Kronecker , a $d^2 \times d^2$ matriz. Por lo tanto, hay soluciones distintas de cero si $\left(A^T \otimes A\right)$ tiene cualesquiera valores propios iguales a 1, y la solución o soluciones son los vectores propios correspondientes.

En $d^2$ valores propios de $\left( A^T \otimes A \right)$ se puede obtener multiplicando todos los emparejamientos del $d$ valores propios de $A$ . Por tanto, si alguno de los valores propios de $A$ tienen un valor absoluto de 1 (incluidos los valores complejos), o si cualquier par de ellos satisface $\lambda_j \lambda_k =1$ tiene una solución para $X=AXA$ .

[En su caso $A=B^TB$ es simétrica por lo que todos los valores propios de $A$ será real].

Por supuesto, puede que no sea posible escalarlo a ese $X$ es una matriz de similitud. Es evidente que todas las soluciones $X$ será singular, a menos que el determinante de $A$ es 1 o -1. De hecho, cualquier $X$ obtenido directamente a partir de un vector propio del producto de Kronecker será de rango 1, siendo el producto exterior de los vectores propios de $A$ (esto se discute más adelante), por lo que un no-singular $X$ sólo podría obtenerse mediante una suma de múltiples soluciones de este tipo.

---

Para el caso en que $A$ es simétrica:

deje $P=\left( A^T \otimes A \right)$

• si $X$ es una solución, entonces también lo es $X^T$
• Para cada valor propio de $P$ que es 1, el vector propio correspondiente da una solución para $X$ .
• Si hay más de una solución, puedes combinarlas arbitrariamente de forma lineal para obtener otras.
• Si existe un valor propio unitario de $P$ donde el vector propio correspondiente da $X$ que no es simétrica, habrá otro que dé $X^T$ así que puedes sumarlos y obtener una solución simétrica. Estos son los valores propios unitarios de $P$ que son productos de dos valores propios de $A$ y, por tanto, se producen por parejas. Los que surgen de cuadrados de {-1,1} valores propios de $A$ dan soluciones simétricas directamente.

Por tanto, cuantos más valores propios unitarios de $P$ más soluciones simétricas tendrás; si tienes suficientes, puedes resolver cómo combinarlas para obtener un resultado con 1 a lo largo de la diagonal.

Por ejemplo, supongamos $d=5$ y los valores propios de $A$ son $[ 1,1, {1 \over 2} , 2,2]$ tendrá 8 valores propios unitarios de $P$ - dos de elevarlos al cuadrado, 3+3 de multiplicarlos por pares; y así obtendrás 5 resultados simétricos para $X$ . Aunque no estoy seguro de que los 5 sean independientes en sus diagonales.

Y cada $X$ candidato -- el vector propio de $P$ correspondiente a un valor propio de $P$ que es el producto de dos valores propios dados de $A$ -- puede hallarse como el producto exterior de los dos vectores propios correspondientes de $A$ reordenado en un vector. O dejado en forma de matriz ya que desea $X$ . Así que no necesita encontrar $P$ o todos sus vectores propios.

En una aplicación práctica, puede ser necesario realizar un ajuste a las mejores soluciones simétricas disponibles, incluidas las correspondientes a valores propios de $P$ que son "suficientemente cercanos" a 1.

---

O, si necesita ajustar los valores propios de $A$ un poco para obtener una solución exacta para $X$ es relativamente sencillo volver a reflejar esos cambios en $B$ es decir, encontrar un nuevo $B$ pero con un resultado exacto $X$ solución. La nueva $B$ tendrá la misma descomposición de valores singulares que el original pero con SV ligeramente diferentes:

(1) encontrar la descomposición eigen de $A$ : $$ B^T B = A = Q L Q^T $$ ... donde $L$ es una matriz diagonal con los valores propios de $A$ y $Q$ es una matriz ortonormal con los vectores propios en las columnas

(2) Buscar $X$ solución(es) como arriba, ajustando los valores propios según sea necesario; Esto conduce a un nuevo conjunto de valores propios $L'$ y nuevo valor para $A$ Llámalo $A'=Q L' Q^T$

(3) encontrar una matriz diagonal $R$ cuyos elementos diagonales son las raíces cuadradas de los factores por los que multiplicaste los valores propios. Entonces: $$\begin{align} L' &= RLR \\ A' &= Q R L R^T Q^T \end{align}$$

(4) encontrar un nuevo valor $B' = BQRQ^T$ . Ahora $$\begin{align} {B'}^T B' &= QR Q^T B^T B Q R Q^T\\ &= QR Q^T A Q R^T Q^T \\ &= QR Q^T Q L Q^T Q R^T Q^T \\ &= QR L R^T Q^T \\ &= A' \end{align} $$ Así que, suponiendo $R$ se aproxima a una matriz de identidad, $B'$ se acerca al original $B$ y da el valor exacto de $X$ solución(es) seleccionada(s) ajustando los valores propios en (2)