Cómo caracterizar las rotaciones en $\mathbb{R}^n$?

Question

Estoy estudiando el rendimiento de un optimizador algoritmo para encontrar el $$ \textrm{argmin}_{x\in \mathbb{R}^n} f(x) \text{ donde } f : \mathbb{R}^n \rightarrow \mathbb{R} $$

Me gustaría probar cómo los cambios de rendimiento cuando puedo rotar el sistema de coordenadas. Necesito hacer esto de una manera sistemática , de modo que cada rotación tiene "la misma probabilidad".

En el $n=2$ de los casos esto es relativamente fácil, ya que cualquier 2-dimensional de rotación de la matriz puede ser escrita como:

\begin{pmatrix} cos(\phi) & sin(-\phi) \\ sin(\phi) & cos(\phi) \end{pmatrix}

La rotación se caracteriza por un único número $\phi$ así que puede muestra el $\phi$ uniforme (en forma equidistante) en $[-\pi; \pi]$.

En el $n=3$ caso de que las cosas se ponen más difíciles. Hay 3 ejes por los que me pueden girar, pero la composición de estas rotaciones no es conmutativa. Para que yo pudiera obtener resultados sesgados cuando me muestra estos 3 rotaciones de manera uniforme.

Yo estaba pensando en usar el de Euler, rotación del teorema:

en el espacio 3D, cualquiera de los dos sistemas de coordenadas Cartesianas con origen común están relacionados por una rotación alrededor de algún eje fijo

Esto significa que las rotaciones en 3d se caracteriza por un eje y un ángulo.

Así, pude muestra todos los posibles ejes de algunos de longitud fija y todas las posibles rotaciones alrededor de dicho eje. Pero este enfoque es muy trivial para generalizar a dimensiones arbitrarias.

¿Cómo puedo la muestra n-dimensional rotaciones de manera uniforme?

Answer 1

El espacio de todas las rotaciones en $\Bbb R^n$ es la Mentira de grupo $SO(n)$, y puede ayudar a leer el artículo de wikipedia sobre ellos. Ellos son normalmente representados como matrices, y también puede ser visto como un conjunto ordenado de vectores de la base que son mutuamente ortogonales. En vista de esto, es fácil generar un conjunto de: a grandes rasgos, de aplicar de Gram-Schmidt a un conjunto aleatorio de los vectores.

Para ser más precisos: generar un azar vector unitario $v_1\in\Bbb R^n$. La manera más fácil de hacer esto es tomar ventaja de la rotación de la invariancia de la distribución normal en $n$ dimensiones: si $x_1,\dots,x_n\sim{\cal N}(0,1)$, $u_1=(x_1,\dots,x_n)$ se distribuye en una rotación invariable manera, y $v_1=\frac {u_1}{|u_1|}$ es una manera uniforme elegido vector unitario.

A continuación, vamos a elegir al azar vector ortogonal a $v_1$. Usted puede hacer esto mediante la generación de otro al azar vector normal $u_2$, luego de restar la parte en la dirección de $v_1$, y normalizar para obtener $v_2$.

Continuar de esta manera, orthogonalizing vectores aleatorios con respecto a todos los vectores anteriores, para obtener el $v_1,\dots,v_{n-1}$. Sin embargo, $v_n$ requiere un poco de manejo especial. Sólo hay dos posibles la unidad de vectores que son ortogonales a todos los vectores anteriores, ya que no es sólo una de las dimensiones restantes. Si queremos una rotación, es decir, no es un reflejo, entonces debería ser nuestra elección $v_n=v_1\times v_2\times\dots\times v_{n-1}$, que define la orientación correcta y nos da un elemento de $SO(n)$. Si los reflejos no importa, a continuación, el mismo método que antes de que le dará un elemento de $O(n)$, el grupo ortogonal.

Como por la complejidad del cálculo, esto requiere de $n^2$ muestras de una distribución normal, así como aproximadamente el $n^2/2$ orthogonalizations de dimensión $n$ vectores, por lo que es la complejidad de la $O(n^3)$.

Answer 2

Usted podría hacerlo inductivamente como sigue:

1) elija un vector unitario $u$ uniformemente al azar en $\mathbb{R}^n$. Este vector será la imagen de $e_1$ en virtud de la rotación.

2) el Uso de Gram-Schmidt a la base $u,e_2,...,e_n$ para obtener una nueva base ortonormales $u,w_1,...,w_{n-1}$. Cambiar el signo de $w_1$ si es necesario para que usted tenga una orientada a la base, es decir, por lo que el determinante de la matriz $[u, w_1, ..., w_{n-1}]$ es positivo. Usted no tiene que calcular el determinante - a causa de la forma de Gram-Schmidt funciona el determinante es igual a la de $[u, e_2, ..., e_n]$, que es el signo de la primera componente de $u$. (Este proceso se producirá un error si el primer componente de $u$ es igual a $0$, pero que es una probabilidad cero de eventos). Deje $U$ denotar la matriz $[u, w_1, w_2, ..., w_{n-1}]$.

3) elija una rotación $A$ $\mathbb{R}^{n-1}$ al azar. A continuación, vamos a $\bar{A}$ $n \times n$ matriz cuya parte superior a la izquierda de la entrada es de $1$, cuya parte inferior derecha cuadrado es igual a $A$, y el resto de cuyas entradas son cero. Esquemáticamente:

$$\bar{A} = \left(\begin{matrix} 1 & 0 \\ 0 & A \end{matrix}\right)$$

A continuación, $\bar{A}U$ es una rotación aleatoria de $\mathbb{R}^n$.

Por cierto, yo no sé mucho acerca de la complejidad computacional por lo que si este es demasiado computacionalmente ineficiente, pido disculpas.