¿Qué ocurre si normalizo repetidamente y de forma alternativa las filas y columnas de una matriz?

Question

He aquí un algoritmo:

matriz de entrada M

(en el lugar)

dividir cada fila de M por su norma

dividir cada columna de M por su norma

Repita

¿Qué aspecto tendrá M después de que esto se haya repetido muchas veces? ¿Podemos decir algo sobre lo que hace este proceso?

Answer 1

He aquí una respuesta parcial:

1. El signo de cada entrada se mantiene bajo la normalización. Así, podemos suponer sin pérdida de generalidad que $M$ es no negativo a la entrada.

2. Por lo tanto, si $A_k$ es el cuadrado de la entrada del $k$ -ésima iteración $M_k$ entonces los iterados $A_k$ se normalizan mediante sumas de filas y sumas de columnas en lugar de las normas de las filas y columnas. Creo que es más fácil trabajar con $\{A_k\}$ que con $\{M_k\}$ .

3. Así, $A_k$ es estocástico de fila cuando $k$ es impar, o estocástico de columna cuando $n\ge2$ está en paz. Sin pérdida de generalidad, supongamos que $A_0$ (el cuadrado de la entrada de la inicial $M$ ) también es estocástica de columna.

4. Claramente, $A$ es un punto fijo si y sólo si es doblemente estocástico. (En otras palabras, en el escenario original, $M$ es un punto fijo si y sólo si es el producto Hadamard de un $\{-1,1\}$ -y una raíz cuadrada de entrada de una matriz doblemente estocástica. Además, como el conjunto de todas las matrices estocásticas de filas o columnas está acotado, cada una de $\{A_k\}_{k\ge0},\ \{A_{2k}\}_{k\ge0}$ et $\{A_{2k+1}\}_{k\ge0}$ siempre tiene una subsecuencia convergente.

5. Este procedimiento iterativo de normalización alternativo por sumas de filas y sumas de columnas se conoce como Algoritmo Sinkhorn-Knopp que se utiliza para determinar el " $DAD$ forma" en Teorema de Sinkhorn . Se sabe que $\{A_k\}_{k\ge0}$ converge si y sólo si $A_0$ contiene una diagonal positiva, es decir, si para alguna matriz de permutación $P$ todas las entradas de $A_0$ en las posiciones de los de $P$ son positivos. Véase

   R. Sinkhorn y P. Knopp (1967), Sobre las matrices no negativas y las matrices doblemente estocásticas Pacific J. Math, 21(2):343-348.

6. Así que, $\{A_k\}_{k\ge0}$ puede no converger. De hecho, pueden existir ciclos. Ejemplo: $$ \pmatrix{0&\frac12&0\\ 1&0&1\\ 0&\frac12&0} \rightarrow\pmatrix{0&1&0\\ \frac12&0&\frac12\\ 0&1&0} \rightarrow\pmatrix{0&\frac12&0\\ 1&0&1\\ 0&\frac12&0} $$ (Para obtener un ejemplo de $\{M_k\}_{k\ge0}$ , sólo hay que tomar las raíces cuadradas de entrada de las matrices anteriores).

7. También podemos modificar el ejemplo anterior para obatin un divergente $\{A_k\}_{k\ge0}$ que no contiene ningún ciclo. Primero, considere la siguiente secuencia: $$ A_0'=\pmatrix{1&\frac12\\ 0&\frac12} \rightarrow A_1'=\pmatrix{\frac23&\frac13\\ 0&1} \rightarrow A_2'=\pmatrix{1&\frac14\\ 0&\frac34} \rightarrow\cdots . $$ En otras palabras, supongamos que $$ A_{2k}'=\pmatrix{1&\frac1{2k+2}\\ 0&\frac{2k+1}{2k+2}}, \ A_{2k+1}'=\pmatrix{\frac{2k+2}{2k+3}&\frac1{2k+3}\\ 0&1} $$ para cada $k$ . Claramente, $A_k'$ converge a $I$ pero nunca alcanza un punto fijo o entra en cualquier ciclo. Ahora, consideremos la secuencia definida por $$ A_{2k}=\pmatrix{0&\frac12A_{2k}'&0\\ A_{2k}'&0&A_{2k}'\\ 0&\frac12A_{2k}'&0}, \ A_{2k+1}=\pmatrix{0&A_{2k+1}'&0\\ \frac12A_{2k+1}'&0&\frac12A_{2k+1}'\\ 0&A_{2k+1}'&0}. $$ Entonces $\{A_k\}_{k\ge0}$ es divergente y no contiene ciclos.

8. Sin embargo, no estoy seguro de que las secuencias de índice par o impar sean siempre convergentes. En todos los ejemplos anteriores, lo son. Los detalles del artículo mencionado u otros artículos relacionados con el algoritmo de Sinkhorn-Knopp pueden ser útiles a este respecto.

Answer 2

Añadiré la respuesta analítica de mvw con una numérica.

En primer lugar, implementé esta normalización de filas y columnas en Mathematica y lo aplicamos a una serie de datos generados aleatoriamente. $4\times 4$ matrices con entradas en $[-1,1]$ . El algoritmo converge, al parecer, con bastante rapidez. (Obsérvese que, aunque esto no es una prueba de convergencia, todos los términos de la secuencia, excepto posiblemente el primero, se encuentran en el conjunto acotado de matrices con entradas en $[-1,1]$ por lo que existe una subsecuencia convergente). La media de la norma matricial de la diferencia entre la 10ª iteración y la 100ª iteración era inferior a $0.001$ . Tras muchas iteraciones, las matrices eran, como cabía esperar, matrices con filas y columnas casi normalizadas.

Las matrices con filas y columnas exactamente normalizadas son, obviamente, puntos fijos de su algoritmo. Llamémoslas matrices unitarias fila-columna. Una pregunta interesante es: ¿existen puntos fijos de su algoritmo que no sean matrices fila-columna unitarias? Espero que si hay algún punto fijo de este tipo, sea inestable.

Para $2\times 2$ podemos ver fácilmente cuáles son las matrices fila-columna de la unidad. Dado el elemento superior izquierdo de la matriz, podemos hacer exactamente dos elecciones para el elemento superior derecho, y exactamente dos elecciones para el elemento inferior izquierdo. Por último, hay dos opciones para el elemento inferior derecho también. Por lo tanto, tenemos ocho subclases de matriz: $$\left(\begin{matrix} \cos t & \sin t\\ \sin t & \cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & \sin t\\ \sin t & -\cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & \sin t\\ -\sin t & \cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & \sin t\\ -\sin t & -\cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & -\sin t\\ \sin t & \cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & -\sin t\\ \sin t & -\cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & -\sin t\\ -\sin t & \cos t\end{matrix}\right),$$ $$\left(\begin{matrix} \cos t & -\sin t\\ -\sin t & -\cos t\end{matrix}\right).$$

He creado el siguiente e interesante diagrama:

Arriba se ve el círculo de la unidad con "pelos" que sobresalen. El extremo del pelo que no está junto al círculo unitario es la fila superior de un $2\times 2$ matriz aleatoria. El pelo es el camino que toma la fila superior de la matriz al converger al círculo unitario. Como puedes ver, la convergencia es sensible a las condiciones iniciales.

Answer 3

Usted tiene $$ F(A) = C(R(A)) $$ con $$ R(A) = \left(\prod_i \frac{1}{\lVert (e_i^T A)^T\rVert}\right) A = \left(\prod_i \frac{1}{\lVert A^T e_i\rVert}\right) A \\ C(A) = \left(\prod_i \frac{1}{\lVert Ae_i\rVert}\right) A $$ que parece una operación no lineal.

En la práctica, define una iteración $$ A_n = F^n(A) $$ que parece tener al menos el punto fijo $A = I$ .

Answer 4

El algoritmo que ha propuesto es esencialmente el mismo que el esquema de equilibrio matricial de Ruiz (ver http://www.numerical.rl.ac.uk/reports/drRAL2001034.pdf ).

En el álgebra lineal numérica, a menudo es beneficioso reducir la norma de cada fila y columna a 1 antes de resolverla, ya que esto tiende a hacer las soluciones más estables numéricamente. El equilibrio de Ruiz normaliza la norma máxima de cada fila y columna a 1. También demuestra que esto se aplica a cualquier $p$ -norma bajo ciertas condiciones.

Answer 5

Este proceso convergerá hacia una matriz R para la que tanto las líneas como las columnas están normalizadas y que comparten los mismos valores para $\forall (i,i',j,j') \frac{M_{i,j}M_{i',j'}}{M_{i,j'}M_{i',j}}=\frac{R_{i,j}R_{i',j'}}{R_{i,j'}R_{i',j}}$

La prueba de la conservación es inmediata. No tengo a mano la prueba de la convergencia. Pero en la práctica, utilizamos ese algoritmo y siempre ha convergido.