a variance-covariance matrix. We only need $\mathrm{O}(n^2 \log n)$ computational cost in learning iteration loop, whereas BPBC requires $\mathrm{O}(n^2 \log n)$ in each iteration step. Therefore it is practically faster than BPBC, although total computational cost of learning has the same order $\mathrm{O}(mn^2)$ in our algorithm and BPBC with $m$ training data size. **2: Analytical treatment of hashing criteria**

Typical criteria for measuring hashing performance are quantization error, variance of each bit, and entropy. To the author’s knowledge, analytical treatment of these criteria has not been well studied yet. We show an analytical result, and a set of algorithms derived naturally from the result. The analytical calculation is mainly based on gaussian distribution. That does not mean the proposed algorithm is only applicable to gaussian-distributed data. Because any non-gaussian distributions can be expanded around gaussian [@Kolassa2006], assuming gaussian distribution means taking lowest order of expansion. As will be discussed below, lowest order approximation leads enough hashing accuracy and yields extremely efficient algorithm.

Theoretical Background {#sec:theoretical_background}
======================

Quantization Error for Binary Hashing
-------------------------------------

Along with clustering methods such as k-means clustering, most binary hashing algorithms aim at minimizing quantization error between binarized codes and original feature vectors[@Gong2013b; @Gong2013]. In this study, 