$\mathrm{O}(n \log_2 n)$ fill-ins using pairwise isotropic rotation, although original Isotropic Hashing [@Kong2012] needs dense transformation matrix with $\mathrm{O}(n^2)$ fill-ins.

In two-dimensional space, there are only two isotropic transformations. It corresponds to $\theta = \pi/4, 3\pi/4$ in equation (\[eq:r-theta\_representation\_of\_2d\_gauss\]). From the symmetry of the gaussian distribution, it is enough to consider $\theta = \pi/4$. For any two-dimensional variance-covariance matrix $\Sigma$, the rotation matrix that makes variances isotropic is $$\begin{aligned}
 \label{eq:iso_rotation}
R = 
\begin{pmatrix}
\cos \theta_{\text{iso}} & -\sin \theta_{\text{iso}} \\
\sin \theta_{\text{iso}} & \cos \theta_{\text{iso}}
\end{pmatrix}
, \quad \theta_{\text{iso}} = \tan^{-1} \left( \frac{1}{2} \frac{\sigma_{11} - \sigma_{22}}{\sigma_{12}} \right).\end{aligned}$$

To develop isotropic transformation for full dimension, we define “basic isotropic rotation”. It consists of three steps. First step is to sort dimensions by diagonal elements of variance-covariance matrix in descending order. Second step is to create pairs of dimensions as $(1, n), (2, n-1), \cdots$. Third step is taking isotropic rotation (\[eq:iso\_rotation\]) for each pairs. The set of processes is denoted by a permutation (sorting) matrix and a rotational matrix with $2n$ fill-ins. This transformation, which we call it “basic isotropic rotation”in what follows, make variances pairwise isotropic. Then we apply above transformation sequentially. Applying the transformation two times make variances quadruple isotropic, 