Faster Binary Embeddings for Preserving Euclidean Distances
Authors: Jinjie Zhang
Rayan Saab
Venue: ICLR 2021 Poster (2021)
Keywords: Binary Embeddings
Johnson-Lindenstrauss Transforms
Sigma Delta Quantization

Abstract: We propose a fast, distance-preserving, binary embedding algorithm to transform a high-dimensional dataset $\mathcal{T}\subseteq\mathbb{R}^n$ into binary sequences in the cube $\{\pm 1\}^m$. When $\mathcal{T}$ consists of well-spread (i.e., non-sparse) vectors, our embedding method applies a stable noise-shaping quantization scheme to $A x$ where $A\in\mathbb{R}^{m\times n}$ is a sparse Gaussian random matrix. This contrasts with most binary embedding methods, which usually use $x\mapsto \mathrm{sign}(Ax)$ for the embedding. Moreover, we show that Euclidean distances among the elements of $\mathcal{T}$ are approximated by the $\ell_1$ norm on the images of $\{\pm 1\}^m$ under a fast linear transformation. This again contrasts with standard methods, where the Hamming distance is used instead.  Our method is both fast and memory efficient, with time complexity  $O(m)$ and space complexity $O(m)$ on well-spread data. When the data is not well-spread, we show that the approach still works provided that data is transformed via a Walsh-Hadamard matrix, but now the cost is $O(n\log n)$ per data point.  Further, we prove that the method is accurate and its associated error is comparable to that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization error that admits a polynomial decay as the embedding dimension $m$ increases.
	Thus the length of the binary codes required to achieve a desired accuracy is quite small, and we show it can even be compressed further without compromising the accuracy. To illustrate our results, we test the proposed method on natural images and show that it achieves strong performance.

Published as a conference paper at ICLR 2021
FASTER BINARY EMBEDDINGS FOR PRESERVING EUCLIDEAN DISTANCES
Jinjie Zhang & Rayan Saab
Department of Mathematics, Hahıcooğu Data Science Institute University of California San Diego {jiz003, rsaab)eucsd.ed
ABSTRACT
We propose fast, distance-preservingg binary embedding algorithm to transform a high-dimensional dataset T S R" into binary sequences in the cube {=1}m When T consists of well-spread (i.e., non-sparse) vectors, our embedding method applics a stable noise-shaping quantization scheme to Ax where A E IR"x"" is sparse Gaussian random matrix. This contrasts with most binary embedding methods, which usually use æ + sign(Az) for the embedding. Moreover, we show that Euclidean distances among the elements of T approximated by the f norm on the images of {+1) under a fast linear transformation. This again contrasts with standard methods, where the Hamming distance used instead. Our method is both fast and memory efficient, with time complexity ((m) and space complexity (mm) on well-spread data. When the data not well-spread, we show that the approach still works provided that data is transformed via a Walsh-Hadamant matrix, but now the cost is Ong n) per data point. Further, we prove that the method is accurate and its associated error is comparable that of a continuous valued eπror that admits polynomial decay as the embedding dimension increases. Thus the length of the binary codes required to achieve a desired accuracy quite small, and we show it even be compressed further without compromising the accuracy. To illustrate our results, we test the proposed method on natural images and show that it achieves strong performance.
embedding plus quantization
INTRODUCTION
Analyzing large data sets of hign-dimensional raw data usually computationally demanding and memory intensive. As result, it is often necessary preprocessing step to transform data into a lower-dimensional space while approximately preserving important geometric properties, such as pairwise le distances. As critical result in dimensionality reduction, the
(JL) lemma (Johnson & Lindenstrauss 1984) guarantees that every finite set T C R can be (lin- early) mapped
O(c log([7 ()) dimensional space in such way that all pairwise dis- tances are preserved up to an e-Lipschitz distortion. Additionally, there are many significant results speed up the JL transform by introducing fast embeddings, e.g. (Ailon & Chazelle 2009 Ailon & Liberty 2013 Krahmer & Ward [201]] Nelson et al. 2014).. or by using sparse matrices (Kane & Clarkson Woodruff] 2017). Such fast embeddings can usually be computed in On log n versus the O(mn) time complexity of JL transforms that rely unstructured dense
Nelson 2014|2o00
matrices.
1.1 RELATED WORK
To further reduce memory requirements, progress has been made in nonlinearly embedding high- dimensional sets T C 1nt to the binary cube {-1, with < n. process known binary embedding. Provided that d1 (+.)) is metric on R., a distace preserving binary embedding is map
"The Python source code of our paper: http:///tthhoooooo///mm////////n
Preserving-Fucliddan-- Maaelidea--Dstanncee

---

Published as a conference paper at ICLR 2021
f:
and function d) on (-1,1) x f-1,1)" to approximate distances, i.e., (a)( f(y)) di (æ, y) S a, for y
(1)
The potential dimensionality reduction (m < n) and 1-bit representation per dimension imply that storage space can be considerably reduced and downstream applications like learning and retrieval can happen directly using bitwise operations. Most existing nonlinear mappings f in (T) are gener- ated simple memory-less scalar quantization (MSQ). For example, given set of unit vectors T C gn- with finite size [T], consider the map
qu f(z) Sign(Ga)
where G E R is a standard Gaussian random matrix and sign(-) returns the element-wise sign of its argument. Let di (at, y) = _ [[ | (xc y)) be the normalized angular distance and d2(1z. fy) 2m ll qr fy |I be the normalized Hamming distance. Then, Yi et al. (205)) show that (I) holds with probability at least 1 - if m Z a a= a==log((T1/m)) so one can approximate geodesic distances with normalized Hamming distances. While this approach achieves optimal bit complexity (up to constants) (Yi et al., 2015), it has been observed in practice that m is usually around O(n) ()) to guarantee reasonable accuracy (Gong et al., 2013 Sánchez & Perronnin 2011 Yu et al. 2014). Much like linear JI. embedding techniques admit fast counterparts, fast binary embedding algorithms have been developed to significantly reduce the runtime of binary embeddings (Gong et al., 2012b] Liu al. 2011] Gong et al. 2012a 2013 Li al. [011 Raginsky & Lazebnik 2009). Indeed, fast JL transforms (FJLT) and Gaussian Toeplitz matrices (Yi et al. 2013), structured hashed projections (Choromanska et al. 2016), iterative quantization (Gong al.,
2012b), bilinear projection GGogg et al.1))) circulant binary embedding (Yu et al., Dirksen & Stollenwerk] 2018, 2017 Oymak et al. 2017 Kim et al. 2018), sparse projection (Xia et al. 2015). and fast orthogonal projection (Zhang et al. 2015) have all been considered.
These methods can decrease time complexity to (n log operations per embedding, but still suffer from some important drawbacks. Notably, due to the sign function, these algorithms completely discard all magnitude information, as sign(Aw) = sign( A (aæ)) for all a >> 0. So, all points in the same direction embed to the same binary vector and cannot be distinguished. Even if one settles for recovering geodesic distances, using the sign function in is an instance of MSQ so the estimation
error in decays slowly the number of bits increases YY et al. 2015).
In addition to the above data independent approaches, there are data dependent embedding methods
for distance recovery. including product quantization (Jegou et al. 2010 Ge et al. 2013), LSH-
based methods (Andoni & Indyk, 2006) [Shrivastaaa & Li] 2014] Datar et al. 20044 and iterative quantization (Gong et al.] (2012c). Their accuracy, which can be excellent, nevertheless depends on the underlying distribution of the input dataset. Moreover, they may be associated with larger time and space complexity for embedding the data. For example, product quantization performs k-means clustering in each subspace to find potential centroids and stores associated lookup tables. LSH-based methods need random shifts and dense random projections to quantize each input data point.
Recently Huynh & Saab (2020) resolved these issues by replacing the simple sign function with a Sigma- Delta (EA) quantization scheme, or alternatively other noise-shaping schemes (see (Chou & Güntürk 2016) whose properties will be discussed in Section 3 They use the binary embedding
qu = QDBrx)
where Q is now a stable ΣA quantization scheme, D E Rmxm is a diagonal matrix with random signs, and B mmx are specific structured random matrices. To give an example of ΣA quan- tization in this context, consider w == DBR. Then the simplest VA scheme computes qa via the following iteration, run for i 1, m:
uo 0, In (i) = sign (w; + 04-1),
(4)
14 Ui- 1 wi qi-
The choices of B in (Huynh & Saab, 2020) allow matrix vector multiplication to be implemented using the fast Fourier transform. Then the original Euclidean distance || -yll can be recovered via a pseudo-metric on the quantized vectors given by
di (qm: 9y)
Vi qu)ll2
(5)
2

---

Published as a conference paper at ICLR 2021
where V E IRxx is "normalized condensation operator", sparse matrix that can be applied fast (see Section 3). Regarding the complexity of applying (3) to a single æ E R", note that æ H DB has time complexity Onn logn) n) while the quantization map needs (mm) time and results in an m bit representation. So when m S n, the total time complexity for (3) around On log n).
1.2 METHODS AND CONTRIBUTIONS
We extend these results by replacing DB in (3) by sparse Gaussian matrix A R so that now
(6) Given scaled high-dimensional data T C R" contained in the & ball B3 with radius K, we put forward Algorithm [ generate binary sequences and Algorithm 2 to compute estimates of the Euclidean distances between elements of T via an & f1-mrrm rather than fo-nom. The contribution of this work threefold. First, we prove Theorem 1.1 quantifying the performance of our algorithms.
qu Q(Ax).
Algorithm 1: Fast Binary Embedding for Finite
Input: = { j== C (g (K)
Data points in &g ball >> Sparse Gaussian matrix A
Generate A E Rm as in Definition 2.2
for j
do
2() Ax(()
( = Q(z(1)
b Stable ΣA quantizer Q as in (4), or more generally 21
Output: Binary sequences B 1 S 11,,1
Algorithm 2: f2 Norm Distance Recovery
Input: (()) q0) B
Binary sequences produced by Algorithm 1 >> Condense the components of q
(
g000) + Vgli
Output: 1 -10--(11) (1)
Approximation of |[x( x x
Theorem 1.1 (Main result). Let T C R be a finite, appropriately scaled set with elements satis- (oog((T2///)) and 2 is fying || (1/n1//|[a]]) and | < 1. If m pp: Qi
25 on the draw of the sparse Gaussian matrix A. the following holds uniformly over all æ, y in T: Embedding x, into 1,1, 1)mh using Algorithm
the integer order of Q. then with probability
and estimating the associated distance between them using Algorithm vields the error bound
-r+1/2 1/2
dr 9y)
|
y112
771
+ E 8112
P
where 0 is constaur.
Theorem I.1 yields an approximation error bounded by two components, one due to quantization and another that resembles the error from a linear JL embedding into a p-dimensional p space. The latter part is essentially proportional to p 11/2, while the quantization component decays polynomially fast in m, and can be made harmless by increasing m. Moreover, the number of bits m Z E -2 (og((T)) achieves the optimal bit complexity required by any oblivious random embedding that preserves Eu- clidean or squared Euclidean distance, see Theorem 4.1 in (Dirksen & Stollenwerk 2020). Theorem 4.2 a more precise version of Theorem [.] with all quantifiers, and scaling parameters specified explicitly, and with potential modification to A that enables the result to hold for arbitrary (not necessarily well-spread) finite T, the cost of increasing the computational complexity of embed- ding point O log We also note that if the data did not satisfy the scaling assumption of Theorems 1.1 and 4.2 then one can replace [-1,1} by (-C, C.}, and the quantization error would
scale by
Second, due to the sparsity of A, (6) can be computed much faster than (3) when restricting our results to "well-spread" vectors I, i.e., those that are not sparse. On the other hand, in Section 5 we show that Algorithm|| achieves (m)) time and space complexity contrast with the common
Onn log n) runtime of fast binary embeddings, e.g., (Gong et al. 2013 Yi et al. 2015 Yu et al.
3

---

Published as a conference paper at ICLR 2021
2014
Dirksen & Stollenwerk 2018 2017: Huynh & Saab 2020) that rely on fast JL transforms circulant matrices. Meanwhile, Algorithm 2 requires only ((m) runtime.
Third, Definition 2.3 shows that V is sparse and essentially populated by integers bounded by
(m/p)" where P are as in Theorem 1.1 In Section we note that each y =Va (and the distance query), can be represented by O(p (mgg(m/p)) J Jits,, instead m bits, without affecting the reconstruction accuracy. This is a consequence of using the ---norm in Algorithm 2 Had we instead used an ly-norm, we would have required
(epplogg(m/p)))) bits.
Finally, remark that while the assumption that the vectors I well-spread (i.e. ||/| O(n 1/2 (nn11/2||an (x]l))) may appear restrictive, there are important instances where it holds. Natural im- ages seem to be one such case, as are random Fourier features (Rahimi & Recht] (2007). Sim- ilarly, Gaussian (and other subgaussian) random vectors satisfy slightly weakened |<]| ((log(n)n=1/211z)))
assumption with high probability, and slightly reducing the sparsity A (and slightly increasing the computational cost) to handle such vectors. On the other hand, if the data simply does not satisfy such an assumption, apply Theorem 4.2 part (ii), but now the complexity of embedding point O(n log n).
modify our construction by
still
2 PRELIMINARIES
2.1 NOTATION AND DEFINITIONS
Throughout, f(n) = (g(n)) and f(n) = ((g(n) mean that [f())] is bounded above and below
respectively by a positive function ((n) up constants asymptotically; that is, lim sup ((n)
[f(n]]
0o. Similarly, we use (n) - (g(n) to denote that f(z) is bounded both above and below by positive function (n) up to constants asymptotically. We next define operator norms.
Definition 2.1. Let a, 3 oo] be integers. The (a, B) operator norm of K Rmxx is
K |la = max,500 ||||
|
We now introduce some notation and definitions that are relevant to our construction.
Definition 2.2 (Sparse Gaussian random matrix). Let A (a.y) E mx be random matrix with i..dd entries such that a.j is 0 with probability 1 - and is drawn from A( !) with probability
We adopt the definition a condensation operator of Chou & Güntürk 2016:; 2020
Huynh & Saab
Definition 2.3 (Condensation operator). Letp, r, À be fixed positive integers such that À = 1 for some integer X. Let m Ap and v be row vector in R whose entry vj is the j-th coefficient of the polynomial (1 + z +... + x 21- Define the condensation operator V E Rpxx by
v
V Ip 80=
v
For example, when r = X, and o RRA,A is simply the vector of all ones. The normalized condensation operator is given by
V VT/2
The fast JI. transform was first studied by Ailon & Chazelle (2009). It admits many variants and improvements, e.g. (Krahmer & Ward 2011] Matoušek The idea is that given any æ T we use a fast "Fourier-like" transform, like the Walsh-Hadamard transform, to distribute the total mass (i.e. ||æ||2)) of æ relatively evenly its coordinates.
Definition 2.4 (FJLT). The fast JL transform be obtained by
Φ A ADD mm
4

---

Published as a conference paper at ICLR 2021
Here, A E R is sparse Gaussian random matrix, in Definition 2.2 while H E R is normalized Walsh-Hadamarr matrix defined by Hąj (-1 bitwise dot product of the binary representations of the numbers and j- Finally, D E Raxx diagonal with diagonal entries drawn independently from {-1,1} with probability 1/2 for each.
where (i.j) is the
2.2 CONDENSED JOHNSON-LINDENSTTR.E TRANSFORMS
Definition 2.5. When V is a condensation operator, and A is a sparse Gaussian, we refer to VA as condensed sparse JL transform (CSJLT). When A is replaced by o as in Definition 2.4 refer V d condensed fast JL transform (CFJLT).
The definition above is justified by the following lemma (see Appendix B for the proof).
Lemma 2.6 (CJLT lemma). Let T be finite subset of TR", À E N, E (0, 2 5
E (0, p- =
O log([T))/8)) E N and m Ap. Let V E Rpxm be as in Definition 2.3 be the sparse Gaussian matrix in Definition 2.2 with
A
E RMxx
O(c nn + = AHD Rmxa be the FJLT in Definition 2.4 with s = O(E n /
S
1. and
log S
T consists of well-spread vectors, that is, || O(n 2|])) for all x E then
V - 8)ll - 1| ull2 S <|| 8112
(8)
holds uniformly for all x, y E T with probability at least If is finite but arbitrary, then
| (( y)1l 1| 2l12 S <|| yllp
holds uniformly for all x, y E T with probability at least 5.
So T S TR is embedded into R with pairwise distances distorted at most 6, where p O (T]) one would expect from a JL embedding. This will be needed guarantee the accuracy associated with our embeddings algorithms. Note that the bound on p does not require extra logarithmic factors, in contrast to the bound ( -2 log IT log n) in (Huynh & Saab, 2020).
SIGMA-DELTA QUANTIZATION
An r-th order EA quantizer Q(+) RR' + 9 maps input signal y (,)) Rd via a quantization rule p and the following iterations quantized sequence = (q E Am
u-1
0, ()-)) for i
9: Q (p((t, p' y q
m,
(10)
where Q²y) = arg min A ly u| is the scalar quantizer related to alphabet A and P E mm is the first order difference matrix defined by
{
if
Pij
ifi=j+1,
otherwise.
Note that 100 is amenable to an iterative update of the state variables u.
P'u = y- = u Σ(-1p-1 (
Uss + ys ls 1
(11)
j=1
Definition 3.1. A quantization scheme is stable if there exists μ > such that for each input with ||u||oo C. Crucially, p and C' do not depend m.
1o μu, the state vector T satisfies
Stability heavily depends on the choice of quantization rule and difficult to guarantee for arbitrary p in I0p when the alphabet is small, is the case of 1-bit quantization where A {=1}. When
1 and A {1 the simplest stable ΣA scheme Q(1) m n equipped with the greedy quantization rule P(3/, u4-1) == U;-1 + y/ giving the simple iteration (4) from the introduction, albeit
with y replacing w. description of the design and properties stable Q(7) with r > 2 can be found in Appendix
5

---

Published as a conference paper at ICLR 2021
4 MAIN RESULTS
The ingredients that make our construction work are a JL embedding followed by EA quantization. Together these embed points into {+1]m², but it remains define pseudometric that we may approximate Euclidean distances by distances on the cube. We now define this pseudometric.
Definition 4.1. Let A [+ and let V RRxx with p S m. We define dy on A x A as
(q (2) = [V(g g2)ll V q Q2 E AM.
We now present our main result, more technical version of Theorem 1.I proved in Appendix D
Theorem 4.2 (Main result). Let X, E E. (0, 2) 8 (0, 8 2(log( (7))))
0.
E (0, 1). p =
E N, and m = Ap. Let V E _pxx be as in Definition
2.3
A Rmxx be the sparse Gaussian matrix in Definition 2.2 with s O(c n "[Ioll /||
1, and & be the FJLT in Definition 2.4 with s = O(
(1/0 /12)|12) l n) s 1.
||م|| S x} and suppose that Let be finite subset of B (k) == {o= E R2
2 B + (2g)
Defining the embedding maps f1 T { m by f1 = Q(+) A and f2 T + {+1}m by
fa = Q(1) o Φ. there exists a constant C(p,r) r) such that the following are true:
(i) the elements of satisfy || O( 1/2 |/11) then the bound
(1) - | vllæ - C(a, r) + <|| - y112
(12)
holds uniformly for all x, y T with probability exceeding - ô - -
(ii) On the other hand, for arbitrary T C (x))
(I2(a)) f2(1)) - | -1l2 S r(u, -++12 + <||x0 - y/12
(13)
holds uniformly for any y, E T with probability exceeding 1 - 5 - T -B
Under the assumptions of Theorem 4.2 we have
E - ov
log((T12/5)
(14)
P
VP
By 12 13 and 14). we have that with high probability the inequality
dy (f((2. - | -ull $ C(Hrr)
m
1/2
+ c||x
-yl12
-1+1/2
r(u,r)
2ne
p
-r+1/2
C2 VP
C(u,r)
(15)
p
V3 + log(2m)
holds uniformly for x, y T. The first term in 15) results from ΣA quantization while the second error term is caused by the CJLT. So the term (((m/p) -++1/2) dominates when À = m/p small. m/p is sufficiently large, the second term O(1/p)) becomes dominant.
COMPUTATIONAL AND SPACE COMPLEXITY
In this section, we assume that T= (1) 1 RD consists of well-spread vectors. Moreover, we 1==1
will focus on stable r-th order ΣΑ schemes Q(+) Rm + A with A = {-1,1). By Definition
2.3 when have (1, 1,.,, 1) IR while when = 2, (1,2, ... A- 1,

---

Published as a conference paper at ICLR 2021
= 2 = 0(c-'n--x- I as in Theorem 4.2 We consider b-bit floating-por -pontt or fixed-point representations for numbers. Both entail the same computational complexity for computing sums and products of two numbers. Addition and subtraction require O()) operations while multiplication and division require M(b) O(b²) operations via "standard" long multiplication and division. Multiplication and division can be done more efficiently, particularly for large integers and the best known methods (and best possible up to constants) have complexity ((b) =
1,,1..2,11 E RA* In general, /0/|>>/||e|] 0(X-1/2) holds for all r N. We also assume that $ = 0
(b log b) (Harvey & Van Der Hoeven 2019 We also assume random access to the coordinates of our data points.
Embedding complexity. For each data point a²(i T, one use Algorithm quantize it. Since A has sparsity constant ( -0===n----3 and e- O2p by (14), and since À = m/p, computing (z( needs (smm)
0(x m)) (p2) time. Additionally, it takes (mm)
time to quantize (x( based on 21 When pa/² < m, Algorithm [ can be executed in ((m) for each x()), Because A has O (ster)
(mm) nonzero entries, the space complexity is ((m) bits per data point. Note that the big O notation here hides the space complexity dependence on the bit-depth of the fixed or floating point representation of the entries of A and (,)) This clearly has no effect on the storage space needed for each g()), which is exactly m bits.
Complexity of distance estimation. If one does not use embedding methods, storing T directly, i.e., by representing the coefficients of each x ()) by b bits requires knb bits. Moreover, the resulting computational complexity of estimating ||æ: ylا where x:, y E T is O(n.((b))- On the other A by performing Algorithm Non T- hand, suppose obtain binary sequences B = 1 1 Using our method with accuracy guaranteed by Theorem 4.2 high-dimensional data points TC C IR" now transformed into short binary sequences, which only require km bits of storage instead of knb bits. Algorithm 2 can be applied to recover the pairwise & distances. Note that V is the normalization of an integer valued matrix V Ip v (by Definition 2.3 and q E A is binary vector. So, by storing the normalization factor separately, we can ignore it when considering runtime and space complexity. Thus we observe:
1. The number of bits needed to represent each entry of is at most loga (1<011so)) ~ (r 1) logg À = O(log2 A) when > 1 and O(1) when = 1. So the computation of y Vi E R2 only involves m additions subtractions of integers represented by Ologz A) bits and thus the time complexity in computing ())) is Om Omg2 A).
2. Each of the p entries of (f) is the sum of À terms each bounded by X We can store (+) in (pp log2 X) bits.
3. Computing 1 (1) ( needs O(p A) time and O(p log, A) bits.
So we use O(plog, A) bits to recover each pairwise distance
[x(()
x in Om A) time.
Method
Time
Space O(n)
Storage
Query Time
Gaussian Toeplitz. Yi et al. 2015)
(n log n) (nn/m)
((m)
((m)
Bilinear (Gong et 2013)
O ((ymn)
((m)
((m)
Circulant Yu et al. 2014)
(n log n)
O(n)
((m)
(
BOE or PCE (Huynh& & Saab 2020)
(n lon n)
(())
O(p Logg X)
Op. A))
Our Algorithm" (on well-spread 7
(m)
(()) OOp logg X)
Opplog A)
These algorithms recover Euclidean distances and others recover geodesic distances.
Table 1: Here "Time" is the time needed to embed a data point, while "Space" is the space needed to
store the embedding matrix. "Storage" contains the memory usage to store each encoded sequence. "Query time" is the time complexity of pairwise distance estimation.
Comparisons with baselines. In Table 1 compare our algorithm with various JL-based methods from Section [ Here n is the input dimension, m is the embedding dimension (and number of bits), and p- m/A is the length of encoded sequences Vq. In our case, we use O(plog2 X) to store y Vg. See Appendix for comparison with product quantization.
7

---

Published as a conference paper at ICLR 2021
-K-
12F
y- 165
165m
Dista Bistance HArE
Disaance
13"4
512
1024
2048
1024
8102
26384
(a) MAPE of Method 1 (r 1)
(b) MAPE of Method 2 (r = 1)
10F
139
- 165m
y- 165mm-30
Dioza ne HAVE
se MANE
10"
1024
2040
4096
8192
26.344
16384
(c) MAPE of Method (r
(d) MAPE of Method (r 2)
Figure 1: Plots of l2 distance reconstruction error when r y= 1,2
6 NUMERICAL EXPERIMENTS
To illustrate the performance of our fast binary embedding (Algorithm I and &g distance recovery (Algorithm 2 we apply them real-world datasets: Yelp open datase( ImageNet (Deng et al., 2009). Flickr30k (Plummer et al. 2017). and CIFAR-10 (Krizhevsky et al. 2010). All images are converted to grayscale and resampled using bicubic interpolation to size 128 128 for images from Yelp, ImageNet, and Flickr30k and 32 x 32 for images from CIFAR-10. So, each can be represented by a 16384-dimensional or dime-dimes vector. The results are reported here and in Appendix We consider the two versions of our fast binary embedding algorithm from Theorem 4.2
A
Method 1. We quantize FJLT embeddings 4æ, and recover distances based on Algorithm
Method 2. We quantize sparse JL embeddings Aæ and recover distances by Algorithm 2
In order to test the performance of our algorithm, we compute the mean absolute percentage error (MAPE) of reconstructed & distances averaged over all pairwise data points, that is,
2
Σ
[q
4y 11 | x
k(K
y
J.JTT
To give numerical illustration of the relation among the length m of the binary sequences, embedding dimension and order r, as compared to the upper bound in (15), we use both Method and Method 2 on the Yelp dataset. We randomly sample A 1000 images and scale them by the same constant so all data points are contained in the Ez unit ball. The 16384 and 1650/n z 0.1. For each fixed p. we apply Algorithm and Algorithm 2 for various m. We present our experimental results for stable ΣA quantization schemes, given by 2T). with r and 2 in Figure 1 For r = 1, we observe that the curve with small quickly reaches an error floor while with high the error decays like m -1/2 and eventually reach a lower floor. The reason is that the first error term in (15) is dominant when m/p p is relatively small but the second error term eventually dominates as
Experiments on the Yelp dataset.
scaled dataset is denoted by T. Based on Theorem 4.2 we set
Yelp open dataset: https//wwww.ycln.cm/daaas
8

---

Published as a conference paper at ICLR 2021
-K-
10
300m
Distanee MAPE
300m
Disaacee
10-1
236
1024
(a) MAPE of Method (p = 64)
(b) MAPE of Method 2 (p = 64)
-X--
Ditance NOPE
y=m
Ditannce
2011
128
(c) MAPE of Method (p = p(m)
(d) MAPE of Method 2 (p = p(m))
Figure 2: Plots of distance reconstruction error with fixed p = 64 and optimal p = p(m)
m becomes larger and larger. When r r= 2 the error curves decay faster and eventually achieve the same flat error because now the first term in (15) has power -3/2 while the second flat error term is independent of r. Moreover, the performance of Method 2 is very similar to that of Method 1.
Next, illustrate the relationship between the quantization order and the number of measure- ments in Figure 2 The curves obtained directly from an unquantized CFJLT (resp. CSJLT) as in Lemma [.66] with m 256, 512, 1024, 2048, 4096, and p 64 are used for comparison against the quantization methods. The first row of Figure 2 depicts the mean squared relative eтror when p = 64 fixed for all distinct methods. shows that stable quantization schemes with order outperform the first order greedy quantization method, particularly when m is large. Moreover, both the r = 2 and r 3 curves converge to the CFJLT/CSJLT result as m goes to 4096. Note that by using quarter of the original dimension, i.c. m 4096, construction achieves less than 10% error. Furthermore, if we encode Vq as discussed in Section 5 then need at most rp log, A = 64r log, 1o (4096/64) 384r bits per image, which is S 0.023 bits per pixel.
For our final experiment, we illustrate that the performance of the proposed approach can be further improved. Note that the choice of only affects the distance computation in Algorithm and does not appear in the embedding algorithm. improve performance. This can be done either analytically by viewing the right hand side of (15) as a function of p and optimizing for p (up to constants). It can also done empirically, as we do here. Following this intuition, if we vary
other words, one can vary p in Algorithm 2 to
function of and use the empirically optimal p = p(m) in the construction of V, then obtain the second row of Figure 2 where the choice r = exhibits lower error than other quantization methods. Note that the decay rate, as a function of m, very closely resembles that of the unquantized JL embedding particularly for higher orders (as one can verify by optimizing the right hand side of (15
ACKNOWLEDGMENTS
Our work was supported part by NSF Grant The authors would like to thank Sjoerd Dirksen for inspiring discussions and suggestions.
and a UCSD senate research award.

---

Published as a conference paper at ICLR 2021
REFERENCES
Nir Ailon and Bernard Chazelle. The fast linissnn-iiddesttausss transform and approximate nearest neighbors. SIAM Journal on computing, 39(1):30--322, 2009.
Nir Ailon and Edo Liberty. An almost optimal unrestricted fast johnson--inddentraass transform.
ACM Transactions on Algorithms (TAAssTTAAAA (TALG), 9-3):1-12, 2013.
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neigh- bor in high dimensions. In 2006 47th anmual IEEE symposium on foundations computer science (FOCS (FOCS)06), pp.
IEEE, 2006.
Anna Choromanska, Krzysztof Choromanski, Mariusz Bojarski, Tony Jebara, Sanjiv Kumar, and Yann LeCun. Binary embeddings with structured hashed projections. In International Conference on Machine Learning. pp. 344-353, 2016.
Evan Chou and C Sinan Güntürk. Distributed noise-shaping quantization: beta duals of finite frames and near-optimal quantization of random measurements. Constructive Approximation, 44 (1):1-22, 2016.
Kenneth L Clarkson and David Woodruff. Low-rank approximation and regression in input spar- sity time. Journal of the ACM (JACM), 63(6): 2017.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni. Locality-sensinee hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pp- 253 263, 2004.
Ingrid Daubechies and Ron Derer Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order. Annals of mathe- matics, 158(2):679-710, 2003.
Percy Deift, Felix Krahmer, and C Sinan Güntürk. An optimal family of exponentially accurate one-bit sigma-delta quantization schemes. Communications Pure and Applied Mathematics, 64(7):883-919, 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Sjoerd Dirksen and Alexander Stollenwerk. Fast binary embeddings with gaussian circulant ma- trices. In 2017 International Conference on Sampling Theory and Applications (SampTA), pp- 231-235. IEEE, 2017.
Sjoerd Dirksen and Alexander Stollenwerk. Fast binary embeddings with gaussian circulant matri- ces: improved bounds. Discrete & Computational Geometry, 60()):599-626, 2018.
Sjoerd Dirksen and Alexander Stollenwerk. Binarized Johnson-llndenstren embeddings. arXiv preprint arxiv:2009 08320, 2020.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2946-2953, 2013.
Yunchao Gong, Sanjiv Kumar, Vishal Verma, and Svetlana Lazebnik. Angular quantization-based binary codes for fast similarity search. In Advances in neural information processing systems, pp- 1196-1204, 2012a.
Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE transactions on pattern analysis and machine intelligence, 25(12):2916-2929 2012h 2b.
Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE transactions on pattern analysis and machine intelligence, 29(1)):216-2999) 2012c
10

---

Published as a conference paper at ICLR 2021
Yunchao Gong, Sanjiv Kumar, Henry A Rowley, and Svetlana Lazebnik. Learning binary codes for high-dimensional data using bilinear projections. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 484 2013.
Sinan Güntürk. One-bit sigma-delta quantization with exponential accuracy. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 56(1 I): 16000 2003.
David Harvey and Joris Van Der Hoeven. Integer multiplication in time o (n log n). Preprint, 2019.
Thang Huynh and Rayan Saah. Fast binary embeddings and quantized compressed sensing with structured matrices. Communications on Pure and Applied Mathematics, 73(1):110-144) 2020.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117-122, 2010.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. 1984.
Contemporary mathematics,
Daniel M Kane and Jelani Nelson. A derandomized sparse johnson--inndestrruss transform. arXiv
preprint arXiv:1006.3585 2010.
Daniel M Kane and Jelani Nelson. Sparser Johnson-lindenstraane transforms. Journal of the ACM (JACM), 61(1):1-23, 2014.
Sachoon Kim, Jungtaek Kim, and Seungjin Choi. On the optimal bit complexity of circulant binary embedding. In AAAI, pp. 3423-3430, 2018.
Felix Krahmer and Rachel Ward. New and improved johnson-lindenstraus. embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis,
2011.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced re-
search). URL http:///ww. cs. toronto. edu/kriz/cifar. html, 5, 2010.
Ping Li, Anshumali Shrivastava, Joshua I. Moore, and Arnd C König. Hashing algorithms for large-
scale learning. In Advances in neural information processing xystems, pp. 2672-2680, 2011.
Wei Liu, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. Hashing with graphs. In ICML, 2011.
Jiří Matoušek. On variants of the johnson-iindenstraus lemma. Random Structures & Algorithmss, 3362):142-156, 2008.
Jelani Nelson, Eric Price, and Mary Wootters. New constructions of rip matrices with fast multi- plication and fewer rows. In Proceedings of the twenty-fitth annual ACM-SIAM symposium on Discrete algorithms, pp. 1515-1528. SIAM, 2014.
Samet Oymak, Christos Thrampoulidis, and Babak Hassibi. Near-optimal sample complexity bounds for circulant binary embedding. In 2017 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 6359-6361 IEEE, 2017.
Bryan A. Plummer, Liwei Wang, Christopher M. Cervantes, Juan C. Caicedo, Julia Hockenmaier, and Svetlana Lazebnik. Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentenct models. IJCV, 123(1):74-93, 2017.
Maxim Raginsky and Svetlana Lazebnik. Locality sensitive binary codes from thift-invariant ker- nels. In Advances in neural information processing systems, pp. 1509-1517, 2009.
Locality-sensitive
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20:1 20:1177-1184, 2007.
Jorge Sánchez and Florent Perronnin. High-dimensional signature compression for large-scale im- age classification. In CVPR 2011, pp. 1665-1672. IEBE, 2011.
Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Artificial Intelligence and Statistics, pp. 886-894, 2014.

---

Published as a conference paper at ICLR 2021
Yan Xia, Kaiming He, Pushmeet Kohli, and Jian Sun. Sparse projections for high- diheemsiensionl binary codes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3332-3339, 2015.
Xinyang Yi, Constantine Caramanis, and Eric Price. Binary embedding: Fundamental limits and fast algorithm. In International Conference on Machine Learning, pp. 2162 216222122220 2170, 2015.
Felix Yu, Sanjiv Kumar, Yunchao Gong, and Shih-Fu Chang. Circulant binary embedding. In International conference on machine learning, pp. 946-9446999 2014.
Xu Zhang, Felix Yu, Ruiqi Guo, Sanjiv Kumar, Shengjin Wang, and Shi-Fu Chang. Fast orthogo- nal projection based on kronecker product. In Proceedings of the IEEE International Conference on Computer Vision, pp. 9929-29399 2015.
A COMPARISONS ON DIFFERENT DATASETS
-X- Yelp with r=1
10
ImageNet with r=1
Flickr30k with
CIFAR-10 with r=1
3x
* Yelp with r=2
ImageNet with r=2
Flickr30k with r-2
CIFAR-10 with r=2
Distance MAPE
2
10-1
512
1024
2048
4096
8192
16384
m
Figure Plot of MAPE of Method 2 on four datasets with fixed p 64 and order 1,
Experiments on the Yelp dataset in Section 6 showed that Method based sparse embeddings performs as well as Method 1 which usues an FJLT to enforce the well-spreadness assumption. Now, we only focus Method 2 and check its performance all four different datasets: Yelp, ImageNet, Flickr30k, and CIFAR-10.
Specifically, for each dataset we randomly sample A 1000 images and scale them such that all scaled data points are contained in the E, unit ball. Then we apply Method 2 to each dataset separately and compute the corresponding MAPE metric, see Figure where we fix = 64 and let fluctuate, but displays clear downward trend, when
2. We can observe that curves with m < 8192 and reach an error floor around 0.08. In contrast to the first order quantization scheme, curves with Method 2 performs well on all datasets and implies that assumption well-spread input vectors is restrictive natural images.
decays faster and eventually achieve lower floor around 0.07. Additionally,
12

---

Published as a conference paper at ICLR 2021
B PROOF OF LEMMA 2.6
We will require the following lemmas, adapted from the literature, to prove the properties of our condensed sparse Jahnson-Lindenstruuss transform (CSJLT) and condensed fast Laanson-Lindenstrauss transform (CFJLT) in Lemma 2.6
Lemma B.1 (Theorem 5.1 Matoušek 2008)). Let n N. (0, 8 (0,1), a 1 1]
be parameters and sei - loog s 2a /e S A I mm be as Definition
N where C' is sufficiently large constant. Let
2.2
Then
VT/2
P((1-e)ll S
|A s (1 + e)12=l12) 21 1 -
(16)
holds for all x E IR" with || S a||20|12-
Lemma B.2 below is adapted from (Ailon & Chazelle 2009 Lemma 1), and present its proof for completeness.
Lemma B.2. Lei H Raxa and D E Raxx be as Definition 2.4 For any > and x E Tk we have
P [1HD2 S Al|zlll)) 2 1 -2ne n2
(17)
Proof. Without loss of generality, we can assume |a112 = 1. Let u HDz (11, Un Fix
i E [l....,m.. Then E ayd with P aj = Ja = P(a, - 2 for all j.
Moreover, a,, 02,..., On are independent and symmetric. So u, also symmetric, that is, ue and share the same distribution. For any / E I we have
exp(tv/nz,) exp((tt/nz,)
E (ma)
II E Eexp((nna,7,)
II j=1 n
II j=1
exp(nt exp(nt 12).
Since uN is symmetric, by Markov's inequality and the above result, we get
P([ue] 2 A) PP e "n) S 2e A""E(e) = 2c 22n/2
Inequality 17 follows by the union bound over all i E n1.
Lemma B.3. Let n, E N. e E (0,
(1, 8 E (0,1), = OlE 2 log(( E N and m = Ap. Let
V E p be as in Defimition
2.3
A E Rmxn be the sparse Gaussian matrix in Desinition
2.2
with - (1|0 /
2
S 1, and + = AHD E Ruxn be the FJLT in Definition
2.4
with = O n (1 [z
log S 1. Then for x E TR. with ||0:|00 = O(n 1/2
||x
12)
we have
P (1 - =] < V Ax//1 s (1 (1++e) (1+1))=)122 2 21-8,
(18)
for arbitrary E RR, we have
P((1 p((1-e)l e)|1=|12 - Vo0l < (1 + 2 1
(19)
8 For Sig p and S n, we have
Proof. Recall that V = I and $ AHD. Let y E R K = VA = (I,8U)A
Kij
Denote the row vectors of A by a1, a2,..... Am- follows that
(Ky); Σ
Kig8; ΣΣ
Σ
uk a a [
1=1 k=
13

---

Published as a conference paper at ICLR 2021
where
a1
a2
aA
ax+1
ax+2
a2x
V2y
B
E
R
and v'
E R
a (p- 1JA+1 A(p- 1)2+2
ApA_
Hence VAy = Ky- = B( s y) holds for all y E IR.. Additionally, we get a reshaped sparse Gaussian random matrix B by rearranging the rows of A.
For the first assertion the theorem, note that æ E R" satisfies || = [ 2/vn). So, we have V Ax = B(v 8w),, | @ @01122 = ||>||||a=||z and || @ @ | || Then (18) holds by applying Lemma B.1 to random matrix B and vector v 60 with = O(n Onn-1/2 || 22
For the second assertion, if x: E IR. is arbitrary, then by substituting HDv for y one can get
v B(v (HDz)).
Note that ||lT @ (HDæ)ll2 = || HD2/22 = |2 and || @ (HDx) || HDx so.
Inequality (19) follows immediately by using the above fact and applying Lemma B. and Lemma
B.2 to the random operator B and vector wt & (HDx) with = O(n log n) 1/2 b0/ l2)
Now can embed set of points in high dimensional space into space of much lower dimension in such a way that distances between the points are nearly preserved. By substituting 6 with 26 T
28 in Lemma B.3 and using the fact 1 (Z) π-.² 1 1711
28
> 1 6, Lemma 2.6 follows
TT
from the union bound over all pairwise data points in T.
C STABLE SIGMA-DELTA QUANTIZATION AND ITS PROPERTIES
Although it is a non-trivial task to design a stable quantization rule p when r > 1, families of one- bit ΣΛ quantization schemes that achieve this goal have been designed by Daubechies Vore (2003; Güntürk (2003); Deift et al. (2011), and we now describe one such family. To start, note that an r-th order ΣA quantization scheme may also arise from a more general difference equation of the form
(20) where * denotes convolution and the sequence f = P"g with E f. Then any (bounded) solution of (20) generates (bounded) solution u of (11) via u g * v. Thus (T) can be rewritten in the form (20) by change of variables. Defining h = ((0) f. where (0)) denotes the Kronecker delta sequence supported at 0, and choosing the quantization rule in terms of the new variable as (h v): + ys. Then (TO) reads as
y y q = f=
= Q( * v); + 3,), (h v); + y/: 4--
(21)
By designing proper filter h one can get stable r-th order ΣA quantizer,
done in Deift
let al. (201T); Güntürk (2003), leading to the following result from Güntürk (2003), which exploits the above relationship between e and bound ||u||oo.
+ Proposition C.I. Fix an integer r, an integer 2 6 and let = o(j - 1)² + + j = 1,2,..., Let the filter h be of the form
d,80s
j=1
where 8 is the Kronecker delta supported at ny and dy = II ".
n-nn for 1,2,...,
r. There
exists universal constant C > 0 such that the rth order EA scheme (21) with 1-bit alphabet 11,,1], stable, and
lBo/loo <p<l= 1|2llbo S ColuTr'
(22)
where c(p) > 0 is constant only depends on μ..
14

---

Published as a conference paper at ICLR 2021
Having introduced stable Σλ quantization, now present lemma controlling operator norm of VP'. We will need this result in controlling the error in approximating distances associated with our binary embedding.
Lemma C.2. For a stable r-th order EA quantization scheme,
[VP" 1..1 S / 1
Proof.
By the same method used in the proof of Lemma 4.6 in Huynh & Saab 2020), one can get
V P' 100,00 S <22rr1 and || 2 X -7
It follows that
VT22 p|l1|2
vT22 ||o||
IV
b0,1
V P
bo,1 S
Prl 100,00 S (
The following result guarantees that the linear part of embedding generates a bounded vector, and therefore allows us to later appeal to the stability property of Σı quantizers. In other words, it will allow to use (22) control the infinity norm state vectors generated by Σ' quantization.
Lemma C.3 (Concentration inequality for || [1- Let 3 > 0, E (0, 1). A E Rmxx be the sparse
Gaussian matrix Definition 2.2 with s = Oe--In 1) 1, and
AHD E mxx be the FJLT
in Definition 2.4 with O -n logn) I 1. Suppose that
4
2 3 log(2m) S 5 Ve
(23)
Then
P(IAAx|1 S {p1z012) 2 1 - e0
(24)
holds for x E RRns with | O(n-1/(1))))) 1/2 (aan1//||=>l1)) and
P1| S (||ا||ا) 2 1 2
(25)
holds for E R
Proof. Without loss of generality, we can assume that x is a unit vector with | = 1. We start with the proof of 255 By applying Lemma B.2 to a with A e(Vlog no)n, we have
PIIHD==/ lo s <x) 2 - 1
(26)
Let A be as in Definition 2.2 with s = 2X² /e- = O - 1n -1 log n) S and recall that AHD.
Suppose that E T with | = 1 and - S x. Let Y = Ay. Then Y, == (Ay);
Ej=1 Aiylij for 1 < < m. For 1 < to /2s/> = 2/VE, we get ("y 22s < 1 for all j. Since
e" < 1+2x for all E [0, 1] and 1+x S et for all x E R, set" 23/2= +1-s < (1+ /3)
1 - V3 < c PV. It follows that
n
B(e = II E(e (am))
II
of
25 + 1 5)
e 3 e²
se
1=1
j=1
j=1
holds for all 1 isis m and t E [0,to]. So fort e [0, tol. by Markov inequality and above inequality have
P(Y:2H) = P p(ctti2elt)
2 ) S se-
(e-(e(( s -mute
According to (23) we can set t = 112 < to 2/, then (Yx 2 R) 12/12/4 By symmetry we
p(Y;
have P -Y-2 p) ---12/4 12/4 Consequently, for all 1 < < m we have
P(Ixa 2 m) < 22-="² -²/4
(27)
15

---

Published as a conference paper at ICLR 2021
By union bound, 23 and 27
Aylle 2 n) = P
max 1sism
|ú 2 24) S mP (
2me 12/4 < -
(28)
It follows immediately from 226 and
28
with y = HDD that
P( 1 $ (i)
P( A AHD=| so S μ))
S μ., |HD 20 _
PD] do S μ |HD 1o0 S A) HDe 1o0 S 2)
2 e
2 1 -1-20 22-2e-4 2
Furthermore, if replace y by in 28 and use A with O(c-'n then inequality (24
follows. The difference in the choice of is due to the fact that for vectors in the unit ball with ||0]| O(n 1/2 (//[|//(
have that ||>|||> I 1n/2
D PROOF OF THEOREM 4.2
Proof. Since the proofs of (12 and (13) are almost identical except for using different random projections A and we shall only establish the result for (13) in detail. For any T B (x)
we have [ 12 I K. By applying Lemma C.3 we get
P(| <n) 2 P( @ < 21|z112/k)
2 (1 @ 2 log(2m)] ||=||2)
2 1 2e -9
Since above inequality holds for arbitrary
T. by union bound one can get
P max TET
px 2 < 11)
2
Suppose that Ug is the state vector of input signal 4ax which is produced by stable r-th order ΣA scheme. Using Lemma C.2 and formula (22) to get
VV' bo,, Uw loc S Cc(w))r"(8r) V -+11/2
(29)
which holds uniformly for all æ T with probability exceeding -
Furthermore, by Lemma 2.6 the probability that
(( 1) || 7ll2 S c||x
8/12
(30)
holds simultancously for all æ, y T is at least - 8.
We deduce from triangle inequality and equations
30 that
de (f2(z) || =vll
(QQ1) ( - || vlla
[VQ (2x) ( - - ( - -y]l + V 1))1 - | y112
& ((Q"") (0x) - Φx) - (( (By) Φy) 11 +
V - b) - || - -ylla
VP' + P un + | ( will
|| - 2112
VP''l ll + 11 + V - w)ll - | - -vll
(Bc( / 7/2 121 + <|| 4//2
(2 +1 r 1/2 +e|l - 4/12
-(r,1))-++1/2 c| 1/1
16

---

Published as a conference paper at ICLR 2021
holds uniformly for any æ. E T with probability at least - e The bound T2) associated with a weaker condition on | due to the associated weaker condition Lemma C.3
E COMPARISON WITH PRODUCT QUANTIZATION
Note that the distance preserving quality (as well as performance on retrieval and classification tasks) of MSQ binary embeddings using bilinear projection (Gong et al. (0013) circulant matrices Yuu
ct al. 2014) has be shown to be at least as good as product quantization (Jegou et al.) 2010). LSH
Andoni & Indyk 2006 Shrivastava & Li. 2014) and ITQ (Gong et al. 2012c). Our method uses
Sigma-Delta quantization, which
1. gives provably better error rates than the MSQ design as shown in this paper, and in (Huynh & Saab 2020);
2. is more efficient in terms of both memory and distance query computation as shown in Section [
In order to more explicitly compare our algorithm with data dependent methods, as an example, we now briefly analyze product quantization as presented in (Jegou al. 2010). We then present a brief analysis of optimal data-independent methods as well as data-independern product quantization, in comparison with our method.
DATA- ENTA-DEPENDENT PRODUCT QUANTIZATION
The key idea here is decompose the input vector space R" into the Cartesian product of M low-dimensional subspaces Rd with n = Md d and quantize each subspace into k" codewords, for example by using the k-means algorithm. So the total number of centroids (codewords) in I is k = ( and the time complexity of learning all centroids is O(nNk=1) where N is the number of training data points and is the number iterations in the k-means algorithm. Moreover, converting each input vector x E IR" to the index of its codeword needs time (k = O(nk*) and the length of binary codes is m log, and M lookup tables, memory usage is ( + (k))²)) Onk M(k") )2). Moreover, the query time, i.e. the time complexity of pairwise distance estimation O(Mk") using lookup tables.
M log, k Since we have store all A centroids
As result, we obtain Table 2 whose column headings are analogous to those in Table
Method
Time
Space
Storage Ol k.) O(p logz X)
Query Time O(Mk)) Opplog, X)
Product Quantization
Olnk")
O(nk ((k))²) 0(m)
Our Method (on well-spread 7)
((m)
Table 2: Comparison between the proposed method and product quantization per data point
A direct comparison of the associated errors is not possible due to the fact that the error associated with data-dependent product quantization is a function of the input data distribution, and the conver- gence of the k-means algorithm. Nevertheless, one can note some tradeoffs from Table 2 Namely, the embedding time and the space needed to store embedding matrix are lower than those asso- ciated with product quantization. On the other hand, the space needed to store the embedded data points and the query time associated with product quantization depend on the parameter choices M and k", which also affect the resulting accuracy. Finally, we note that product quantization (using k- means clustering) is associated with rre-processing time O(nNk"t)) which is significantly larger than our method.
DATA-INDEPENTE
PRODUCT QUANTIZATION AND OPTIMALITY OF OUR METHOD
If one were to just encode, a data independent way, the & ball of R", so that the encoding error is at most 0, then simple volume argument shows that one needs at least 8-n codewords, hence n log, (1/0) bits. This lower bound holds, independent of the encoding method, ie., whether one uses product quantization any other technique. To reduce the number of bits below n, one
17

---

Published as a conference paper at ICLR 2021
approach is to capitalize on the finiteness of the data, and use JL type embedding (such random sampling for well-spread data) to reduce the dimension to p = log (up to log factors), and therefore introduce new embedding error of e, top of the encoding error. The advantage is that one would then only need to encode an &2 ball in the p-dimensional space. Again, independently need p poog(1/ /0) bits to get encoding error of O. If
of the encoding method, would denote C2. Cy. the encoding of æ and y, then this gives the error estimate
||le- Gyll || v|| S 0 + e||xr vll-
If we rewrite the enror now in terms of the number of bits b plog(1/8). get
||le- - Tyll - | x|l| - b/p + e||a - =1l-
Note that in all of this, no computational complexity was taken into account.
One can envision replacing k-means clustering in product quantization, with a data-independent encoding. With careful choice of parameters, this may be significantly more computationally efficient than the above optimal encoding, albeit at the expense of sub-optimal error bound.
On the other hand, consider that our computationally efficient scheme uses bits, and that those m bits can be compressed into = rp rolog(m//) /p) bits (see Section 5). then our error, by Theorem 4.2 is
|||c, Gyl
||
ylll x (mmmp))++1) e|| v/1
which in rate- cate-distortion terms is
- -yll || x|l| $ 2-- <|| yll-
In other words, up constants in the exponent, and possible logarithmic terms, our result is near- optimal.
18


Reviews:
[{"review_id": "vCXAWuVhc4f", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a new mapping of Euclidean vectors to bit vectors (quantization), along with a de-quantization method. The method is closely related to recent work by Huynh & Saab (2020), but instead of using a random rotation DBx on the input vector x, a sparse, Gaussian random projection is used. Under the assumption that the mass of x is \"well spread out\" this mapping also preserves Euclidean distances, but is quicker to compute (assuming random access to entries of x). After this mapping, a so-called Σ∆ quantization method is used, following Huynh & Saab.\n\nThe main issue I have with the paper is that there is no adequate comparison with quantization methods other than Σ∆ quantization. Notably, there is no comparison with product quantization (IEEE transactions on pattern analysis and machine intelligence, 2011). (Though it is presented as a data dependent method, it also makes sense as a data-independent method.) Also, LSH-based methods like simhash, and binarized E2LSH are not considered. It would also be helpful for the reader with a comparison to *data dependent* schemes, e.g. \"Practical Data-Dependent Metric Compression with Provable Guarantees\", NeurIPS 2017. Finally, there are related works in the theory literature that should probably be cited, e.g. \"Optimal Compression of Approximate Inner Products and Dimension Reduction\", FOCS 2017 (relevant for the case of normalized vectors).\n\nAnother claimed contribution, a speedup from O(n log n) to O(m) time, is not surprising (or new): It is known that for well spread vectors, even random sampling is an optimal dimension reduction method. (I think this goes back at least to Ailon and Chazelle.)\n\nThe writing can be made clearer. Even though I worked on related things, I found several parts of the paper hard to make sene of. For example:\n\n- The abstract suggests that the results apply to all vectors that are not sparse, but in fact they apply only to vectors that satisfy a hard-to-satisfy L-infinity norm restriction.\n- The abstract does not make clear that random access to the input vector is assumed, making it hard to understand how time less that O(n+m) is possible.\n- Algorithms 1 and 2 in the introduction are impossible to understand without reading section 3 first. Maybe give a special case, with explicit details, and the general case later or in appendix?\n- I suspect some assumption is missing in Theorem 1.1: The set of possible distances d_V(q_x,q_y) is finite, yet is supposed to be able to express the distance between arbitrary vectors x and y in R^n ...!\n- The start of section 5 seems to imply that one can assume that vectors are well spread without loss of generality, by applying a random rotation. However, for random rotations the l-infinity norm will exceed the required norm by a factor sqrt(log n) with high probability.\n- Is it important that L1 distance is used in algorithm 2, rather than L2 distance? After all, these distances are similar up to scaling for \"spread out\" vectors.\n- Out of curiosity: Did you consider Kashin's representations of vectors?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "k_9ijVXV3M8", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies binary embeddings that preserve Euclidean distances for the case when the vector mass is spread fairly evenly across the coordinates, which is a very common case in practice.\n\nWhat the paper essentially does is a standard observation that uniform subsampling of coordinates (in spirit of Ailon -- Chazelle) of such dense vectors gives a Johnson--Lindenstrauss guarantee on the pairwise distances, and then it uses the quantization procedure developed earlier by Huynh and Saab.\n\nTo me the result sounds like a fairly straighforward ramification of the result of Huynh and Saab, but I can see it potentially being accepted, since the studied problem is extremely important.\n\nI'm happy to revise the score if I got something wrong and the main resul is _not_ a straightforward variant of Huynh--Saab.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fkxZhnI2HGv", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a distance preserving embedding algorithm to reduce the dimensionality / encoding of a high dimensional Euclidean point-set. The proposed embedding is a combination of stable noise-shaping quantization and sparse Johnson-Lindenstrauss transformations. The proposed method requires O(m) time and space complexity. The main contribution of the paper is Theorem 1.1 where the authors prove a bound on the distortion of the proposed embedding. The (additive) distortion consist of two terms due to the quantization error and JL relative error.\n\n\nReasons for score:\nOverall, I vote for a slightly below acceptable due to the following concerns: (a) after reading the paper it was not clear if the authors do assume that the input pointset are well-spread or not. Theorem 1.1 states that the input points are well-spread and moreover Algorithm 1 assumes (implicitly) that the input is normalized. (b) the time complexity of the embedding is O(m) for well-spread vectors. In the first sentence of Section 5, the authors state that well-spread vectors can be assumed after an fast JL transformation. Indeed, but then the running time is not O(m), right? To transform any point-set to well-spread position you need at least O(nlogn).\n\nStrong points:\n* Well written paper with a clear contribution statement\n* Concise algorithm description and corresponding theoretical guarantees.\n\nConcerns:\n* References to input sparsity time embedding (see below) are missing. How does your results compare to these papers?\n* Theorem 1.1: Is the main contribution here the quantization part of the statement? It is known that the input pointset can be efficiently projected to p dimensions. Is it possible to decouple your contribution on quantization with JL projections?\n* Theorem 1.1: Isn't the assumption of well-spreadness too strong here? If the vectors are so well-spread, I believe that uniformly sampling of coodinates could also work. Please discuss it in the paper.\n\nMinor comments:\n*Introduction: what is an $\\epsilon$-Lipschitz distortion? Do you mean (1+\\eps) distortion?\n*Introduction: You may want to compare/discuss your work with input sparsity embeddings by Woodruff and Clarkson \"Low Rank Approximation and Regression in Input Sparsity Time\" and relevant count-min sketch embeddings.\n* Algorithm 1: does algorithm 1 requires scaled data points or is this required only for the analysis?\n* Equation (20) is referenced quite early. Please consider introducing it earlier.\n* Theorem 1.1: \"with high probability\" -> this can be made more explicit using the \\delta parameter as in the appendix.\n* In general, there are several forward looking references in the text (\"Finally, Definition 2.3 shows..\", \"Equation (20)\". Please minimize such forward references.\n* Theorem 4.2: Isn't it better to fix \\beta to be greater than O(ln |T| / \\delta). Otherwise the probability statements involve negative probabilities.\n* Section 5, first sentence: rephrase the \"without of loss of generality\" statement.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RcRMX2rt1Z", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the author proposed a fast, distant-preserving, binary embedding algorithm. This is in contrast with most binary embedding methods in mapping and recovery. Their method is fast and memory efficient, and accurate, so that the error is compared to that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization error. In addition to theoretical results, the authors also test the proposed algorithm on nature images, showing strong performance of their method.\n\nThe strong points includes\n+Proposing a new binary embedding algorithm\n+Providing theoretical results of approximate error\n+Empirical results supporting the superiority of the proposed method\n\nThe weak points includes\n-Some parts not easy to follow\n-Experiments could be remarkably improved\n\nOverall, the technical part looks strong, but the presentation and experiment could be improved.\n\nFirst, the introduction part is difficult to follow, since too many symbols are used in this paper while some of which are not explained at all. Besides, in Lemma 2.6, it is unclear where to use $s$.\n\nSecond, the proposed algorithm is tested on one real-world dataset based on distance reconstruction error, and compared with FJLT. It could be much convincing if more datasets, more metrics, and more baselines are considered. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "BTs5EfXjjdx", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a scheme for fast distance-preserving binary embeddings of R^n into {-1/+1}^m. Guarantees are given for embedding l2-distance in the host space. Under certain assumptions about the input data both encoding and decoding can be done in O(m) time/space, which improves substantially upon the O(n log n) complexity from the previous work. Compared to the previous work by Huynh and Saab (2020) and Chou and Gunturk (2016) the key idea is to apply condensed JL transform instead of the Sigma-Delta quantization or other quantization methods used by the previous work. This is a very natural idea and it is somewhat surprising that this hasn’t been done before. \n\nThe overall technical result is highly technical to state (Theorem 4.2) so I won’t attempt to fully reproduce it here. On a technical level the results in this paper are hardly too surprising for the JL community, but it is nice to see this analysis worked out in detail. The key weakness of this paper is that in order to get optimal time/space complexity strong assumptions on the input vectors are required. The well-spread assumption used in the paper roughly corresponds to saying that the input vectors look like +/- O(1) in most coordinates, which might be unrealistic in the case of inputs with a small number of large coordinates. Despite this shortcoming, I think the paper is still going to be of moderate interest to the theoretical community.\\\n\nOverall, the paper is clearly written and presents and contributions well within the landscape of the previous work.\n\nOther comments:\n\n-- Maybe I missed it but it might be useful to add some discussion regarding the optimality of the first term in the bound in Theorem 1.1, i.e. is this term required?\n\n-- Enlarge images and font sizes in Figure 2\n\n-- Experiments are done one small data (500 128x128 images) -- this is not very convincing for a big data paper.\n\n-- Is MAPE the right metric for image compression?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a new distance preserving embedding based on a recent result called sigma-delta quantization. The authors notice that in many realistic scenarios, the input vectors are well-spread and under assumptions regarding the spreadness provide a fast technique to convert the input vectors into binary vectors, possibly of lower dimension. For completeness, the authors analyze the setting where the vectors are not spread and show that by using a randomized Walsh-Hadamard transform, their results still apply.
The authors do not provide a completely novel approach, to quote R2 “On a technical level the results in this paper are hardly too surprising for the JL community, but it is nice to see this analysis worked out in detail”. That being said, they show that a natural idea indeed works out by providing both a theoretical analysis and experimental results. The experiments can be more thorough but do convey the point that the result indeed works and moreover is somewhat robust in that it works well even when the formal requirements do not entirely hold.
There are a few issues mentioned by the reviewers that should be addressed: A clearer exposition of the guarantees and assumptions, some comparison with previous papers. However given the responses and discussions these seem minor and fixable towards a camera ready version. I recommend accepting the paper

Decision: Accept (Poster)