1
$\begingroup$

I don't know whether this question fits best on StackOverflow, Math.SE or CrossValidated; I am looking for a practical algorithm to generate uniformly distributed matrices in $SO(n,\mathbb{R})$ (aka uniformly random rotation matrices in dimension $n$). This answer goes into rather lengthy explanations without giving a clear "recipe", and Wikipedia provides a description for which I am struggling to find an implementation:

Stewart (1980) replaced this with a more efficient idea that Diaconis & Shahshahani (1987) later generalized as the "subgroup algorithm" (in which form it works just as well for permutations and rotations). To generate an (n + 1) × (n + 1) orthogonal matrix, take an n × n one and a uniformly distributed unit vector of dimension n + 1. Construct a Householder reflection from the vector, then apply it to the smaller matrix (embedded in the larger size with a 1 at the bottom right corner).

As far as I understand, this would be equivalent to (but more efficient than) the following (Matlab language):

Q = randn(n); % uniformly random entries
Q = Q * diag(sign(diag(Q))); % flip column signs to have positive diagonal
Q = orth(Q); % orthogonalise
Q = Q / det(Q)^(1/n); % unit determinant

I am asking: i) whether the previous indeed generates uniformly distributed matrices in $SO(n)$; and ii) whether someone could provide a practical implementation of the algorithm described on Wikipedia (quoted above).

$\endgroup$
  • $\begingroup$ This shoud be the same as picking a random point on the sphere $S^n$. Or the same as picking $n-1$ Euler angles (en.wikipedia.org/wiki/Euler_angles) uniformly at random. $\endgroup$ – Jack D'Aurizio Feb 25 '17 at 17:46
  • $\begingroup$ I don't think it is the same as picking random point on $S^n$; the idea then is to realise that the level sets of isotropic normal distributions are n-spheres, and so normalised samples from a normal distribution are uniformly distributed on the sphere (exploiting the "isotropy"). How does that relate to uniformly random rotations? $\endgroup$ – Sheljohn Feb 25 '17 at 17:57
  • 1
    $\begingroup$ A random point on $S^n$ gives an axis of rotation and an element of $SO(n)$ once a further angle is chosen, doesn't it? $\endgroup$ – Jack D'Aurizio Feb 25 '17 at 18:01
  • $\begingroup$ Now I get it :) Yes of course you are right. So then we are looking at higher-dimensional counterparts of quaternions? $\endgroup$ – Sheljohn Feb 25 '17 at 18:03
  • $\begingroup$ I guess so, essentially. The main issue is that not every element of $SO(4)$ is a rotation around an axis. The last paragraph en.wikipedia.org/wiki/… is relevant. $\endgroup$ – Jack D'Aurizio Feb 25 '17 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.