that can treat 10K dimensions or higher. However, this method folds feature vectors and bilinearly rotates them in the folded space. It is unable to treat all of the Special Orthogonal group (Rotational group) $SO(n)$. There is still no linear high dimensional binary hashing method that can directly treat $SO(n)$.

In this paper, we propose a new highly efficient linear binary hashing method. Our method is inspired by Isotropic Hashing [@Kong2012]. We found out its natural extension. First, we study the meaning of isotropic transformation analytically. Then we develop a efficient isotropic hashing algorithm and its extension using trade-off relationship between isotropy and entropy. Recently proposed Sparse Isotopic Hashing method[@Sato2013] produces sparse rotational matrices that yield isotropic variances; however the learning of high-dimensional rotational matrices is not feasible in practice. Our main contributions are, **1: State-of-the-art computational cost and accuracy**

Our algorithm takes $\mathrm{O}(n \log n)$ encoding cost for $n$ dimensional features. The previously known state-of-the-art method BPBC requires $\mathrm{O}(n^2/d + nd)$ (typically $d=128$, with no dimension reduction case) cost. We show that the proposed algorithm is more accurate than BPBC. Moreover, it is remarkably faster in learning phase. The main cost consuming point of our algorithm is calculation of 