Método para invertir un producto de Kronecker

Question

Digamos que tengo dos vectores simples: $[0, 1]$ y $[1, 0]$ .

Su producto de Kronecker sería $[0, 0, 1, 0]$ .

Digamos que sólo tengo el producto de Kronecker. ¿Cómo puedo encontrar los dos vectores iniciales de nuevo?

Si mis dos vectores se escriben como : $[a, b]$ y $[c, d]$ el producto de Kronecker (dado) es:

$$[ac, ad, bc, bd] = [k_0, k_1, k_2, k_3]$$ Así que tengo un sistema de cuatro ecuaciones no lineales que deseo resolver: $$\begin{align*} ac &= k_0\\ ad&= k_1\\ bc&= k_2\\ bd &=k_3. \end{align*}$$

Estoy buscando una forma general de resolver este problema para cualquier número de vectores iniciales en $\mathbb{C}^2$ (llevando mi número de variables a $2n$ y mis ecuaciones a $2^n$ si tengo $n$ vectores).

Así que aquí hay algunas preguntas específicas:

¿Cuál es el nombre común de este problema?

Si se conoce una solución general, ¿cuál es su clase de complejidad?

¿El hecho de que tenga más y más ecuaciones cuando $n$ sube en comparación con el número de variables ayuda?

(Nota: realmente no sabía qué poner como etiqueta).

Answer 1

Este problema (producto de Kronecker inverso) tiene una solución conocida llamada "Producto de Kronecker más cercano" y se generaliza también a las matrices.

Dado $A\in \mathbb R^{m\times n} $ con $m = m_1m_2$ y $n = n_1n_2$ , encontrar $B\in \mathbb R^{m_1\times n_1}$ y $C\in \mathbb R^{m_2\times n_2}$ así que

$\phi(B,C)$ = min. $|| A- B\otimes C||_F$ , donde $F$ denota la norma de Frobenius.

Esto se reformula como:

$\phi(B,C)$ = min. $|| R- vec(B)\otimes vec(C)'||_F$

$vec$ es el operador de vectorización que apila las columnas de una matriz unas sobre otras. A se reordena en $R \in \mathbb R^{m_1n_1\times m_2n_2}$ tal que la suma de cuadrados en $|| A- B\otimes C||_F$ es exactamente lo mismo que $|| R- vec(B)\otimes vec(C)'||_F$ .

Ejemplo de acuerdo en el que $m_1=3,n_1=m_2=n_2=2$ :

$$ \phi(B,C) = \left| \left[ \begin{array}{cc|cc} a_{11}& a_{12} & a_{13} & a_{14} \\ a_{21}& a_{22} & a_{23} & a_{24} \\ \hline a_{31}& a_{32} & a_{33} & a_{34} \\ a_{41}& a_{42} & a_{43} & a_{44} \\ \hline a_{51}& a_{52} & a_{53} & a_{54} \\ a_{11}& a_{62} & a_{63} & a_{64} \end{array} \right] - \begin{bmatrix} b_{11}& b_{12} \\ b_{21}& b_{22} \\ b_{31}& b_{32} \end{bmatrix} \otimes \begin{bmatrix} c_{11}& c_{12} \\ c_{21}& c_{22} \end{bmatrix} \right|_F \\ \phi(B,C) = \left| \begin{bmatrix} a_{11}& a_{21} & a_{12} & a_{22} \\ \hline a_{31}& a_{41} & a_{32} & a_{42} \\ \hline a_{51}& a_{61} & a_{52} & a_{62} \\ \hline a_{13}& a_{23} & a_{14} & a_{24} \\ \hline a_{33}& a_{43} & a_{34} & a_{44} \\ \hline a_{53}& a_{63} & a_{54} & a_{64} \end{bmatrix} - \begin{bmatrix} b_{11} \\ b_{21} \\ b_{31} \\ b_{12} \\ b_{22} \\ b_{32} \end{bmatrix} \begin{bmatrix} c_{11}&c_{21} & c_{12} & c_{22} \end{bmatrix} \right|_F $$

Ahora el problema se ha convertido en una aproximación de rango 1 para una matriz rectangular. La solución viene dada por la descomposición del valor singular de $R = USV^T$ en [1,2]. $$ vec(B) = \sqrt{\sigma_1}u_1, \quad vec(C) = \sqrt{\sigma_1}v_1 $$

Si $R$ es una matriz de rango 1 la solución será exacta, es decir $A$ es totalmente separable[3].

[1] Golub G, Van Loan C. Matrix Computations, The John Hopkins University Pres. 1996 [2] Van Loan C., Pitsianis N., Approximation with Kronecker Products, Cornell University, Ithaca, NY, 1992 [3] Genton MG. Separable approximations of space-time covariance matrices. Environmetrics 2007; 18:681-695.

Answer 2

En primer lugar: no va a haber ninguna respuesta única sobre cómo factorizarlos. Para tomar un ejemplo muy simple,

$\begin{align} [0\;\;6\;\;0\;\;0] = \left\{\begin{array}{c} [6\;\;0] \otimes [0\;\;1] \\ \\ [2\;\;0] \otimes [0\;\;3] \\ \\ [1\;\;0] \otimes [0\;\;6] \end{array}\right.\end{align}$

por lo que cualquiera de los productos de la derecha (¡así como un continuo de otros!) podría ser una respuesta válida. Sólo podemos remediar esta situación generalizando su criterio para una factorización, exigiendo una función que mapee cualquier vector del producto de Kronecker $\mathbf p$ una salida consistente en un escalar $s \in \mathbb C$ y dos vectores unitarios $\mathbf v, \mathbf w \in \mathbb C^2$ tal que $\mathbf p = s \, (\mathbf v \otimes \mathbf w)$ . Con el fin de $\mathbf v$ y $\mathbf w$ para ser única, también tenemos que fijar el grado de libertad en sus coeficientes representados por el argumento complejo, exigiendo que el primer coeficiente no nulo sea un real positivo. Y si $s = 0$ , arreglaremos $\mathbf v = \mathbf 0$ y $\mathbf w = \mathbf 0$ en lugar de vectores unitarios. Es torpe... pero entonces, tiene sentido hablar de una función.

En segundo lugar, tenemos que tener alguna forma de identificar si un vector $\mathbf p$ es un producto de Kronecker en absoluto. En realidad, hay una forma bastante sencilla de hacer esto. Considere la definición del producto de Kronecker, en términos de bloques:

$\mathbf v \otimes \mathbf w = [\;v_1 \mathbf w \;\;|\;\; v_2 \mathbf w \;\;|\;\; \cdots \;\;|\;\; v_m \mathbf w\;]$

donde $\mathbf v \in \mathbb C^m$ y $\mathbf w \in \mathbb C^n$ . Si tomáramos esos bloques y los convirtiéramos en filas separadas, obtendríamos una matriz:

$\begin{bmatrix} v_1 \mathbf w \\ \hline v_2 \mathbf w \\ \hline \vdots \\ \hline v_m \mathbf w\end{bmatrix} = \mathbf v^\top \mathbf w$ .

Hay un isomorfismo entre los elementos de $\mathbb C^m \otimes \mathbb C^n$ y m  ×  n matrices; el mapeo sólo baraja los coeficientes. Los productos de Kronecker, como vemos, se convierten en productos externos de vectores, y lo más destacado de estas matrices es que sus filas son múltiplos de un vector fila común (y lo mismo ocurre con las columnas), por construcción. Para ver si una matriz (no nula) es un producto exterior, basta con saber si tiene rango 1. Para saber si es un producto exterior de se puede encontrar cualquier fila no nula $\mathbf r_\ast\,$ y encontrar los coeficientes de un vector $\mathbf q_\ast$ tal que la matriz es igual a $\mathbf q_\ast^\top \mathbf r_\ast\,$ . Puede hacer lo mismo para cualquier vector del producto de Kronecker; y para devolver un resultado "canónico", debe calcular los vectores unitarios $\mathbf v \propto \mathbf q_\ast$ y $\mathbf w \propto \mathbf r_\ast$ (junto con el factor escalar $s$ ). Si se hace esto para la matriz, se obtiene también una respuesta para el producto de Kronecker.

A partir de estas observaciones, debería quedar bastante claro que deshacer un producto de Kronecker es en $\mathsf P$ ya que se trata de simples cálculos sobre m  ×  n matrices.

Answer 3

Prefiero decir que el Kronecker de dos vectores es reversible, pero hasta un factor de escala. De hecho, Niel de Beaudrap ha dado la respuesta correcta. Aquí intento presentarla de forma concisa.

Dejemos que $a\in\mathbb{R}^N$ y $b\in\mathbb{R}^M$ sean dos vectores columna. La OP es: dado $a\otimes b$ cómo determinar $a$ y $b$ ?

Nota $a\otimes b$ no es más que $\mathrm{vec} (ba^T)$ . El $\mathrm{vec}$ reestructura una matriz en un vector columna apilando los vectores columna de la matriz. Nota: $\mathrm{vec}$ es reversible. Por lo tanto, dado $c=a\otimes b$ primero se le da forma a un $M\times N$ matriz $C=ba^T$ . $C$ es una matriz de rango uno. Simplemente se puede descomponer $C$ para conseguir $kb$ y $a/k$ .