Simultaneous Compression and Quantization:
A Joint Approach for Efficient Unsupervised Hashing
Tuan Hoang∗
∗

Thanh-Toan Do+
Dang-Khoa Le-Tan∗
Ngai-Man Cheung∗
Singapore University of Technology and Design (SUTD)

arXiv:1802.06645v1 [] 19 Feb 2018

nguyenanhtuan hoang@mymail.sutd.edu.sg, {letandang khoa, ngaiman cheung}@sutd.edu.sg
+

The University of Adelaide

thanh-toan.do@adelaide.edu.au

Abstract

very challenging to simultaneously satisfy all three requirements, especially, under the binary constraint which leads
to an NP-hard mixed-integer optimization problem.
The proposed hashing methods in literature can be
categorized into data-independence [9, 17, 22] and datadependence; in which, the latter recently receives more attention in both (semi-)supervised [16, 18, 19, 20, 25] and
unsupervised [2, 4, 5, 10, 12, 13] manners. However, in
practice, labeled datasets are limited and costly; hence,
in this work, we focus only on the unsupervised setting.
We refer readers to recent surveys [11, 29, 30, 31] for
more detailed reviews of data-independent/dependent hashing methods.

The two most important requirements for unsupervised
data-dependent hashing methods are to preserve similarity in the low-dimensional feature space and to minimize
the binary quantization loss. Even though there are many
hashing methods that have been proposed in the literature,
there is room for improvement to address both requirements
simultaneously and adequately.
In this paper, we propose a novel approach, named
Simultaneous Compression and Quantization (SCQ), to
jointly learn to compress and binarize input data in a single formulation. A simple scale pre-processing is introduced to help to preserve data similarity. With this approach, we introduce a loss function and its relaxed version, termed Orthonormal Encoder (OnE) and Orthogonal
Encoder (OgE) respectively, which involve the challenging binary and orthogonal constraints. We then propose
novel algorithms that can effectively handle these challenging constraints. Comprehensive experiments on unsupervised image retrieval show that our proposed methods consistently outperform other state-of-the-art hashing methods
while still being very computationally-efficient.

1.1. Related works
The most relevant work to our proposal is Iterative Quantization (ITQ) [10], which is a very fast and competitive
hashing method. The fundamental of ITQ is two folds.
Firstly, to achieve low-dimensional features, it uses the
well-known Principle Component Analysis (PCA) method.
PCA maximizes the variance of projected data and keeps dimensions pairwise uncorrelated. Hence, the low-dimension
data, projected using the top PCA component vectors, can
preserve data similarity well. Secondly, minimizing the binary quantization loss using an orthogonal rotation matrix
strictly maintains the data pairwise distance. As a result,
ITQ learns binary codes that can highly preserve the local structure of the data. However, optimizing these two
steps separately, especially when no binary constraint is
considered in the first step, i.e., PCA, leads to suboptimal
solutions. In contrast, our proposed formulation optimizes
the projection variation and the quantization loss simultaneously.
Other works relevant to our proposed method are Binary Autoencoder (BA) [2], Relaxed Binary Autoencoder
(RBA) [6] and UH-BDNN [4]. In these methods, the authors proposed to combine the data dimension reduction
and binary quantization into a single step by using encoder

1. Introduction
For decades, image hashing has been an active research
field in the vision community [1, 10, 32, 35]. Under specific
conditions [10], image hashing has great advantages in storage and computation speed for similarity search/retrieval,
especially in the application of Content-based Image Retrieval [7, 3, 14]. Firstly, the binary code should be short
so as to the whole hash table can fit in the memory. Secondly, the binary code should preserve the similarity, i.e.,
(dis)similar images have (dis)similar hashing codes in the
Hamming distance space. Finally, the algorithm to learn
parameters should be fast and for unseen samples, the hashing method should produce the hash codes efficiently. It is
1

of autoencoder, while the decoder encourages (dis)similar
inputs map to (dis)similar binary codes. However, the reconstruction criterion is not a direct way for preserving the
similarity [4]. Additionally, even achieving very competitive performances, UH-BDNN is based on the deep neural
network (DNN); hence, it is difficult to produce the binary
code computationally-efficiently.

1.2. Contribution
In this work, to address the problem of learning to preserve data affinity in low-dimension binary codes, we first
propose a novel loss function to learn a single linear transformation under the column semi-orthonormal constraint1
in the unsupervised manner that compresses and binarizes
the input data jointly. While this linear transformation generally does not guarantee to retain high variance components of the dataset, we secondly show that by applying
an appropriate scale pre-processing, this linear transformation can be learned to retain high variance components, i.e.,
well preserve the local structure of data. We then propose
to relax the column semi-orthonormal constraint to column
semi-orthogonal constraint that not only helps to gain extra
retrieval performances but also significantly improves the
training time.
Our proposed loss functions are confronted with two
main challenges including the binary constraint, which is
the traditional and well-known difficulty of hashing problem [1, 10, 32], and the orthonormal/orthogonal constraint,
which is non-convex [33]. To tackle the binary constraint,
we propose to apply an alternating optimization with an
auxiliary variable and resolve the orthonormal/orthogonal
constraint by using the discrete coordinate descent approach
to learn one column of the projection matrix at a time while
fixing the others. The proposed methods are named as Orthonormal Encoder (OnE) and Orthogonal Encoder (OgE).
Comprehensive experiments on common benchmark
datasets show considerable improvements on retrieval performance of proposed methods over other state-of-the-art
hashing methods. Additionally, the training time and online
processing time are also discussed to show the computational efficiency of our methods.

1.3. Notations and Term definitions
We first introduce the notations. Given a zero-centered
dataset X = {xi }ni=1 ∈ Rn×d which consists of n
images and each image is represented by a d-dimension
feature descriptor, our proposed hashing methods aim to
learn a column semi-orthonormal/semi-orthogonal matrix
V ∈ Rd×L (L  d) which simultaneously compresses input data X to L-dimensional space, while retains a high
amount of variation, and quantizes to binary codes B ∈
{−1, +1}n×L .
1 Please

refer to Section 1.3 for our term definitions.

It is important to note that, in this work, we abuse the
terms: column semi-orthonormal/semi-orthogonal matrix. Specifically, the term column semi-orthonormal matrix is used to indicate the matrix V that VT V = IL×L ,
where IL×L is the L × L identity matrix. While the term
column semi-orthogonal matrix indicates matrix V that
VT V = DL×L , where DL×L is an arbitrary L × L diagonal matrix. The word “semi” is prepended to “orthonormal/orthogonal” to indicate that the matrix is non-square
and the word “column” means that columns of the matrix
are pairwise independent.
We define Λ̂ = [λd , · · · , λ1 ] as the eigenvalues of the
covariance matrix XT X sorted in ascending order. Finally,
let bk , vk be the k-th (1 ≤ k ≤ L) columns of B, V respectively.

2. Simultaneous Compression & Quantization:
Orthonormal Encoder
2.1. Problem Formulation
In order to jointly learn data dimension reduction and
binary quantization using a single linear transformation V,
we propose to solve the following constrained optimization:
1
arg min Q(B, V) = kB − XVk2F
B,V
n
(1)
s.t. VT V = IL×L ; B ∈ {−1, +1}n×L ,
where k · kF denotes the Frobenius norm. Note that V is
constrained to be a column semi-orthonormal matrix, which
is necessary to make sure no redundant information is captured in binary codes [28] and the projection vectors do not
scale up/down projected data.
It is noteworthy that even though the loss function Eq.
(1) is similar to the binary quantization loss function of ITQ
[10], their fundamentals are different. Firstly, our approach
works directly on the original high-dimensional feature
space X, instead of on the compressed low-dimensional
feature space after using PCA. This leads to the second main
difference that the column semi-orthonormal matrix V simultaneously (i) compresses data to low-dimension with
high amount of retained variation; in section 2.2, we provide detailed analysis on how Eq. (1) can accomplish this
non-trivial task; and (ii) quantizes to binary codes instead
of just minimizing the quantization loss by using an orthogonal matrix as in ITQ. Finally, the optimization Eq. (1) is
challenging since there is no easy way for solving for nonsquare V. In section 2.3, we propose a novel and efficient
algorithm to handle this difficulty.

2.2. Balancing retained variation and quantization
loss
In the loss function Eq. (1), we do not explicitly maximize the retained variation of projected data, which is

26

50 - 0.34

37.9
23

25 - 0.29

0.25
20

0.25

0.2

0.15

0.1

0 - 0.24

Scale S

24.25

24

22

75 - 0.40

50 - 0.35

48.8

20

25 - 0.30

0.27
18

0.2

0.15

0.1

0 - 0.25

100 - 0.37

40.54
40

75 - 0.32

38

36

25 - 0.22

0.20
34

0.2

0.15

0.1

0 - 0.17

Scale S

Scale S

(a) CIFAR-10

50 - 0.27

48.5

Retained Var (%) | Quantization Loss

75 - 0.39

42

mAP (%)

mAP (%)

29

100 - 0.45

Retained Var (%) | Quantization Loss

30.82

26

mAP (%)

100 - 0.44

Retained Var (%) | Quantization Loss

32

(b) Labelme-12-50k

(c) SUN397

Figure 1: Analyzing the effects of the scale value S on (i) the quantization loss per bit (blue dash line with blue right Y-axis),
(ii) the percentage of total retained variation by the minimizing quantization loss projection matrix in comparison with the
total retained variation of top-L PCA components (red line with red right Y-axis), and (iii) the retrieval performance (green
line with green left Y-axis). The baseline retrieval performance of ITQ [10] is included for easier comparison (black line with
green left Y-axis). To obtain each data point, we solve the problem Eq. (1) at various scale values S, i.e., replace SX with X
in Eq. (1), and use Algorithm 1 (section 2.3) to tackle the optimization. We use VGG-FC7 feature descriptors of CIFAR-10,
Labelme-12-50k, and SUN397 datasets2 at L = 32. Note that x-axis is in descending order.
an important condition to preserve local structure of data.
Hence, before discussing how to solve the problem, in this
section, we show that by applying an appropriate scale S on
the dataset we can control the amount of retained variation
and achieve small quantization loss in the minimizing quantization loss problem. Noticeably, by applying any positive
scale S > 03 on the dataset, the local structure of data is
strictly preserved, i.e., the ranking nearest neighbor set of
every data point is always the same. Therefore, in the hashing problem for retrieval task, it is equivalent to work on a
scaled version of the dataset, i.e., XS = SX. Thus, the loss
function of Eq. (1) can be re-written as following:
Q(S, V) = k1 −

S|XV|k2F

T

s.t. V V = IL×L ; S > 0,
(2)
where | · | is the operation to find the absolute values and 1
is the all-1 (n × L) matrix.
Considering the Fig. 1 which shows the analysis of the
effects of the scale value S on (i) the quantization loss per
bit, (ii) the total retained variation by the minimizing quantization loss projection matrix in comparison with the total retained variation of top-L PCA components, and (iii)
the retrieval performance4 , we cannot achieve a scale value
S that can simultaneously maximizes the retained variation
and minimizes the optimal quantization loss. On the one
hand, as the scale value S decreases, minimizing the loss
function Eq. (2) produces a projection matrix that focuses
on high-variance directions, i.e., retains more variation in
comparison with PCA (red line). On the other hand, at
smaller S, the quantization loss is much larger (blue dash
2 Please refer to Section 4.1 for more details about the datasets and performance evaluation.
3 For simplicity, we only discuss positive scale value S > 0. Negative
scale value S < 0 should have similar effects.
4 Please refer to image caption for more detail.

line). We will discuss how to automatically determine an
appropriate S that can achieve good trade-off between retained variation and quantization loss.
2.2.1

Maximizing retained variation

We recognize that by scaling to the dataset X by a small
scale value S, such that all projected data points are inside the hyper-cube of 1, i.e., max(S|XV|) ≤ 1, the minimizing quantization loss problem can achieve similar results to the maximizing retained variation problem, i.e.,
arg max kSXVk2F ≈ arg min k1 − S|XV|k2F , in which
V

V

VT V = IL×L . Intuitively, we can interpret the PCA problem as to find the projection that maximizes the distances
of projected data points from the coordinate origin, while
the minimizing quantization loss problem tries to find the
projection matrix that minimizes the distances of projected
data points from −1 or +1 correspondingly. Since each vector of V is constrained to have the unit norm, the condition
max(S|XV|) ≤ 1 actually can be satisfied by scaling the
dataset by Smax var , where 1/Smax var is equal to the largest
l2-distance between data points and the coordinate origin,
to have all data points in the original space inside the hyperball with unit radius. The experimental results in Fig. 1 are
strongly support this claim. Specifically, as S gets smaller
(and approaches Smax var , which approximate 0.01 for the
datasets in Fig. 1), minimizing quantization loss projection
matrix can help to retain more variation (and up to over 99%
of variation) in comparison with PCA.
2.2.2

Minimizing quantization loss

Regarding the quantization loss Q(S, V) (Eq.
2),
which is a convex function of S|XV|, by setting

2.5

1

5

1
0

1
0
-1

0
Data points
1st PCA component - 61 = 0:07 - Qb = 0.65
2nd PCA component - 62 = 0:01 - Qb = 0.87
Min. Q proj. V - var = 0.07 - Qb = 0.65

-1
-1

0

1

-1

-2.5
-2.5

Data points
1st PCA component - 61 = 1:14 - Qb = 0.46
2nd PCA component - 62 = 0:12 - Qb = 0.57
Min. Q proj. V - var = 0.59 - Qb = 0.37

(a) S = Smax var

-1

0

1

2.5

-5
-5

Data points
1st PCA component - 61 = 10:23 - Qb = 6.19
2nd PCA component - 62 = 1:04 - Qb = 0.39
Min. Q proj. V - var = 1.04 - Qb = 0.39

(b) S = 4Smax var

-1

0

1

5

(c) S = 12Smax var

Figure 2: A toy example for n = 200, d = 2 and L = 1 to illustrate how the quantization loss and the minimizing quantization
loss vector (green dash line) vary when S increases. The values in legends represent the variances and the quantization losses
per bit, Qb , of the data which is projected in corresponding vectors (rounding to two decimal places).
∂Q(S, V)/∂S|XV| = 0, we have the optimal solution for
Q(S, V) as following:
(
mean(|XV|) = 1/S
∂Q(S, V)
= 2(S|XV|−1) = 0 ⇔
∂S|XV|
var(|XV|) = 0
(3)
where 0 is the all-0 (n × L) matrix.
Considering S ≥ Smax var , there are two important
findings. Firstly, there is obviously no scaling value S
that can concurrently achieve S max(|XV|) ≤ 1 and
Smean(|XV|) = 1, except the case S|XV| = 1 which
is unreal in practice. Secondly, from Eq. (3), we also can
recognize that as S gets larger, i.e., 1/S gets smaller, minimizing the loss Q will produce V that focuses on lowervariance directions so as to achieve smaller mean(|XV|) as
well as smaller var(|XV|), i.e., S|XV| gets closer to the
global minimum of Q(S, V). Consequently, the quantization loss becomes smaller. This explanation is consistent
with the observation in Fig. 1 that the quantization loss
and the retained variation simultaneously reduce when S
increases. However, keeping increasing S when V already
focuses on least-variance directions will make the quantization loss larger.
In Fig. 2, we show a toy example to illustrate that as S
increases, the minimizing quantization loss projection vector diverts from top-PCA component (Fig. 2a) to smaller
variance directions (Fig. 2b → 2c), while the quantization
loss (per bit) gets smaller (Fig. 2a → 2c).

eigenvalues, which are the variances of PCA components,
to find the scaling value. Specifically, we empirically found
that dividing the dataset by the square root of the (L/2)-th
eigenvalue, i.e.,
q
S ∗ = 1/ λ(L/2)
(4)
generally achieves a good trade-off between quantization
loss and retained variation. In fact, as shown in Fig. 1, our
proposed method works well and outperforms ITQ [10] for
a wide range of scale values (black line). It is worth noting
that ITQ [10] does not care about scaling.
For the rest of paper, we will only work on the dataset
that is scaled by S ∗ , i.e., XS ∗ = S ∗ X. However, for simplicity, we discard the subscript in later formulations.

2.3. Optimization
In this section, we discuss the key detail of the algorithm
(Algorithm 1) for solving the optimization problem Eq. (1).
In order to handle the binary constraint in Eq. (1), we propose to use alternating optimization over V and B.
2.3.1

When V is fixed, the problem becomes exactly the same as
when fixing rotation matrix in ITQ [10]. Hence, the optimal
value of B can be simply achieved by5 :
B = sign(XV).
2.3.2

2.2.3

Quantization loss Vs. Retained variation

Since both quantization loss and retained variation are critical in the hashing problem, it is necessary to make a tradeoff between these two requirements. So, “How to determine the scalar value that can properly scale the dataset?”
As data variation varies from dataset to dataset, it is difficult to find the optimal scale value for all datasets (Fig.
1: green line). Therefore, the scale value should be determined from the dataset itself. In particular, we leverage the

Fix V and update B

(5)

Fix B and update V

When fixing B, the optimization is no longer a mix-integer
problem. However, the problem is still non-convex and difficult to solve due to the orthonormal constraint. It is important to note that V is not a square matrix, i.e., the objective function is not the classic Orthogonal Procrustes problem [24]; hence, we cannot achieve the closed-form solution
for V as proposed in [10]. To the best of our knowledge,
there is no easy way for achieving the closed-form solution
5 Please

refer to ITQ [10] for more detailed explanation.

Algorithm 1 Orthonormal Encoder
Input:
X = {x}ni=1 ∈ Rn×d : scaled training data;
L: code length;
max iter: maximum iteration number;
{, b , u }: convergence error-tolerances;
Output
Column Semi-Orthonormal matrix V.
1: Initialize V = WPCA R, where WPCA ∈ Rd×L and
R ∈ RL×L respectively are the PCA dimension reduction matrix and ITQ [10] orthogonal rotation matrix.
2: for t = 1 → max iter do
3:
procedure F IX V, UPDATE B.
4:
Compute B (Eq. (5)).
5:
procedure F IX B, UPDATE V.
6:
Find ν1 using binary search (BS) (Eq. (9)).
7:
Compute v1 (Eq. (8)).
8:
for k = 2 → L do
9:
procedure S OLVE vk
10:
Initialize Φk = [0, · · · , 0].
11:
while true do
12:
Fix Φk , solve for νk using BS.
13:
Fix νk , compute Φk = A−1
k ck .
14:
Compute vk (Eq. (13)).
15:
if |vkT vk − 1| < u then
16:
return vk
17:
if t > 1 and |Qt−1 − Qt |/Qt <  then break
18: return V


ν1 > −λd /n


 ∂G
1
= [(XT X + nν1 I)−1 XT b1 ]T
∂ν


 1
[(XT X + nν1 I)−1 XT b1 ] − 1 = 0

where λd is the smallest eigenvalue of XT X.
In Eq. (9), the first condition is to make sure that
(XT X + nν1 I) is non-singular and the second condition
is achieved by setting the derivative of G1 (ν1 ) with regard
to ν1 equal to 0.
The second equation in Eq. (9) can be recognized as
a d-order polynomial equation of ν1 which has no explicit
closed-form solution for ν1 when d > 4. Fortunately, since
G(ν1 ) is a concave function of ν1 , ∂G1 /∂ν1 is monotonically decreasing. Hence, we can simply solve for ν1 using
binary search with a small error-tolerance, b . Note that:

∂G1

lim
∂ν1 = +∞
ν1 →(−λd /n)+
,
(10)
 lim ∂G1 = −1
∂ν1
ν1 →+∞

thus ∂G1 /∂ν1 = 0 always has a solution.
• k-th vector (2 ≤ k ≤ L)
For the second vector onward, besides the unit-norm constraint, we also need to make sure that the current vector is
independent with its (k − 1) previous vectors.
1
kbk − Xvk k2
n
s.t. vkT vk = 1; vkT vi = 0, ∀i ∈ [1, k − 1].
arg min Qk =
vk

of non-square V. Hence, in order to overcome this challenge, inspired by PCA, we use the coordinate descent approach to learn one vector, i.e., one column of V, at a time.
We now consider two cases for k = 1 and 2 ≤ k ≤ L.
• 1-st vector
1
kb1 − Xv1 k2 s.t. v1T v1 = 1, (6)
n
where k · k is the l2-norm.
Let ν1 ∈ R be the Lagrange multiplier, we formulate the
Lagrangian L1 :
arg min Q1 =
v1

L1 (v1 , ν1 ) =

1
kb1 − Xv1 k2 + ν1 (v1T v1 − 1).
n

(7)

By minimizing L1 over v1 , we can achieve:
T

−1

v1 = (X X + nν1 I)

T

X b1 ,

(8)

given ν1 that maximizes the dual function G1 (ν1 )6 of
L1 (v1 , ν1 ). Equivalently, ν1 should satisfy the following
conditions:
6 The dual function G (ν ) can be simply constructed by substituting
1 1
v1 from Eq. (8) into Eq. (7).

(9)

(11)

Let νk ∈ R and Φk = [φk1 , ..., φk(k−1) ]T ∈ R(k−1) be
the Lagrange multipliers, we also formulate the Lagrangian
Lk :
1
Lk (vk , νk , Φk ) = kbk − Xvk k2
n
k−1
(12)
X
+ νk (vkT vk − 1) +
φki vkT vi .
i=1

Minimizing Lk over vk , similar to Eq. (8), we can achieve:
!
k−1
nX
T
−1
T
φki vi , (13)
vk = (X X + nνk I)
X bk −
2 i=1
given {νk , Φk } that satisfy the following conditions which
make the corresponding dual function Gk (νk , Φk ) maximum:


νk > −λd /n
(14)
vkT vk = 1


A k Φk = c k
where







A k =










v1T Zk v(k−1)

..

.

T
· · · v(k−1)
Zk v(k−1)
iT
T
· · · v(k−1)
Zk XT bk

v1T Zk v1

..
n 
.
2 
T
v(k−1)
Zk v1

h
ck = v1T Zk XT bk

···
..
.

in which Zk = (XT X + nνk I)−1 .
There is also no straight-forward solution for {νk , Φk }.
In order to resolve this issue, we propose to use alternative
optimization to solve for νk and Φk . In particular, (i) given a
fixed Φk (initialized as [0, · · · , 0]T ), we find νk using binary
search as discuss above. Additionally, similar to ν1 , there
is always a solution for νk . Then, (ii) with fixed νk , we
can get the closed-form solution for Φk as Φk = A−1
k ck .
Note that since the dual function Gk is a concave function
of {νk , Φk }, alternative optimizing between νk and Φk still
guarantees the solution to approach the global optimal one.
We stop this alternative optimization when |vkT vk −1| ≤ u .
Fig. 3 shows an error convergence curve of Eq. (1).
We stop the optimization when the relative reduction of the
quantization loss is less than , i.e., |Qt−1 − Qt |/Qt < .
9.6
9.4

Q(B; V)

9.2
9

8.8
8.6
8.4
8.2

0

20

40

60

80

100

Number of iterations

Figure 3: Quantization error for learning the projection matrix V with L = 32 on the CIFAR-10 dataset (section 4.1).

3. Simultaneous Compression & Quantization:
Orthogonal Encoder
3.1. Problem Formulation
In Orthonormal Encoder (OnE), we work with the column semi-orthonormal constraint on V. However, we
recognize that relaxing this constraint to column semiorthogonal constraint, i.e., relaxing the unit norm constraint
on each column of V, by converting it into a penalty term,
provides three important advantages. We now achieve the
new loss function as following:
arg min Q(B, V) =
B,V

L
X
1
kB − XVk2F + µ
viT vi
n
(15)
i=1

s.t. B ∈ {−1, +1}n×L ; viT vj = 0, ∀i 6= j,
where µ is a fixed positive hyper-parameter to penalize large
norms of vi .
Firstly, with an appropriately large µ, the optimization
prefers to choose large variance components of X since this
helps to achieve the projection vectors that have smaller

norms. In other words, without penalizing large norms of
vi , the optimization has no incentive to focus on high variance components of X since it can produce projection vectors with arbitrary large norms that can scale any components appropriately to achieve minimum binary quantization loss. Secondly, this provides more flexibility of having different scale values for different directions. Consequently, relaxing the unit-norm constraint of each column
of V helps to mitigate the difficulty of choosing the scale
value S. However, on the other hand, a too large µ may distract the optimization from minimizing the binary quantization term. Finally, from OnE Optimization (Section 2.3),
we observed that the unit norm constraint on each column
of V makes the OnE optimization difficult to be solved efficiently since there is no closed-form solution for {v}L
k=1 .
By relaxing this unit norm constraint, we now can achieve
the closed-form solutions for {v}L
k=1 ; hence, it is very computationally beneficial.

3.2. Optimization
Similar to the Algorithm 1 for solving Orthonormal Encoder, we apply alternative optimize V and B with the B
step is exactly the same as Eq. (5). For V step, we also
utilize the coordinate descent approach to iteratively solve
V, i.e., column by column. The loss functions are rewritten
and their corresponding closed-form solutions for {v}L
k=1
can be efficiently achieved as following:
• 1-st vector
1
kb1 − Xv1 k2 + µv1T v1 .
(16)
n
We can see that Eq. (16) is the regularized least squares
problem, whose closed-form solution is given as:
arg min Q1 =
v1

v1 = (XT X + nµI)−1 XT b1 .
• k-th vector (2 ≤ k ≤ L)
1
arg min Qk = kbk − Xvk k2 + µvkT vk
vk
n
s.t. vkT vi = 0, ∀i ∈ [1, k − 1].

(17)

(18)

Given
the
Lagrange
multiplier
Φk
=
[φk1 , · · · , φk(k−1) ]T ∈ R(k−1) , similar to Eq.
(8)
and Eq. (12), we can obtain vk as following:
!
k−1
X
n
φki vi , (19)
vk = (XT X + nµI)−1 XT bk −
2 i=1
where Φk = A−1
k ck , in which


v1T Zv1
···





.
..

n

..
A k = 2
.



v1T Zv(k−1)

..

.

T
T

v
Zv
·
v
Zv
1
(k−1)

(k−1)
(k−1)

h
iT


T
c = vT ZXT b · · · vT
ZX
b
k
k
k
1
(k−1)

and Z = (XT X + nµI)−1 . Additionally, given a fixed µ,
Z is a constant, the (k − 1) × (k − 1) matrix Ak contains
(k − 2) × (k − 2) matrix A(k−1) in the top-left corner. It
means that only the (k − 1)-th row and column of matrix
Ak are needed to be computed. Thus, Φk can be solved
even more effectively.
Similar to OnE (Fig. 3), we also empirically observe
the convergence of the optimization problem Eq. 15. We
summarize the Orthogonal Encoder method in Algorithm
2.
Algorithm 2 Orthogonal Encoder
Input:
X = {x}ni=1 ∈ Rn×d : scaled training data;
L: code length;
max iter: maximum iteration number;
: convergence error-tolerance;
Output
Column Semi-Orthogonal matrix V.
1: Initialize V = WPCA R, where WPCA ∈ Rd×L and
R ∈ RL×L respectively are the PCA dimension reduction matrix and ITQ [10] orthogonal rotation matrix.
2: for t = 1 → max iter do
3:
Fix V, update B: Compute B (Eq. (5)).
4:
Fix B, update V: Compute {vi }L
i=1 (Eq.(17),(19)).
5:
if t > 1 and |Qt−1 − Qt |/Qt <  then break
6: return V

4. Experiments
4.1. Datasets, Evaluation protocols, and Implementation notes
The CIFAR-10 dataset [15] contains 60, 000 fullyannotated color images of 32 × 32 from 10 object classes
(6, 000 images for each class). The provided test set (1, 000
images for each class) is used as the query set. The remaining 50,000 images are used as training set and database.
The LabelMe-12-50k dataset [27] consists of 50, 000
fully-annotated color images of 256 × 256 of 12 object
classes, which is a subset of LabelMe dataset [23]. In this
dataset, for images having multiple label values in [0.0, 1.0],
the object class of the largest label value is chosen as image
label. We also use the provided test set as query set and the
remaining images as training set and database.
The SUN397 dataset [34] contains about 108, 000 fullyannotated color images from 397 scene categories. We select a subset of 42 categories which contain more than 500
images (about 35, 000 images in total). We then randomly
sample 100 images per class to form the query set. The
remaining images are used as training set and database.
For all datasets, each image is represented by a 4096-D
feature vector extracted from the fully-connected layer 7 of
pre-trained VGG [26].

Evaluation protocols. We apply three standard evaluation metrics, which are widely used in literature [2, 8, 10],
to measure the retrieval performance of all methods: 1)
mean Average Precision (mAP(%)); 2) precision at Hamming radius of 2 (prec@r2 (%)) which measures precision
on retrieved images having Hamming distance to query ≤ 2
(we report zero precision for the queries that return no image); 3) precision at top 1000 return images (prec@1k (%))
which measures the precision on the top 1000 retrieved images. Class labels are used as ground truths for all evaluation. Additionally, to avoid biased results due to unbalanced
samples of different classes in the query sets, we calculate
the average results for all classes.
Implementation notes. For computational efficiency,
we apply PCA to reduce the feature dimension to 512-D.
For OgE method, the hyper-parameter is empirically set as:
µ = 0.02. The maximum number of iteration is set as 100.
Finally, we set all error-tolerance values, , b , n , as 10−4 .
For all compared methods: Spherical Hashing (SpH)
[13], K-means Hashing (KMH)7 [12], Binary Autoencoder
(BA) [2], and Iterative Quantization (ITQ) [10]; we use the
implementation with suggested parameters provided by the
authors. Besides, to improve the statistical stability in the
results, we report the average values of 5 executions.

4.2. Comparison with state-of-the-art
In this section, we evaluate our proposed hashing methods, SCQ - OnE and OgE, and compare to the stateof-the-art unsupervised hashing methods including SpH,
KMH, BA, and ITQ. The experimental results in mAP,
prec@r2 and prec@1k are reported in Table 1. Our proposed methods clearly achieves significant improvement
over all datasets at the majority of evaluation metrics. The
improvement gaps are clearer at higher code lengths, i.e., L
= 32. Additionally, OgE generally achieves slightly higher
performance than OnE. Moreover, it is noticeable that, for
prec@r2, all compared methods suffer performance downgrade at long hash code, e.g., L = 32. However, our proposed methods still achieve good prec@r2 at L = 32. This
shows that binary codes producing by our methods highly
preserve data similarity.
Comparison with Deep Hasing (DH) [8] and Unsupervised Hashing with Binary Deep Neural Network
(UH-BDNN) [4]. Recently, there are several methods [8, 4]
applying DNN to learn binary hash code, which achieved
very competitive performances. Hence, in order to have a
complete evaluation, following the experiment settings of
[8, 4], we conduct experiments on CIFAR-10 dataset. In
this experiment, 100 images are randomly sampled for each
class as a query set; the remaining images are for training
and database. Each image is presented by a GIST 512-D
7 Due to very long training time at high-dimension of KMH [12], we
apply PCA to reduce dimension from 4096-D to 512-D.

Table 1: Performance comparison with the state-of-the-art unsupervised hashing methods.
The Bold and Underline values indicate the best and second best performances respectively.

SpH [13]
KMH [12]
BA [2]
ITQ [10]
SCQ - OnE
SCQ - OgE
SpH
KMH
BA
ITQ
SCQ - OnE
SCQ - OgE
SpH
KMH
BA
ITQ
SCQ - OnE
SCQ - OgE

8
17.09
14.26
23.24
24.75
27.08
26.98
18.04
12.42
23.67
24.38
24.48
24.35
22.93
26.64
31.73
32.40
33.38
33.41

CIFAR-10 [15]
16
24
18.77
15.55
24.02
26.47
29.64
29.33
30.58
34.01
38.05
38.41
36.49
38.30
26.99
25.83
34.16
36.35
37.82
38.33

20.19
24.20
24.77
26.86
30.57
30.65
37.28
42.33
42.95
42.96
41.53
43.01
29.50
34.52
35.67
37.25
39.13
39.54

32

8

20.96
23.12
25.92
27.19
30.82
31.15
21.40
27.46
23.49
28.63
43.90
44.01
31.98
30.75
37.01
37.96
40.40
40.70

11.68
14.70
17.48
17.56
19.76
20.63
11.72
9.93
16.22
15.86
16.69
16.57
14.07
16.33
21.14
21.01
22.91
23.94

descriptor [21]. In addition, to avoid bias results due to test
samples, we repeat the experiment 5 times with 5 different random training/query sets. The comparative results in
term of mAP and prec@r2 are presented in Table 2. Our
proposed methods are very competitive with DH and UHBDNN, specifically achieving higher mAP and prec@r2 at
L = 32 than DH and UH-BDNN.
Table 2: Performance comparison in mAP with Deep Hashing (DH) and Unsupervised Hashing with Binary Deep
Neural Network (UH-BDNN) on CIFAR-10 dataset. The
Bold values indicate the best performances.

CIFAR-10

Methods
DH [8]
UH-BDNN [4]
SCQ - OnE
SCQ - OgE

mAP
16
32
16.17 16.62
17.83 18.52
17.97 18.63
18.00 18.78

prec@r2
16
32
23.33 15.77
24.97 18.85
24.57 23.72
24.15 25.69

4.3. Training time and Processing time
In this experiment, we empirically evaluate the training
time and online processing time of our methods. The experiments are carried out on a workstation with a 4-core
i7-6700 CPU @ 3.40GHz. The experiments are conducted
on the combination of CIFAR-10, Labelme-12-50k, and
SUN397 datasets. For OnE and OgE, the training time
include time for applying zero-mean, scaling, reducing dimension to D = 512 and ITQ initialization (50 iterations).
We use 50 iterations for all experiments. The Fig. 4 shows
that our proposed methods, OnE and OgE, are very efficient.
OgE is just slightly slower than ITQ [10]. Even though
OnE is much slower than OgE and ITQ, it takes just over a

LabelMe-12-50k [27]
16
24
32
13.24
12.79
17.10
17.73
21.96
23.07
19.38
26.17
25.75
25.46
27.30
27.80
16.78
14.97
21.71
22.00
25.39
25.94

14.39
16.99
17.91
18.52
23.61
23.54
25.14
32.09
31.35
31.43
34.63
34.77
18.52
21.41
22.64
22.98
26.55
26.99

SUN397 [34]
16
24

8

14.97
15.09
18.07
19.09
24.25
24.68
13.66
18.62
13.14
17.66
33.04
34.64
19.27
19.02
22.83
23.63
27.16
27.46

9.13
21.91
20.73
20.16
23.37
23.44
6.88
9.50
10.50
9.78
8.68
8.76
10.79
18.94
19.22
18.86
19.26
20.10

13.53
23.42
31.18
30.95
34.09
34.73
23.68
36.14
37.75
35.15
30.12
29.31
15.36
22.93
28.68
28.62
29.95
29.95

16.63
26.04
35.36
35.92
38.13
39.47
37.21
51.27
50.38
49.85
43.54
45.03
18.21
23.74
31.31
31.56
32.72
33.43

32
19.07
29.17
36.40
37.84
40.54
41.82
27.39
39.29
41.11
46.34
50.41
51.88
20.07
27.26
31.80
32.74
34.08
35.00

minute for 100.000 training samples which is still very fast
and practical, in comparison with several dozen minutes (up
to hours) for BA [2] and UH-BDNN [4]8 .
100

Training time (s)

prec@1k

prec@r2

mAP

Dataset
L

80

OgE
OnE
ITQ

60
40
20
0
25000

75000

125000

Number of training samples

Figure 4: The training time for learning 32-bit hash code
embedding.
Compared with training cost, the time to produce new
hash codes is more important since it is done in real time.
Similar to Semi-Supervised Hashing (SSH) [28] and ITQ
[10], by using only a single linear transformation, our proposed methods require only one BLAS operation (gemv or
gemm) and a comparison operation; hence, it takes negligible time to produce binary codes for new data points.

5. Conclusion
In this paper, we successfully addressed the problem of
jointly learning to preserve data pairwise (dis)similarity in
low-dimension space and minimize the binary quantization
loss. Extensive experiments on various datasets show that
both our proposed methods, Simultaneous Compression
8 For training 50000 CIFAR-10 samples using author’s release code and
dataset [4].

and Quantization (SCQ): Orthonormal Encoder (OnE) and
Orthogonal Encoder (OgE), outperform other state-of-theart hashing methods by a clear margin under the three standard evaluation metrics. Moreover, OgE achieves slightly
higher performance while having much shorter training
times than OnE.

References
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for
approximate nearest neighbor in high dimensions. Commun.
ACM, 51, Jan. 2008. 1, 2
[2] M. Á. Carreira-Perpiñán and R. Raziperchikolaei. Hashing
with binary autoencoders. In CVPR, 2015. 1, 7, 8
[3] T.-T. Do and N.-M. Cheung. Embedding based on function
approximation for large scale image search. TPAMI, 2017. 1
[4] T.-T. Do, A.-D. Doan, and N.-M. Cheung. Learning to hash
with binary deep neural network. In ECCV, 2016. 1, 2, 7, 8
[5] T.-T. Do, A.-D. Doan, D.-T. Nguyen, and N.-M. Cheung.
Binary hashing with semidefinite relaxation and augmented
lagrangian. In ECCV, 2016. 1
[6] T.-T. Do, D.-K. Le Tan, T. T. Pham, and N.-M. Cheung. Simultaneous feature aggregating and hashing for large-scale
image search. In CVPR, 2017. 1
[7] T.-T. Do, Q. Tran, and N.-M. Cheung. FAemb: A function
approximation-based embedding method for image retrieval.
In CVPR, 2015. 1
[8] V. Erin Liong, J. Lu, G. Wang, P. Moulin, and J. Zhou. Deep
hashing for compact binary codes learning. In CVPR, 2015.
7, 8
[9] A. Gionis, P. Indyk, and R. Motwani. Similarity search in
high dimensions via hashing. In VLDB, 1999. 1
[10] Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR, 2011.
1, 2, 3, 4, 5, 7, 8
[11] K. Grauman and R. Fergus. Learning binary hash codes for
large-scale image search. 411, 01 2013. 1
[12] K. He, F. Wen, and J. Sun. K-means hashing: An affinitypreserving quantization method for learning binary compact
codes. In CVPR, 2013. 1, 7, 8
[13] J. P. Heo, Y. Lee, J. He, S. F. Chang, and S. E. Yoon. Spherical hashing. In CVPR, 2012. 1, 7, 8
[14] T. Hoang, T.-T. Do, D.-K. L. Tan, and N.-M. Cheung. Selective deep convolutional features for image retrieval. In
ACM-MM, 2017. 1
[15] A. Krizhevsky and G. Hinton. Learning multiple layers of
features from tiny images. In Technical report, University of
Toronto, 2009. 7, 8
[16] B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In Y. Bengio, D. Schuurmans, J. D.
Lafferty, C. K. I. Williams, and A. Culotta, editors, NIPS,
2009. 1
[17] B. Kulis and K. Grauman. Kernelized locality-sensitive
hashing for scalable image search. In ICCV, Nov 2009. 1
[18] G. Lin, C. Shen, Q. Shi, A. van den Hengel, and D. Suter.
Fast supervised hashing with decision trees for highdimensional data. In CVPR, 2014. 1

[19] W. Liu, J. Wang, R. Ji, Y. G. Jiang, and S. F. Chang. Supervised hashing with kernels. In CVPR, 2012. 1
[20] M. Norouzi, D. J. Fleet, and R. Salakhutdinov. Hamming
distance metric learning. In NIPS, 2012. 1
[21] A. Oliva and A. Torralba. Modeling the shape of the scene:
A holistic representation of the spatial envelope. IJCV, pages
145–175, 2001. 8
[22] M. Raginsky and S. Lazebnik. Locality-sensitive binary
codes from shift-invariant kernels. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta,
editors, NIPS. 2009. 1
[23] B. C. Russell, A. Torralba, K. P. Murphy, and W. T. Freeman. Labelme: A database and web-based tool for image
annotation. IJCV, pages 157–173, 2008. 7
[24] P. H. Schönemann. A generalized solution of the orthogonal
procrustes problem. Psychometrika, 1966. 4
[25] F. Shen, C. Shen, W. Liu, and H. T. Shen. Supervised discrete
hashing. In CVPR, 2015. 1
[26] K. Simonyan and A. Zisserman. Very deep convolutional
networks for large-scale image recognition. CoRR, 2014. 7
[27] R. Uetz and S. Behnke. Large-scale object recognition with
cuda-accelerated hierarchical neural networks. In IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS), 2009. 7, 8
[28] J. Wang, S. Kumar, and S. F. Chang. Semi-supervised hashing for large-scale search. TPAMI, 2012. 2, 8
[29] J. Wang, W. Liu, S. Kumar, and S. Chang. Learning to hash
for indexing big data - a survey. 104, 09 2015. 1
[30] J. Wang, H. Tao Shen, J. Song, and J. Ji. Hashing for similarity search: A survey. 08 2014. 1
[31] J. Wang, T. Zhang, j. song, N. Sebe, and H. T. Shen. A survey
on learning to hash. TPAMI, 2017. 1
[32] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In
NIPS, 2009. 1, 2
[33] Z. Wen and W. Yin. A feasible method for optimization with
orthogonality constraints. Math. Program., Dec 2013. 2
[34] J. Xiao, K. A. Ehinger, J. Hays, A. Torralba, and A. Oliva.
Sun database: Exploring a large collection of scene categories. IJCV, Aug 2016. 7, 8
[35] D. Zhang, J. Wang, D. Cai, and J. Lu. Self-taught hashing
for fast similarity search. In ACM SIGIR, 2010. 1

