Un tipo inusual de problema de álgebra lineal

Question

Me he encontrado con el siguiente problema de álgebra lineal mientras intentaba derivar algo en teoría de la información. Estoy buscando tanto formas numéricas de resolver este tipo de problema como cualquier cosa analítica que se pueda decir al respecto. Si hay una solución de forma cerrada (por ejemplo, en términos de álgebra matricial) sería genial.

Tengo una matriz $C$ (que puede ser singular) y los vectores $a$ y $b$ tal que $\sum_i a_i = \sum_j b_j$ . Estoy buscando vectores $\alpha$ y $\beta$ de manera que las siguientes condiciones se cumplan simultáneamente: $$ \sum_i \alpha_i C_{ij} \beta_j = b_j\qquad\text{(for every $ j $)} $$ y $$ \sum_j \alpha_i C_{ij} \beta_j = a_i\qquad\text{(for every $ i $).} $$

Está claro que hay casos en los que no existe solución, como cuando $C$ es diagonal y $a\ne b$ Pero sospecho que en mi caso siempre habrá una solución. Parece que esto debería ser fácil de resolver, pero no veo muy bien cómo hacerlo.

Lo siguiente puede ser relevante o no para responder a la pregunta, pero en mi caso todos los números se refieren a una distribución de probabilidad conjunta sobre variables $A$ , $B$ y $X$ :

• Los elementos de $C$ son la distribución marginal de $A$ y $B$ . Es decir, $C_{ij} = p(A=i,B=i)$ ;
• $a$ y $b$ son las siguientes distribuciones marginales de probabilidad condicional: $a_i = p(A=i \mathop{|} X=k)$ y $b_j = p(B=j \mathop{|} X=k)$ para un determinado $k$ ;
• Las cifras $\alpha_i C_{ij} \beta_j$ son los elementos de una distribución condicional (desconocida) $p(A=i,B=j\mathop{|}X=k)$ que es lo que estoy tratando de encontrar. (En realidad no es la verdadera distribución condicional sino una estimación de información mínima de la misma, por lo que tiene esta forma particular).

En términos del problema de álgebra lineal, esto significa que $a$ , $b$ y $C$ satisfacen las siguientes restricciones:

1. todos los elementos de $C$ , $a$ y $b$ son reales y están entre 0 y 1.
2. $\sum_{ij}C_{ij} = 1$
3. $\sum_{i}a_{i} = \sum_j b_j = 1$ .
4. $a$ y $b$ puede expresarse como las sumas de filas y columnas de una matriz $D$ con entradas reales en $[0,1]$ tal que $D_{ij}=0$ siempre que $C_{ij}=0$ y $\sum_{ij}D_{ij}=1$ . (Los elementos de $D$ son la "verdadera" distribución condicional $p(A=i,B=j\mathop{|}X=k)$ .)

Answer 1

Esto amplía mi comentario anterior, aunque sigue sin ser una respuesta completa.

Supondremos que $C$ , $a$ y $b$ son todos no negativos. Para cualquier subconjunto $S$ de filas, dejemos que $N(S)$ denotan el conjunto de columnas que tienen al menos una entrada no nula en alguna fila de $S$ . Del mismo modo, para un subconjunto $T$ de columnas, dejemos que $M(T)$ denotan el conjunto de filas que tienen al menos una entrada no nula en alguna columna de $T$ .

Una condición necesaria (la correspondiente a la de "permanente no nula" en el todo- $1$ caso) es que para todo $S$ y $T$ tenemos $$\sum_{i \in S} a_i \leq \sum_{j \in N(S)} b_j$$ $$\sum_{j \in T} b_j \leq \sum_{i \in M(T)} a_i.$$ (En el caso de la diagonal, esto se reduce a $a_i=b_i$ . Si todas las entradas de $C$ son positivos, esto se reduce a $\sum a_i = \sum b_j$ )

Sospecho que, en realidad, esta condición es suficiente además de necesaria. Esto está motivado en parte por la $1$ (donde es suficiente), y en parte en algunos ejemplos numéricos que ejecuté utilizando el análogo del algoritmo Sinkhorn-Knopp: Repetidamente

1. Escala cada fila para que las sumas de las filas sean iguales al valor requerido.
2. Escala cada columna para que las sumas de las columnas sean iguales al valor requerido.

Los ejemplos que probé tenían $a_i=b_i=i$ y $C$ que se toma como una $50 \times 50$ matriz donde la parte inferior derecha $k \times k$ menor se establece en $0$ y el resto de entradas son uniformes en $[0,1]$ .

Si $k=15$ entonces la condición anterior falla para $S=\{36,37,\dots,50\}$ y, como era de esperar, el algoritmo no converge. Si $k=14$ el algoritmo convergió con bastante rapidez en los ejemplos que probé (todas las sumas de filas dentro de $10^{-8}$ del valor correcto dentro de $100$ iteraciones).