A MULTI-LAYER NETWORK BASED ON SPARSE TERNARY CODES
FOR UNIVERSAL VECTOR COMPRESSION
Sohrab Ferdowsi, Slava Voloshynovskiy, Dimche Kostadinov

arXiv:1710.11510v1 [cs.CV] 31 Oct 2017

Dep. of Computer Science, University of Geneva, Switzerland
{sohrab.ferdowsi, svolos, dimche.kostadinov}@unige.ch
ABSTRACT
We present the multi-layer extension of the Sparse Ternary
Codes (STC) for fast similarity search where we focus on the
reconstruction of the database vectors from the ternary codes.
To consider the trade-offs between the compactness of the
STC and the quality of the reconstructed vectors, we study the
rate-distortion behavior of these codes under different setups.
We show that a single-layer code cannot achieve satisfactory
results at high rates. Therefore, we extend the concept of
STC to multiple layers and design the ML-STC, a codebookfree system that successively refines the reconstruction of the
residuals of previous layers. While the ML-STC keeps the
sparse ternary structure of the single-layer STC and hence is
suitable for fast similarity search in large-scale databases, we
show its superior rate-distortion performance on both modelbased synthetic data and public large-scale databases, as compared to several binary hashing methods.
Index Terms— vector compression, Approximate Nearest Neighbor search, large-scale databases, rate-distortion
theory
1. INTRODUCTION
The framework of Sparse Ternary Codes (STC) [1], [2] was
proposed as an alternative to binary hashing to address the
problem of Approximate Nearest Neighbor (ANN) search.
In ANN, compact representations should be designed to replace real-valued high-dimensional feature vectors in order
to accommodate large-scale data in small memory and perform fast search within them. The main idea behind the STC
framework was to show that projecting the data to higher dimensions and quantizing them to a ternary but sparse alphabet should be preferred to projecting to lower dimensions and
quantizing them to a dense binary alphabet since it provides
better compactness and fidelity of representation. In particular, it was shown in [1] that for a fixed rate-budget, i.e., for
a fixed amount of entropy of the codes, the STC framework
preserves larger mutual information between the encoded versions of the data and its noisy realizations as compared to the
popular binary hashing framework.

To perform more accurate similarity search, one can think
of refining the inaccurate short-list returned by the compact
codes by reconstructing the elements from the list and improve it by matching in the original feature domain. Motivated by this idea of “list-refinement”, we focus in this paper
on the reconstruction of the feature vectors from their STC by
considering the rate-distortion trade-offs of the design.
We provide the following contributions in this paper.
First, complementary to the arguments of coding gain of [1]
where it was shown that for a fixed compactness, ternary
encoding provides higher mutual information between the
encoded data and query, we show in this paper that they also
provide better reconstruction quality compared to the binary
codes for a fixed number of bits used.
Next, we show that in order to provide high-quality reconstruction, i.e., to operate at high rate regimes of the ratedistortion curve, one single layer of representation is not
sufficient. Instead, we show that multi-layers of STC where
each of the layers is operating within a very low-rate regime,
or equivalently with highly sparse ternary values, is able
to approximate the information-theoretic limits of the ratedistortion trade-off.1
Finally, we test the rate-distortion performance of the system for different data sources. We first focus on the i.i.d.
Gaussian data and also correlated data with known covariance
matrix with varying levels of correlation and consider the theoretical Shannon Lower Bound (SLB) as a guiding principle
for design. We next show that we achieve very good compression performance on the MNIST set of images and GIST-1M
set of descriptor features when compared to binary hashing
methods from literature.
Section 2 formalizes the problem of compressive datarepresentation, particularly in view of fast search applications.
After briefly reviewing the STC framework, section 3 focuses
on the problem of reconstruction from them. In section 4 we
perform experiments on public databases and finally we conclude the paper in section 5.
1 Since binary encoding is the special case of ternary encoding when there
is no sparsity, this also implies that one cannot benefit from multi-layer design
based on binary codes to achieve high-quality reconstruction.

2. PROBLEM FORMULATION: COMPRESSIVE
DATA-REPRESENTATION FOR ANN SEARCH
Consider a database F = [f (1), · · · , f (N )], consisting of
data-points f (i)’s ∈ <n , each of them features representing
an entity like human biometrics, images or image descriptors.
When either N or n is large, for a wide variety of tasks, it
is crucial to store these vectors compressed. So we seek a
compressive data representation scheme that should provide
an encoder-decoder pair, Q[·] and Q−1 [·], such that the codes
or the representations are as compact as possible. At the same
time, when decoded, the codes should closely approximate
the original data. The first requirement is characterized by
rate and the second requirement by distortion.
More formally, for any realization vector f , the rate of the
representation x = Q[f ] is defined as in (1a) and the distortion
of the reconstruction f̂ = Q−1 [x] is defined as in (1b)2 , where
we define the squared-error between two n-dimensional vectors a and b as d(a, b) , n1 ||a − b||22 , and E[·] denotes the
expectation operator.
1
E[# bits used]
n
D = E[d(F, F̂)]

R=

(1a)
(1b)

Within the similarity search domain, for many applications, a noisy query q is introduced and it is desired to find
L(q) = {1 6 i 6 N |d(f (i), q) 6 n}, a list of most similar items to q among F. Since for large-scale problems, F
is not available in memory and also direct matching with it
is computationally expensive, an approximative L̂(q) is preferred using low-complexity matching of x(i) = Q[f (i)] vs.
y = Q[q], rather than f (i) vs. q. So we require Q[·] to be
additionally compatible with this framework.
The efficiency of the decoder Q−1 [·] can be doubly important for search applications since we can re-order and prune
the inaccurate L̂(q) by reconstructing f (i)’s with i ∈ L̂(q)
and directly match them with q based on d(f̂ (i), q).
While this idea of “list-refinement” has not been particularly emphasized in the literature, lots of algorithms for fast
search directly target distortion minimization as their main
objective. Among the very broad literature, not to mention
the family of VQ-based methods like PQ [3] and OPQ [4]
which are codebook-based, many examples from the family
of binary hashing methods also aim at distortion minimization. We can mention, e.g., the successful ITQ [5], which
iteratively learns a projector matrix to minimize the distortion of the projected data and the corresponding binary codes.
Another attempt is the Sparse Projections [6], an extension of
ITQ for higher rates using similar objective.

3. PROPOSED: RECONSTRUCTION FROM STC
We first review the basic STC framework for fast search in
section 3.1. Based on its specifications, we design the singlelayer reconstruction from the STC in section 3.2 to its best.
We then extend it to ML-STC, the multi-layer version to
achieve near optimal distortion for all rate-regimes.
3.1. STC framework for fast search
The STC consists of a projection step3 , followed by a ternary
quantization. More formally, the corresponding STC for f ,
i.e., x = QSTC [f ] with threshold λX is:
x = φλX (Af )

β,

(2)

where φλ (x) = sign(x) · 1{|x|>λ} is the element-wise ternary
thresholding operator, ‘ ’ is the Hadamard product and β =
[β1 , · · · , βn ]T is a re-weighting vector which is independent
of a particular f and is fixed for all database vectors4 . Therefore, each element of x, i.e., xi has a ternary alphabet Xi =
{±βi , 0}. In practice, λX is chosen such that x is sparse.
The motivation behind such an encoding comes from similarity search where the memory and computational complexity
requirements encourage sparsity and a fixed-point alphabet.
After the enrollment of all x(i)’s (usually stored in lookup-tables), a query vector q undergoes similar encoding, i.e.,
y = φλY (Aq) and is matched with x(i)’s to produce L̂(q).
This matching can be performed very fast, e.g., using fixedpoint sparse matrix multiplications.
3.2. Single-layer architecture
We formulate reconstruction of STC, i.e., f̂ = Q−1
STC [x] as:
f̂ = Bx = Bφλ (Af )

β.

(3)

Where B is the reconstruction matrix that can be learned
from the training data. However, in order to avoid overfitting, the forward projection step using A should be imposed as a structure to help training. So we decompose as
B = (AT A)−1 AT B0 and instead optimize B0 :
B0 = argmin ||F − (AT A)−1 AT B0 X||2F ,

(4)

B0

where || · ||F is the Frobenius norm for a matrix. This can
easily be re-expressed as:
B0 = argmin ||(AT A)F − AT B0 X||2F
B0
h
i
= argmin Tr (AF − B0 X)T AAT (AF − B0 X)
B0
h
i
T
T
= argmin Tr − 2AAT AFXT B0 + B0 XXT B0 AAT .
B0

2 We can think of the the random variable F (and likewise F̂) as the underlying rule that generates f ’s as its realizations. If p(f , f̂ ) is unknown, D
1 PN
can be approximated from a test set as D̂ = N
i=1 d(f (i), f̂ (i)).

3 Throughout this paper, we assume that the projection matrix A is square
and hence the dimensions of f and x are the same.
4 In [1] and [2], reconstruction was not considered and we had β = 1.

=
=

Therefore, the projected data x̃ , Af is de-correlated
 as
X̃ ∼ N (0, ΣF )5 , where ΣF = diag [σ12 , · · · , σn2 ]T with
σi2 ’s being the eigenvalues of CF which are decaying in value
for the correlated F.
In our experiments, it turns out that with this choice of
A, and the optimal re-weighting vector β for x which will
be described shortly, B0 indeed converges to the identity matrix as N , the number of training samples grows larger. This
means that it suffices to choose B0 = In . Equivalently stated,
B = AT = UF would be the optimal back-projector of x to
f under this setup.
We can characterize the expected distortion for reconstruction of a random vector F from X. Emphasizing the
orthonormality of A, we can then write:



1 
D = E d(F, F̂) = E ||F − AT X||22
n

1 
1 
= E ||AF − X)||22 = E ||X̃ − φλ (X̃)
n
n


β||22 .

This links the distortion in the original domain with that of
the projection domain. Now we should find the optimal reweighting vector β.
We had that X̃i ’s, the elements of X̃ = [X̃1 , · · · , X̃n ]T
are distributed as X̃i ∼ p(x̃i ) = N (0, σi2 ). The total distortion
is the sum of the distortions at each dimension as
PD
n
D = i=1 Di , which can then be written as:


Di = E (X̃i − βi φλ (X̃i ))2
Z −λ
Z +λ
=
(x̃i + βi )2 p(x̃i )dx̃i +
x̃2i p(x̃i )dx̃i +
Z

−∞
+∞

+λ

−λ

2

(x̃i − βi ) p(x̃i )dx̃i ,

n

R=

1X
1
Ht (X) =
Ht (Xi ) =
n
n i=1

n
 (7)
1 X
−
2αi log2 (αi ) + (1 − 2αi ) log2 (1 − 2αi ) ,
n i=1

which follows from the fact that X̃ and hence X are decorrelated and hence we can assume their approximative
independence. For a ternary random variable Xi , αi is defined as αi = P[Xi = +βi ] = P[Xi = −βi ] and completely
characterizes the ternary entropy Ht (·). For the above setup,

this can be calculated for every Xi , simply as αi = Q σλi .
Fig. 1 shows the rate-distortion behavior of the singlelayer STC for 3 different sources: (a) i.i.d., (b) AR(1) with
ρ = 0.5 corresponding to mildly-correlated signals and (c)
AR(1) with ρ = 0.9 corresponding to highly-correlated signals. For every figure, three curves are shown: the Shannon
Lower Bound (SLB) derived from (8) which is the theoretical lower bound achieved in the asymptotic case of n → ∞
for any lossy source-coding scheme, the theoretical characterization of the STC distortion derived from (5) and the empirical distortion calculated from simulations performed on
N = 10, 000 vectors of dimension n = 500 generated randomly. Also the case of binary encoding, i.e., zero sparsity,
corresponding to R = 1 is marked.
1

1
SLB
theoretical
empirical
binary

0.8
0.6

0.4

0.2

0.2

0

1

2
R (bits)

(a) i.i.d.

3

4

SLB
theoretical
empirical
binary

0.8

0.6

0.4

0

This integration leads to the expression of distortion as:

1
SLB
theoretical
empirical
binary

0.8

0.6
D

Assuming F to have a covariance matrix CF , i.e., CF
1
T
E[FF
], we chose the projection as A = UTF , where CF
n
T
UF ΣF UF is the eigenvalue decomposition of CF .

D

B0 = AFXT (XXT )−1 .

of CF which de-correlates the projected data x̃. The ternarization is then performed according to (2), for which the
elements of β are derived according to Eqs. 5 & 6. For decoding , the reconstruction is done by (3), where we showed
that B = AT is the optimal choice.
Having calculated D as a function of CF and λ, we now
derive R using the ternary entropy Ht (·) as:

D

Derivating w.r.t. B0 and equating to zero gives:

0

0.4
0.2

0

1

2

3

R (bits)

4

0

0

1

2

3

4

R (bits)

(b) mid-correlation) (c) high-correlation

(5)

Fig. 1: Distortion-rate curves for single-layer STC (The ‘theoretical’ and ‘empirical’ curves coincide very closely.)

where Q(·) is the q-function, because of which βi cannot be
derived in closed-form. However, for a given σi2 and λ, the
optimal βi∗ , i.e.,
βi∗ = argmin Di ,
(6)

We clearly see that at lower sparsity levels (including the
binary case) corresponding to higher rate-regimes, the singlelayer structure has very poor performance. This phenomenon
is due to sub-optimal rate allocation as we will describe next.

can easily be obtained using a simple grid-search on (5).
As a summary of the single-layer reconstruction from
STC, first for the encoding, A is chosen as the eigenvectors

3.2.1. Optimality of rate-allocation

 −λ2 
 λ  4β σ
i i
− √
exp
,
Di = σi2 + 2βi2 Q
σi
2σi2
2π

βi

5 Gaussianity assumption in the projected domain is justified from CLT,
even if the original data is highly non-Gaussian.

The Shannon theory
 characterized the optimal rate allocation
for X̃ ∼ N 0, Σ (see Ch.10 of [7]). For a given D, this is
σ2 
achieved when Ri = 21 log2 Dii bits are allocated for each

Comparing this optimal rate allocation of (9) with the singlelayer STC of (7) reveals the fact that while they closely approximate the optimal rule at low rates, single-layer structure
largely deviates from the optimal allocation at higher rates.
This explains the saturating behavior of the rate-distortion
curve at Fig. 1. This phenomenon is illustrated in Fig. 2.
·10−3
optimal (i.i.d.)
Single-layer (i.i.d.)
optimal (mid-corr.)
Single-layer (mid-corr.)
optimal (high-corr.)
Single-layer (high-corr.)

1

Ri (bits)

Ri (bits)

1.5

·10−3
optimal (i.i.d.)
Single-layer (i.i.d.)
optimal (mid-corr.)
Single-layer (mid-corr.)
optimal (high-corr.)
Single-layer (high-corr.)

6

4

optimal (i.i.d.)
Single-layer (i.i.d.)
optimal (mid-corr.)
Single-layer (mid-corr.)
optimal (high-corr.)
Single-layer (high-corr.)

8
6
Ri (bits)

·10−3
2

4

2

0.5

2

0

0
100

200

300

400

0

500

100

dimension

200

300

400

500

100

dimension

(a) low-rate

200

300

400

500

dimension

(b) mid-rate

(c) high-rate

Fig. 2: Rate allocation of single-layer STC compared to the
optimal rule, under three different rate regimes and for three
different sources (same as in Fig. 1).

1

1
SLB
empirical

0.8

1
SLB
empirical

0.8

0.6
D

0.6

0.4

0.4

0.2

0.2

0

0

1

2

3

4

0

0.4
0.2

0

1

R (bits)

2

=f

[l−1]

[l] [l]

−B x .

(10)

The superscripts depict the index of the layer l = 1, · · · , L.
f [l] is the input to the algorithm at layer l which is the residual of the approximation from layer l − 1 and is initialized
as f [0] = f . The rest of the procedure is the same as the
single-layer case. Fig. 3 shows the success of this idea in
rate-distortion within the same setup as Fig. 1.
4. EXPERIMENTS
Here we demonstrate the performance of the proposed algorithm on the task of database compression. We use two public

2

3

4

R (bits)

globally as F̂ ← β F̂. Fig. 4 sketches the results of these experiments. The ML-STC outperforms others with a large margin.
1
ML-STC (L = 50)
ITQ
Sparse Projections
PCA
LSH

ML-STC (L = 70)
ITQ
Sparse Projections
PCA
LSH

0.8
0.6
D

D

f

[l]

1

databases, MNIST of mid-scale and the large-scale GIST-1M
set [3]. The MNIST contains 60, 000 train and 10, 000 test
images with 784 pixels which we consider as feature vectors.
The GIST-1M comprises of 960-dimensional GIST descriptors with 500, 000 train and 1 million test vectors. Along with
our ML-STC, we also experiment with the ITQ [5], the Sparse
Projections [6] (using sparsity = 50%), PCA hashing and the
LSH (Sim-Hash) [8]. We train all algorithms on the train and
calculate the distortion on the test set. The reconstruction
from the binary codes consists of pseudo-inversion and, for
PCA hashing, the above-mentioned re-weighting stage followed by the inversion. For the ITQ and Sparse Projections,
the vector β is irrelevant and also detrimental according to
their objective functions. Instead, a scaler-valued optimal β
Tr[FF̂T ]
and multiplied
is learned from the training set as β = Tr[
F̂F̂T ]

0.6

β [l] ,

0

Fig. 3: Rate distortion performance of multi-layer STC

3.3. Multi-layer architecture

[l]

0

4

(a) low-correlation (b) mid-correlation) (c) high-correlation

0.8

x[l] = φλX (A[l] f [l−1] )

3

R (bits)

1

The mismatch between rate-allocation of the single-layer
STC and the optimal rule at high rates limits their efficient
use only for very low rate regimes. One could think of more
intricate quantization schemes than ternary to overcome this
issue. However, this would ruin their simplicity and usefulness for many applications like fast similarity search. Instead,
we keep operating STC at lower rates but use them in succession. This idea is demonstrated in (10):

SLB
empirical

0.8

D

0.6
D

X̃i , where Di , corresponding distortion of each X̃i is:
(
λ, if σi2 > λ
(8)
Di =
σi2 , if σi2 < λ,
Pn
and λ is chosen such that i=1 Di = D. The total rate is
then calculated as:
n
n
 σ2 
X
X
1
i
R(D) =
Ri =
log2
.
(9)
2
D
i
i=1
i=1

0.4

0.4

0.2

0.2

0

0

200 400 600 800 1,0001,2001,4001,600

0

0

1,000

(a) MNIST

2,000

3,000

4,000

# bits

# bits

(b) GIST-1M

Fig. 4: Reconstruction distortion from compressed ANN sets.

5. CONCLUSIONS
A universal compressor network is designed based on the
Sparse Ternary Codes framework for similarity search where
we demonstrate rate-distortion performance on synthetic as
well as real data, superior to several exemplar methods from
the binary encoding family. The intrinsic limitations of rate
allocation w.r.t. optimality suggests a multi-layer design
which is hopeless for binary encoding but applies very nicely
for STC when they are set to be highly sparse. Thanks to
the simplicity of encoding and the universality of the signals
considered, these results can be useful for many applications.
An immediate benefit would be for the idea of list-refinement
in similarity search which we will address in a future work.

6. REFERENCES
[1] Sohrab Ferdowsi, Sviatoslav Voloshynovskiy, Dimche
Kostadinov, and Taras Holotyak, “Sparse ternary codes
for similarity search have higher coding gain than dense
binary codes,” in 2017 IEEE International Symposium
on Information Theory (ISIT) (ISIT’2017), Aachen, Germany, jun 2017.
[2] S. Ferdowsi, S. Voloshynovskiy, D. Kostadinov, and
T. Holotyak,
“Fast content identification in highdimensional feature spaces using sparse ternary codes,”
in 2016 IEEE International Workshop on Information
Forensics and Security (WIFS), Dec 2016, pp. 1–6.
[3] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” Pattern Analysis and
Machine Intelligence, IEEE Transactions on, vol. 33, no.
1, pp. 117–128, 2011.
[4] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun, “Optimized product quantization,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 36, no. 4,
pp. 744–755, April 2014.
[5] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin, “Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 35, no. 12, pp. 2916–2929, Dec 2013.
[6] Yan Xia, K. He, P. Kohli, and J. Sun, “Sparse projections for high-dimensional binary codes,” in 2015 IEEE
Conference on Computer Vision and Pattern Recognition
(CVPR), June 2015, pp. 3332–3339.
[7] T. Cover and J. Thomas, Elements of Information Theory
2nd Edition, Wiley-Interscience, 2 edition, 7 2006.
[8] M. Charikar, “Similarity estimation techniques from
rounding algorithms,” in Proceedings of the thiry-fourth
annual ACM symposium on Theory of computing, 2002.

