Random rotations

May 17, 2021 — December 1, 2021

Suspiciously similar content

Placeholder for random measures on the special orthogonal group, which encodes random $d$ -dimensional rotations. A special type of matrix random variate if you’d like.

1 Uniform random rotations

Key word: Haar measure.

Chatterjee and Meckes (2008) gives us a useful lemma describing the moments of a random rotation:

If $U = {[u_{i j}]}_{i, j = 1}^{n}$ is an orthogonal matrix distributed according to Haar measure, then $E [\prod u_{i j}^{k_{i j}}]$ is non-zero if and only if the number of entries from each row and from each column is even. Second and fourth-degree moments are as follows:

For all $i, j$ , $E [u_{i j}^{2}] = \frac{1}{n}$
For all $i, j, r, s, α, β, λ, μ$ , $\begin{aligned} E [u_{i j} u_{r s} u_{α β} u_{λ μ}] \\ = - \frac{1}{(n - 1) n (n + 2)} [δ_{i r} δ_{α λ} δ_{j β} δ_{s μ} + δ_{i r} δ_{α λ} δ_{j μ} δ_{s β} + δ_{i α} δ_{r λ} δ_{j s} δ_{β μ} \\ + δ_{i α} δ_{r λ} δ_{j μ} δ_{β s} + δ_{i λ} δ_{r α} δ_{j s} δ_{β μ} + δ_{i λ} δ_{r α} δ_{j β} δ_{s μ}] \\ + \frac{n + 1}{(n - 1) n (n + 2)} [δ_{i r} δ_{α λ} δ_{j s} δ_{β μ} + δ_{i α} δ_{r λ} δ_{j β} δ_{s μ} + δ_{i λ} δ_{r α} δ_{j μ} δ_{s β}] \end{aligned}$

Let $H \in O_{n}$ be distributed according to Haar measure. Then $E [h_{i j} h_{k l} h_{m n} h_{p q}]$ is only non-zero if there are an even number of entries from each row and each column. Fourth-order mixed moments are as follows. (i) $E [h_{11}^{2} h_{12}^{2}] = \frac{1}{n (n + 2)}$ (ii) $E [h_{11}^{2} h_{22}^{2}] = \frac{n + 1}{(n - 1) n (n + 2)}$ (iii) $E [h_{11} h_{12} h_{21} h_{22}] = \frac{- 1}{(n - 1) n (n + 2)}$ , and (iv) $E [(h_{i 1} h_{i^{'} 2} - h_{i 2} h_{i^{'} 1}) (h_{j 1} h_{j^{'} 2} - h_{j 2} h_{j^{'} 1})] = \frac{2}{n (n - 1)} [δ_{i j} δ_{i^{'} j^{'}} - δ_{i j^{'}} δ_{i^{'} j}]$ , where $i \neq i^{'}$ and $j \neq j^{'}$

2 Tiny random rotations

Notation: $\oplus$ is the block direct sum.

2.1 Random Givens rotation

Givens rotations are useful. We can parameterize a Givens rotation $A^{(t)}$ by either an angle $t = θ$ or a magnitude $t = ϵ = \sin θ$ . The latter is slightly easier. Formally, a Givens rotation can be defined in any dimension $d \geq 2$ by padding it with zeros and adding it to an identity matrix, but all the action happens over 4 entries, so we can learn how it works by examining a minimal $2 \times 2$ rotation as a perturbation of the identity.

For $- 1 \leq t \leq 1$ fixed, let us define a rotation $\begin{aligned} A^{(t)} & = [\begin{array}{cc} \sqrt{1 - t^{2}} & t \\ - t & \sqrt{1 - t^{2}} \end{array}] \\ = I_{2} + [\begin{array}{cc} - \frac{t^{2}}{2} + δ & t \\ - t & - \frac{t^{2}}{2} + δ \end{array}] \end{aligned}$ where $δ$ is a deterministic constant and $δ = O (t^{4}) .$

Informally (because I do not have space or will to track lots of boring remainder terms) we note that for some fixed $x = [x_{1} x_{2}]^{⊤}$ we have $\begin{aligned} A^{(t)} x x^{⊤} A^{(t)}^{⊤} & \approx (\begin{array}{cc} x_{1}^{2} + 2 t x_{1} x_{2} + t^{2} (- x_{1}^{2} + x_{2}^{2}) & x_{1} x_{2} - 2 t^{2} x_{1} x_{2} + t (- x_{1}^{2} + x_{2}^{2}) \\ x_{1} x_{2} - 2 t^{2} x_{1} x_{2} + t (- x_{1}^{2} + x_{2}^{2}) & - 2 t x_{1} x_{2} + x_{2}^{2} + t^{2} (x_{1}^{2} - x_{2}^{2}) \end{array}) \\ = x x^{⊤} + (\begin{array}{cc} 2 x_{1} x_{2} & - x_{1}^{2} + x_{2}^{2} \\ - x_{1}^{2} + x_{2}^{2} & - 2 x_{1} x_{2} \end{array}) t + (\begin{array}{cc} - x_{1}^{2} + x_{2}^{2} & - 2 x_{1} x_{2} \\ - 2 x_{1} x_{2} & x_{1}^{2} - x_{2}^{2} \end{array}) t^{2} \end{aligned}$

If we want this to work in a higher dimension, we pad it like this: $\begin{aligned} A^{(t)} & = [\begin{array}{cc} \sqrt{1 - t^{2}} & t \\ - t & \sqrt{1 - t^{2}} \end{array}] \oplus I_{d - 2} \\ = I_{d} + [\begin{array}{cc} - \frac{t^{2}}{2} + δ & t \\ - t & - \frac{t^{2}}{2} + δ \end{array}] \oplus 0_{d - 2} \end{aligned}$

Now, let us consider how to randomise these. If we fix two axes and a random $t$ we can construct a random Givens rotation. Suppose $E [t] = 0$ , $var (t) = ε^{2}$ small, and proceeding to do a sloppy Taylor expansion (which will, I assert, not matter in practice when take limits as $t \to 0$ but one should check this to be rigorous). $\begin{aligned} E [A^{(t)} x] & \approx E [(\begin{array}{c} x_{1} + t x_{2} - \frac{t^{2} x_{1}}{2} \\ x_{2} - t x_{1} - \frac{t^{2} x_{2}}{2} \end{array})] \\ = x - E [t^{2}] x . \end{aligned}$

$\begin{aligned} E [A^{(t)} x x^{⊤} A^{(t)}^{⊤}] & \approx E [x x^{⊤} + (\begin{array}{cc} 2 x_{1} x_{2} & - x_{1}^{2} + x_{2}^{2} \\ - x_{1}^{2} + x_{2}^{2} & - 2 x_{1} x_{2} \end{array}) t + (\begin{array}{cc} - x_{1}^{2} + x_{2}^{2} & - 2 x_{1} x_{2} \\ - 2 x_{1} x_{2} & x_{1}^{2} - x_{2}^{2} \end{array}) t^{2}] \\ = x x^{⊤} + (\begin{array}{cc} - x_{1}^{2} + x_{2}^{2} & - 2 x_{1} x_{2} \\ - 2 x_{1} x_{2} & x_{1}^{2} - x_{2}^{2} \end{array}) E [t^{2}] \end{aligned}$

2.2 Doubly Random Givens rotation

If each Givens rotation is over a pair of distinct axes drawn uniformly at random, this will also give us a random rotation. Bookkeeping for these could be irritating, but let us see. wlog we can generate these by choosing the axes $i \sim U ({1, 2, \dots, n - 1}, j \sim U ({i + 1, i, \dots, n} .$

2.3 Random rotation in an isotropic direction

Suppose $Q$ is a Haar-distributed (i.e. uniform) random rotation. Then we can make a tiny incremental rotation using a construction of Chatterjee and Meckes (2008), by applying a small Given rotation in a randomly rotated coordinate frame. The result is a rotation in a random direction, but not far in that direction.

Then $Q^{ε} := Q A_{ε} Q^{⊤}$ is a small random rotation. What can we say about this guy? Let $Q_{1 : 2}$ be the $d \times 2$ matrix made of the first two columns of $Q$ and $C_{2} = [\begin{array}{cc} 0 & 1 \\ - 1 & 0 \end{array}]$ . Then $Q^{ε} = ϵ [- (\frac{ϵ}{2} + ϵ^{- 1} δ) Q_{1 : 2} Q_{1 : 2}^{⊤} + Q_{1 : 2} C_{2} Q_{1 : 2}^{⊤}]$ and $ϵ^{- 1} δ = O (ϵ^{3})$ .

Once again referring to Chatterjee and Meckes (2008) we see that the matrix $M = {[m_{i j}]}_{i, j = 1}^{n} = M_{1 : 2} C_{2} M_{1 : 2}^{⊤}$ satisfies $m_{i j} = u_{i 1} u_{j 2} - u_{i 2} u_{j 1} .$ For all $i, j, ℓ, p$ , $E [m_{i j} m_{ℓ p}] = \frac{2}{n (n - 1)} [δ_{i ℓ} δ_{j p} - δ_{i p} δ_{j ℓ}]$ By the lemma on expectations of random rotations, $E [Q_{1 : 2} Q_{1 : 2}^{⊤}] = \frac{2}{n} I$ .

\[\begin{aligned} \mathrm{Q}^{\varepsilon}-\mathrm{I} &\approx \mathrm{Q}\left( \mathrm{I}_{d} +\left[ $\begin{array}{cc} - \frac{ε^{2}}{2} & ε \\ - ε & - \frac{ε^{2}}{2} \end{array}$ \right] \oplus 0_{d-2} \right)\mathrm{Q}^\top-\mathrm{I\ &=\mathrm{Q}\mathrm{Q}^\top +\mathrm{Q}\left(\left[ $\begin{array}{cc} - \frac{ε^{2}}{2} & ε \\ - ε & - \frac{ε^{2}}{2} \end{array}$ \right] \oplus 0_{d-2}\right)\mathrm{Q}^\top -\mathrm{I\ &=\mathrm{Q}\left(\left[ $\begin{array}{cc} - \frac{ε^{2}}{2} & ε \\ - ε & - \frac{ε^{2}}{2} \end{array}$ \right] \oplus 0_{d-2}\right)\mathrm{Q}^\top\ &=\text{TBD} \end{aligned}\]

TBC.

3 Sparse

We could desire a random rotation be sparse in a few senses, e.g. “ a random rotation in $D$ dimensions described by $N ≪ D$ Givens rotations.” Things that fit this description are fairly easy to generate: we generate a small, possibly random, number of Givens rotations.

A useful context for me is to take something that is expected to be a rotation, but whose realisations are sparse.

4 References

Barthe, Guedon, Mendelson, et al. 2005. “A Probabilistic Approach to the Geometry of the

ℓ_{p}^{n}

-Ball.” The Annals of Probability.

Chatterjee, and Meckes. 2008. “Multivariate Normal Approximation Using Exchangeable Pairs.” arXiv:math/0701464.

Chikuse. 2003. “High Dimensional Asymptotic Theorems.” In Statistics on Special Manifolds.

Chikuse, and 筑瀬. 2003. Statistics on Special Manifolds.

Christensen. 1970. “On Some Measures Analogous to Haar Measure.” MATHEMATICA SCANDINAVICA.

Kaneko, Fiori, and Tanaka. 2013. “Empirical Arithmetic Averaging Over the Compact Stiefel Manifold.” IEEE Transactions on Signal Processing.

Kar, and Karnick. 2012. “Random Feature Maps for Dot Product Kernels.” In Artificial Intelligence and Statistics.

Meckes. 2012. “Approximation of Projections of Random Vectors.” Journal of Theoretical Probability.

Stam. 1982. “Limit Theorems for Uniform Distributions on Spheres in High-Dimensional Euclidean Spaces.” Journal of Applied Probability.