rotation ($\theta_{\text{pca}}$ given in Eq. (\[eq:pca\_rotation\])) is applied to each pair. This procedure is called “basic PCA rotation”. Although it is not obvious how many times the basic PCA rotation should be applied, the experiments discussed in succeeding section show that $\mathrm{O}(\log_2 n)$ times rotations attains maximal retrieval accuracy. So the increasing of the number of fill-ins of the transformation matrix is very little.

Relation with Major Existing Strategies
---------------------------------------

The proposed algorithm introduces a novel strategy, in which the transformation matrix is expressed as a factored form of pairwise rotational matrices. For constructing each rotation, only the variance-covariance matrix is used. In contrast, some existing linear binary hashing algorithms (such as ITQ) use an objective function that is directly calculated from the data (e.g, quantization error due to discretization). These data-dependent objective functions capture non-gaussian property of the distribution of data.

On the other hand, an arbitrary probability distribution function has an expansion series with the lowest order term given by a gaussian distribution. Such expansion is called Edgeworth expansion [@Kolassa2006]. From this viewpoint, it can be regarded as the lowest-order approximation is taken in our algorithm, whereas ITQ and other data-dependent methods consider higher order non-gaussian terms. Omission 