La media aritmética-geométrica para matrices simétricas definidas positivas

Question

Hace un tiempo, quise ver si la noción de la media aritmética-geométrica podría extenderse a un par de matrices simétricas positivas definidas. (Sólo he considerado las matrices definidas positivas, ya que la noción de raíz cuadrada de la matriz es un poco intrincada para otros tipos de matrices).

Esperaba que surgieran algunas complicaciones, ya que, a diferencia de la multiplicación escalar, la multiplicación matricial no es conmutativa. Otra complicación sería que el producto de dos matrices simétricas no tiene por qué ser simétrico (aunque se mantiene la definición positiva, por lo que se puede seguir hablando de una raíz cuadrada de matriz principal).

Por analogía con el AGM escalar, consideré la iteración

$$\mathbf A_0=\mathbf A \; ; \; \mathbf B_0=\mathbf B$$ $$\mathbf A_{i+1}=\frac12(\mathbf A_i+\mathbf B_i) \; ; \; \mathbf B_{i+1}=\sqrt{\mathbf A_i \mathbf B_i}$$

He puesto en marcha un corto Mathematica rutina:

matAGM[u_, v_] := First[FixedPoint[
      {Apply[Plus, #]/2, MatrixPower[Apply[Dot, #], 1/2]} &, {u, v}]] /;
      MatrixQ[u, InexactNumberQ] && MatrixQ[v, InexactNumberQ]

y decidí probarlo con matrices de SPD generadas aleatoriamente.

(Una nota numérica: Mathematica utiliza la descomposición de Schur numéricamente estable en el cálculo de funciones matriciales como la raíz cuadrada de la matriz).

Encontré que para todos los pares de matrices SPD generados aleatoriamente que probé, el proceso era convergente (aunque la tasa de convergencia no es aparentemente tan rápida como la AGM escalar). Como era de esperar, el orden es importante: matAGM[A, B] y matAGM[B, A] no suelen ser iguales (y ambos resultados son unsymmetric ) a menos que A y B conmutan (para el caso especial de la diagonal A y B el resultado es la matriz diagonal cuyas entradas son las medias aritméticas-geométricas de las entradas correspondientes del par).

Ahora tengo tres preguntas:

1. ¿Cómo puedo demostrar o refutar que este proceso converge para cualquier par de matrices SPD? Si es convergente, ¿cuál es la tasa de convergencia?

2. ¿Existe alguna relación entre matAGM[A, B] y matAGM[B, A] si las dos matrices A y B ¿no se desplaza?

3. ¿Existe alguna relación entre esta media aritmético-geométrica matricial y la media aritmético-geométrica escalar habitual? ¿Tendrían algo que ver, por ejemplo, las medias aritmético-geométricas de los valores propios de las dos matrices?

---

(añadido el 8/12/2011)

Indagando más me he convencido de que, efectivamente, debería considerar la formulación de la media geométrica por Pusz y Woronowicz :

$$\mathbf A\#\mathbf B=\mathbf A^{1/2}(\mathbf A^{-1/2}\mathbf B\mathbf A^{-1/2})^{1/2}\mathbf A^{1/2}$$

como más natural; la prueba de convergencia se simplifica entonces, como se muestra en el artículo que Willie enlazó. Sin embargo, todavía me pregunto por qué la formulación original "no natural" parece ser convergente (o bien, me gustaría ver un par de matrices SPD que causan problemas para la iteración no natural). También me interesa saber cómo pueden aparecer aquí las integrales elípticas, al igual que en la versión escalar de la AGM.

Answer 1

¡Buena pregunta!

Lo que sigue a continuación no es realmente una respuesta, pero es demasiado largo para que quepa como comentario. Sería útil si pudieras escribir tu algoritmo de Mathematica en notación matemática tradicional para que sea más fácil ver lo que está pasando.

En primer lugar, estoy seguro de que conoce las definiciones estándar de los medios matriciales. Las recuerdo a continuación en beneficio de otros que consideren su pregunta.

1. La media aritmética es: $(A+B)/2$ como se esperaba. Satisface varias de las propiedades estándar deseables de una media de matrices spd (no negativa, si $A \le B$ entonces $A \le AM(A,B) \le B$ etc.)

2. La media geométrica estándar es: $$GM(A,B) = A^{1/2}(A^{-1/2}BA^{-1/2})^{1/2}A^{1/2}$$ Esta elección particular de GM satisface: $GM(A,B)=GM(B,A)$ .

Ahora bien, si se itera el AGM, utilizando las dos definiciones anteriores de los medios, entonces creo que se puede demostrar la convergencia, etc. -aunque tal vez haya que recurrir a algún tipo de teorema de punto fijo. Si tengo tiempo, pensaré más en esto.

Answer 2

Utilizaré la caracterización de la media geométrica dada por Slowsolver. Como mencioné en un comentario a su respuesta, la media geométrica $GM(A,B)$ es el punto medio geodésico correspondiente a la métrica de Riemann en el espacio de matrices simétricas positivas definidas con

$$ g(X,Y) = \mathop{tr}(A^{-1}XA^{-1}Y)~,\quad X,Y\in T_A(SPD) $$

donde el espacio tangente $T_A(SPD)$ es el espacio de las matrices simétricas. Esta interpretación tiene la siguiente ventaja: tanto el AM como el GM son "invariantes de traslación". Sea $P$ sea una matriz no singular, entonces $AM(PAP^T,PBP^T) = P(AM(A,B))P^T$ trivialmente, y de forma similar para $GM$ usando eso $$g_A(X,Y) = g_{PAP^T}(PXP^T, PYP^T)$$ para que una geodésica $\gamma$ unirse a $A,B$ se convierte en una geodésica $P\gamma P^T$ unirse a $PAP^T$ y $PBP^T$ . Conjugando primero con $P = A^{-1/2}$ Podemos suponer que WLOG $A = I$ . Conjugando entonces con una matriz ortogonal adecuada $O$ para diagonalizar $B$ Podemos suponer que WLOG $A = I$ y $B$ es diagonal.

El resultado sobre la convergencia se deduce ahora de la convergencia de la AGM para el caso de una sola variable real.

Para sus preguntas específicas:

1. La tasa de convergencia es la misma que en el caso escalar, hasta un factor constante que depende de los valores iniciales de $A,B$ (que determina $P$ ).
2. En esta definición $GM(A,B) = GM(B,A)$ Así que la pregunta es discutible.
3. Esto es, en cierto sentido, la generalización natural del caso escalar. Obsérvese que la media geométrica escalar corresponde al punto medio geodésico para el grupo de Lie multiplicativo $(\mathbb{R}_+,\times)$ con la métrica invariante. Una primera generalización es al grupo abeliano de Lie $\mathbb{R}^k_+$ con multiplicación por componentes. (Esto corresponde al caso diagonal.) Lo que mostramos anteriormente es que la secuencia completa de AGM para matrices iniciales arbitrarias de SPD $A$ y $B$ está contenido, hasta la conjugación por $P\cdot P^T$ en uno de esos casos abelianos. Nótese que esto está ligeramente menos relacionado con los valores propios per se, ya que la transformación que utilizamos arriba no preserva los valores propios.

---

EDIT: Se me acaba de ocurrir hacer una búsqueda bibliográfica. En Lawson, J. D. & Lim, Y. "The geometric mean, matrices, metrics, and more". Amer. Math. Monthly, 2001, 108, 797-812 En las secciones 2 y 3 se derivan muchas propiedades de esta media geométrica en las matrices del DSP. En particular, la propiedad crucial (como comenta slowsolver más adelante) de poder establecer $A = I$ y $B$ diagonal, es el contenido del Lemma 3.1 de ese trabajo. A continuación, la desigualdad armónica-geométrica-aritmética-media para las matrices SPD. Empezando por eso y jugando con las propiedades de monotonicidad, es de suponer que también se obtiene otra prueba del resultado de convergencia.

Answer 3

Quizás quieras echar un vistazo al ejercicio 6 de la página 223 de Borwein y Borwein. (Supongo que cualquiera que pregunte sobre la AGM está familiarizado con este libro.) Allí se discute una versión matricial de la AGM y se pide que se demuestre una conexión entre ella y una integral elíptica.

También dan como referencia un artículo de Stickel de 1985: "Fast compuation of Matrix Exponentials and Logarithms". El nombre de la revista es Analysis.

Answer 4

Siento poner esto en una respuesta y no en un comentario, pero soy demasiado nuevo para comentar tu pregunta. Mis pensamientos para probar que este proceso converge (pregunta 1.) estaban en la línea de:

1. $A\,\&\,B$ ambos SPD $\implies AB$ y $A+B$ también son SPD
2. Si $A$ y $B$ son simétricos $n\times n$ matrices, $A$ de los valores propios $\{\lambda_n^A\} \subset [0, a]$ y $B$ 's $\{\lambda_n^B\} \subset [0, b]$ , entonces los valores propios $\{\lambda_N^{AB}\}$ de $AB$ son $\subset [0, ab]$ . Véase, por ejemplo, este discusión. Además, $\{\lambda_n^{A+B}\} \subset [0, a + b]$ ; ver Terry Tao's notas en esto.
3. Creo que la convergencia podría seguirse examinando la AGM de los valores propios; es decir, mirar $AGM(\lambda_k^A, \lambda_k^B)$ para $k = 1,\ldots,n$ . La diferencia entre las medias aritmética y geométrica se hace arbitrariamente pequeña, y los valores propios son todos positivos; esta iteración conduce a una secuencia de matrices SPD cuyo mayor valor propio $\lambda_1 \to 0$ Así que la AGM en cuestión sí converge (tal vez).

No estoy seguro, pero pensé en dar mi $\$ 0.02$. Como dijo @Slowsolver, ¡buena pregunta! También secundo la petición de escribir tu algoritmo en una notación más tradicional, ya que no estoy tan versado en Mathematica como otros. Por último, podría añadir la etiqueta "álgebra lineal numérica" a tu pregunta.

---

EDIT: resulta que me equivoqué en la parte 1, como otros me han señalado. Mis disculpas. A la luz de sus correcciones, puede tener sentido utilizar la media geométrica dada por SlowSolver.

---