¿Cómo generar correctamente elementos aleatorios uniformemente distribuidos de SO(n)?

Question

Ya encontré alguna forma de producir dichas matrices a partir de SO(n) con un método llamado algoritmo de subgrupos, pero me gustaría que me aconsejaran sobre el método que utilicé. En ningún sitio he podido encontrar ningún documento relacionado con SO(n) directamente sino con O(n).

Para simplificarlo, genero un $(k-1) \times (k-1)$ matriz de rotación $\Gamma_{k-1}$ crear la matriz

$\left( \begin{array}{ccc} 1 & \cdots & 0 \\\ \vdots & \Gamma_{n-1} & \\\ 0 & & \end{array} \right)$

entonces encuentro una rotación $R$ que transforma la primera columna en un vector $v$ generado aleatoriamente como un punto de la unidad $k$ -esfera. A continuación, genere una nueva $k \times k$ matriz de rotación $\Gamma_k$ :

$\Gamma_{k} = R\left( \begin{array}{ccc} 1 & \cdots & 0 \\\ \vdots & \Gamma_{k-1} & \\\ 0 & & \end{array} \right)$

La inducción está haciendo todo el trabajo. En la práctica, o bien se empieza por un $1 \times 1$ con un solo elemento igual a 1, o se crea una primera matriz trivial $2 \times 2$ matriz de rotación con un ángulo tomado uniformemente de $[0,2\pi)$ que parece más directo. Me he saltado los detalles de cómo generar la matriz $R$ y el vector $v$ ya que al principio parecía inútil. En resumen $v$ es la normalización de un vector $v'$ qué elementos $v'_i \sim N(0,1)$ y $R$ se obtiene mediante una doble reflexión de Householder.

En la práctica esto parece una encarnación correcta del algoritmo de los subgrupos cuando el grupo es SO(n) pero quería comprobar con personas más inclinadas a las matemáticas que yo si no existía una forma más eficiente. Como he dicho, he encontrado algunos artículos que explican variaciones o mejoras del método original de Stewart $-$ que el algoritmo de subgrupos es una generalización $-$ en papeles de Anderson o Genz. Todos ellos se centraban en matrices ortogonales y me hubiera gustado transponer estas mejoras a matrices ortogonales especiales.

Ver:

• "La generación eficiente de matrices ortogonales aleatorias con una aplicación a los estimadores de condiciones" Stewart
• "Generación de matrices ortogonales aleatorias" Anderson
• "Métodos para generar matrices ortogonales aleatorias" Genz
• "El algoritmo de subgrupos para generar variables aleatorias uniformes" Diaconis

EDIT: por cierto, podría utilizar este algoritmo con n tan grande como 1000 y más

Así que la verdadera pregunta es (y no estoy muy seguro de cómo formularlo correctamente ya que tengo una grave falta de conocimiento en esa área), ¿existe un mapeo de O(n) a SO(n) que preserve la uniformidad?

Answer 1

Aquí hay una referencia relevante: Cómo generar matrices aleatorias a partir de los grupos compactos clásicos http://arxiv.org/abs/arXiv:math-ph/0609050

Answer 2

Puede extraer una respuesta del Artículo de Wikipedia (y el documento Diaconis-Shahshahani al que se hace referencia). En primer lugar, encuentre/escriba una función que produzca una distribución uniforme de puntos en una esfera unitaria (por ejemplo, divida una distribución normal en el espacio euclidiano por la norma). Entonces, si se tiene una distribución uniforme en $O(n-1)$ , incrustado en $O(n)$ de la forma que has descrito, puedes simplemente reflejar en (el hiperplano ortogonal a) tu vector unitario aleatorio para obtener una distribución uniforme en $O(n)$ .

Si se quiere un elemento distribuido uniformemente de $SO(n)$ debe comenzar su proceso utilizando la matriz 1 por 1 $(-1)^{n-1} \in O(1)$ en lugar de un elemento aleatorio de $\{ -1, 1\}$ . Eso arreglará el determinante.

Editar: Diaconis-Shahshahani probar que el método de los subgrupos que he descrito anteriormente produce una distribución que es uniforme con respecto a la medida de Haar en $O(n)$ . Si obtienes cosas extrañas en una comprobación visual, es casi seguro que el problema está en tu implementación.

El método que doy para obtener una distribución uniforme en $SO(n)$ es una alteración directa del método Diaconis-Shahshahani. En cada paso de su recursión, el determinante de su matriz se multiplica por $-1$ . Por lo tanto, el determinante que se obtiene al final sólo depende de la dimensión de la matriz final, y el determinante de la inicial $1 \times 1$ matriz. Si se elige que esta matriz inicial sea $1$ o $-1$ e iterar el proceso como antes, esto concentrará la distribución en uno de los cosets de $SO(n)$ en $O(n)$ pero será uniforme con respecto a la acción de traslación de $SO(n)$ . Por lo tanto, sólo hay que elegir la matriz inicial correcta (utilizando la fórmula que he proporcionado) para obtener una distribución uniforme en $SO(n)$ por este método.

Un método alternativo fue dado por José en los comentarios. Composición con cualquier determinante $-1$ toma la distribución uniforme en $SO(n)$ a la distribución uniforme en el coset no trivial en $O(n)$ y de vuelta. Hacer la recursión del método de subgrupos con paso inicial aleatorio, y si al final el determinante es $-1$ (lo que ocurrirá precisamente cuando su dimensión sea par), cambie un par de filas. Cualquier par de filas servirá.

Aquí está la respuesta a tu última pregunta: el mapa que conmuta las dos primeras filas de una matriz si y sólo si el determinante de esa matriz es $-1$ es un mapeo de $O(n)$ a $SO(n)$ que preserva la uniformidad.

Answer 3

El mejor algoritmo es el de G.W. Stewart

Stewart, G. W. , La generación eficiente de matrices ortogonales aleatorias con una aplicación a los estimadores de condiciones. (Con sección de mircofichas) SIAM J. Numer. Anal. 17, 403-409 (1980). ZBL0443.65027 .

Algoritmo: Sea $M$ sea $n\times n$ con i.i.d $N(0, 1)$ entradas. Sea $M=QR$ sea la factorización QR ( $Q$ ortogonal, $R$ triangular superior). Entonces $Q$ se distribuye uniformemente en $O(n)$ (proyecto a $SO(n)$ si quieres).