Provable Quantization with Randomized Hadamard Transform
arXiv:2605.13810v1 [cs.LG] 13 May 2026
Ying Feng [email protected]
Piotr Indyk [email protected]
Dmitry Krachun [email protected]
Michael Kapralov [email protected] Boris Prokhorov [email protected]
Abstract Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require Θ(d2 ) time. The randomized Hadamard transform HD reduces this cost to O(d log d), but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies HD to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular,√we prove that a dithered version of TurboQuant achieves mean squared error π 3/2 + o(1) · 4−b at b bits per coordinate, where the o(1) term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.
1
Introduction
Vector quantization is a fundamental technique for compressing real-valued vectors in Rd into compact binary representations. Given a vector x ∈ Rd , a quantizer V ECTOR Q UANT maps x to a sequence of b · d bits V ECTOR Q UANT(x). The bits can then be input to another procedure V ECTOR D EQUANT, obtaining the decoded vector x e = V ECTOR D EQUANT(V ECTOR Q UANT(x)). The size b · d of the compressed representation controls the distortion ∥x − x e∥2 , or the expected distortion E[∥x − x e∥2 ] if the procedures are randomized. Alternatively, instead of decoding x e, some function of it (e.g., the distance to another vector y) is estimated. This primitive plays an important role in many areas of machine learning, including similarity search [Cha02, JDS10, DIIM04, GL24, GGX+ 25], federated learning [VBP+ 22, VBBP+ 21, BBPE+ 24], efficient transformers [ZDHM25], and model compression [GKD+ 22, AMC+ 24, TCS+ 24]. A popular and well-studied approach to vector quantization is random projection followed by scalar quantization [Cha02, DIIM04, DCL08, AIL+ 15, VBP+ 22, VBBP+ 21, GL24, AMC+ 24, TCS+ 24, GGX+ 25, ZDHM25]. Here, one computes V ECTOR Q UANT(x) = quant(Rx), where R is a random rotation matrix and quant is a scalar quantizer (e.g., the sign function) applied coordinate-wise to the vector Rx. A key advantage of this approach is that it is data-oblivious: it requires no complex preprocessing tailored to the input distribution. Moreover, this method is amenable to theoretical analysis, since each coordinate of Rx is approximately normally distributed when R is a uniformly random rotation. Preprint.
However, applying a dense random rotation matrix R requires Θ(d2 ) time, which can be prohibitively expensive for high-dimensional vectors. To overcome this bottleneck, [AC09, Sar06, WLRT08, KW11, HMT11] and others proposed to replace random projections with randomized Hadamard transforms. Specifically, one replaces R with the structured matrix HD, where H ∈ Rd×d is the normalized Hadamard matrix and D is a diagonal matrix with independent Rademacher (±1) entries on the diagonal. The resulting transform can be applied in O(d log d) time using the fast Walsh-Hadamard algorithm, yielding a substantial speedup over dense rotations. Thanks to its low complexity and efficient parallel implementation, randomized Hadamard transform is often the method of choice in industrial deployments, see, e.g., [Chr25, AAH+ 24]. Unfortunately, HD is no longer a uniformly random rotation; in fact, it is not even a continuous random variable. As a consequence, the coordinates of HDx have a more complex distribution than in the dense case, and theoretical guarantees for quantization become harder to establish. Existing results are typically either empirical [AIL+ 15, SFKM17, OP25] or provable but with higher dimension or number of bits compared to those achievable with truly random rotations [AL13, KW11, Tro11, LSS14, CN22, BBPE+ 24]. A natural remedy is to use more general structured matrices obtained by composing multiple randomized Hadamard transforms, possibly interleaved with other (e.g., sparse diagonal) matrices [DKS11, LSS14, ZS21, KW16, ZM26]. In particular, the last paper independently showed that the composition of just two randomized Hadamard transforms suffices to approximate1 uniform random rotation in high dimensions. However, those matrices are still more complex than a single randomized transform. Furthermore, the approximation error translates into an increased bound for the expected distortion after quantization. In this paper, we study a simple alternative to composing multiple randomized Hadamard transforms, namely dithering. Specifically, we consider quantizers where each coordinate of HDx is shifted by a random amount (controlled by a parameter U ) before applying the scalar quantizer quant. Such quantizers are quite simple, as they require only one application of the randomized Hadamard transform, followed by a subtraction of a random vector. At the same time, the random offset injects additional randomness into the quantization process, which facilitates the analysis. 1.1
Our results
We consider the following data-oblivious vector quantization problem. For an input vector x ∈ Rd , a quantizer V ECTOR Q UANT : Rd → {0, 1}b·d outputs a binary string of bd bits, where b is the bit-width per coordinate. The dequantizer V ECTOR D EQUANT : {0, 1}b·d → Rd maps this string back to a vector x e ∈ Rd . We aim to design a pair of quantizer and dequantizer such that for any desired bit-width b minimize the following expected distortion measure for any (worst-case) vectors: sup E∥x − x e∥22 ,
x∈S d−1
where the expectation is over the internal randomness of the quantizer. The restriction to unit vectors is only for normalization: for nonzero inputs one can store the norm separately, quantize x/∥x∥2 , and rescale the decoded vector. In the following, we assume that d is padded to a power of 2, thus there exists a d × d Hadamard matrix. Our main result shows that randomized Hadamard mappings HD, after dithering, provides compression guarantees that asymptotically match those achievable with truly random rotation matrices R. Moreover, our quantizer is unbiased, which is a desirable property for numerous applications. In particular we show that our proposed algorithm has the following guarantees: Theorem 1.1. For every dimension d and every unit vector x ∈ S d−1 , Algorithm 5 satisfies ED,U [e x] = x and π ED,U ∥x − x e∥22 ≤
√
3/2 + o(1) , b → ∞, 4b where the o(1) term vanishes as b → ∞, uniformly over d and x.
(1)
1 They show that, for each vector x and coordinate i, (HD HD x) approximates (Rx) in Kolmogorov distance up to 1 2 i i an error of O(d−1/5 ). See Related Work for further discussion.
2
The scaling constant in this theorem matches the bound obtained for TurboQuant in [ZDHM25] that assumed fully random rotation matrices, up to the o(1) term. Furthermore, as noted in [BBBIM+ 26], this also provides guarantees for a special case of the EDEN quantization method [VBP+ 22], also using fully random rotation matrices. Thus, Theorem 1.1 can be viewed as justifying the use a single randomized Hadamard matrix in those methods. We also provide a quantizer for inner products. Similarly to TurboQuant, we achieve this result by additionally quantizing the residual and showing that the quantization error is uncorrelated with the direction of the vector we dot product x with. Somewhat surprisingly, a classical mixed moment property of Rademacher random variables suffices to establish this fact with random rotations replaced by only a single HD matrix: Theorem 1.2. Let x ∈ S d−1 be a unit vector and let y ∈ Rd . Let x b be the reconstructed vector produced by Algorithm 4 with a base bit-width b. Then ! √ 2 π 3 ∥y∥ 2 , E| ⟨y, x b − x⟩ | ≤ 13 + 1 + o(1) 2 d · 4b where the o(1) term vanishes as b → ∞, uniformly over d and x. 1 Moreover, the output of Q UANTIZE(x) from Algorithm 4 can be stored using db + (3 + 2 ln 2 )d + O(log(b + log d)) total bits.
1.2
Related work
In addition to the discussion in the introduction, in this section we elaborate on connections with some prior/concurrent works in more detail. Dithering, i.e., the use of a random offset in quantization, has a long history in quantization theory [Sch64, ZF92]. In the context of random projections combined with quantization, dithering has been employed in [DIIM04, DCL08] and more recently in [GL24]. However, their analysis assumed a truly random matrix R. Another approach to analyzing quantization after a single randomized Hadamard transform appears in [BBPE+ 24], where the authors use the Bentkus–Dzindzalieta tail bound to compare the tails of normalized Hadamard coordinates with Gaussian tails. They then partition the range of coordinates into intervals and bound the quantization error on each interval separately, leveraging the tail bound to control contributions from the outer intervals. However, as the authors themselves note, this approach yields only a loose bound on the expected distortion. An alternative approach to bridging the gap between a single randomized Hadamard transform and a fully random rotation is taken by a very recent independent work [ZM26], which shows that composing two randomized Hadamard transforms HD1 HD2 suffices to approximate a uniform random rotation in Kolmogorov distance, with an error of O(d−1/5 ) per coordinate. While this result provides a general-purpose surrogate for random rotations, the procedure is more complex, and applying it to quantization incurs an additive distortion overhead that does not vanish for fixed d.
2
Construction of the quantizer
For the ease of exposition, we separate the main mean squared error argument from the unbiasedness property. We first present a simpler baseline algorithm, Algorithm 1, which achieves the claimed mean-squared error bound (Eq. (1)) but is slightly biased. In the later Section A.3, we present Algorithm 5, which is an unbiased variant of Algorithm 1. Our quantizer independently and randomly flips the signs of the input vector coordinates, mixes the coordinates using a normalized Hadamard transform, and then applies the same scalar quantizer to every transformed coordinate. The scalar quantizer is a dithered version of Lloyd quantization, which was also used in Turboquant [ZDHM25] and EDEN [VBP+ 22]. We define the scalar quantizer now, start by introducing some basic notations. Let 2
φ(t) = (2π)−1/2 e−t /2 3
be the standard Gaussian density, and define Z 1 t φ(s)1/3 ds, F (t) := A −∞
Z where A :=
φ(t)1/3 dt.
R
Such F is the CDF of a Gaussian random variable with mean 0 and variance 3 (see Claim A.4 for the proof). In Algorithm 1, the scalar quantizer applies F to each coordinate, imposes a shifted uniform grid on the resulting quantile levels, and reconstructs each grid bucket at the inverse image of its midpoint, i.e. reconstructs each bucket at the corresponding middle quantile. Specifically, we choose a uniformly random shift parameter U ∈ [0, 1] and denote the parameter B = 2b (the target codebook size, i.e. number of possible quantized scalar values). Throughout this paper, we use [B] to denote {0, 1, ...B − 1}. For j ∈ [B], we define grid points hj := (j + U )/B. Define h0 := 0 and hB := 1. Now for j ∈ [B] define buckets Bj ← {t ∈ R : hj ≤ F (t) < hj+1 }. Finally, for j ∈ [B] define reconstruction values qj ← F −1 (hj + hj+1 )/2 .
(2)
See Fig. 1 below for an illustration. F (t) (Quantile Space) F (t)
hB 1−U B
m3
h3 1 B
m2
h2 1 B
m1
h1 1+U B
f (t) ∝ F ′ (t) m0
h0
q0 B0
q1 0
q2
B1
B2
q3
t (Input Coordinate) B3
Figure 1: Illustration of the scalar quantizer mapping with B = 4. The function F (t) (blue) and its scaled underlying density f (t) (green) are shown. A uniform grid shifted by U defines boundaries hj on the y-axis, which project back to the boundaries of the quantization buckets Bj . The reconstruction values qj are defined as the inverse image of the bucket midpoints mj = (hj + hj+1 )/2. Our vector quantization algorithm V ECTOR Q UANT, presented in Algorithm 1, applies the scalar dithered quantization scheme described above to every coordinate of the input vector x ∈ S d−1 after applying the HD matrix. For the purposes of the analysis it is convenient to think of the quantizer as returning the corresponding middle quantile as opposed to its index. To this effect, it is convenient to introduce 4
Definition 2.1 (quant function). For z ∈ R define quant(z) to return the middle quantile qj of the bucket Bj that contains z, i.e. quant(z) := qj for z ∈ Bj . With Definition 2.1 in place the task of bounding quantization error in all coordinates becomes, letting z = HDx, the task of bounding Eε,U
X
(zi − quant(zi ))2 = d · Eε,U (z1 − quant(z1 ))2 ,
i∈[d]
where the last equality uses the fact that the marginal P distributions of coordinates of z are the same, i.e. they are all distributed as the Rademacher sum j∈[d] εj xj . The details of the algorithms are depicted in Algorithm 1. Recall [B] always denotes {0, 1, . . . , B−1}. Algorithm 1 Dithered scalar Gaussian quantization 1: input: dimension d and bit-width b 2: Let H ∈ Rd×d be a normalized Hadamard matrix and let B ← 2b . 3: Sample independent Rademacher random variables ε1 , . . . , εd and set D ← diag(ε1 , . . . , εd ). 4: Sample an offset U ∼ Unif[0, 1). 5: procedure C ONSTRUCT S CALAR C ODEBOOK(B, U ) 6: Define grid points hj ← (j + U )/B for j ∈ [B]. 7: 8:
▷ Uniformly shifted grid in [0, 1]
Define h0 ← 0 and hB ← 1. Define buckets Bj ← {t ∈ R : hj ≤ F (t) < hj+1 } for j ∈ [B]. Define reconstruction values qj ← F −1 (hj + hj+1 )/2 for j ∈ [B].
9: procedure V ECTOR Q UANT(x ∈ S d−1 ) 10: y ← HDx 11: for i ∈ [d]√do 12: zi ← d yi 13: idxi ← index j ∈ [B] such that zi ∈ Bj (i.e., the index of zi ’s bucket) 14:
return idx = (idx1 , . . . , idxd ) ∈ [B]d
15: procedure V ECTOR D E Q UANT(idx) 16: for i ∈ [d] do√ 17: yei ← (1/ d) · qidxi 18: 19:
▷ qidxi is the middle quantile of bucket Bidxi , see Eq. (2)
x e ← DH ⊤ ye return x e
The main guarantee of the Algorithm 1 is the following Theorem 2.2. Theorem 2.2. For every dimension d and every unit vector x ∈ S d−1 , Algorithm 1 satisfies π ED,U ∥x − x e∥22 ≤
√
3/2 + o(1) , 4b
b → ∞,
where the o(1) term vanishes as b → ∞, uniformly over d and x. To achieve the additional unbiasedness property, Algorithm 5 makes two changes to the scalar quantizer. First, instead of pinning the grid endpoints h0 , hB at 0 and 1, it uses a shifted grid directly on the quantile levels F (t), so that every input t has a uniformly random position within a bucket. Second, instead of reconstructing each bucket at the corresponding middle quantile by applying F −1 to the midpoint, it uses a modified reconstruction map G, carefully chosen so that averaging G over one bucket recovers the middle quantile value. This makes the scalar reconstruction unbiased, and hence the vector estimator unbiased, while G remains close enough to F −1 on the central region to preserve the same MSE bound. For details, see Algorithm 5 in Section A.3. 5
3
Proof sketch of Theorem 2.2
In this section, we outline our proof ideas for Theorem 2.2. We can use orthogonality of HD to decompose the error coordinate-wise: ∥x − x e∥22 = ∥x − DH ⊤ ye∥22 = ∥HDx − ye∥22 = d √ 2 2 1 1X yi − √ quant( dyi ) = zi − quant(zi ) . d i=1 d i=1
d X
Therefore, to control the total MSE: ED,U ∥x − x e∥22 , it is enough to bound the variance of the scalar quantizer quant(·) under the specific input distibution of zi . For every coordinate i, this distribution is given by X √ √ X Hij Djj xj = εj xj zi = d(HDx)i = d j
j
where εj are i.i.d. Rademacher random variables taking values ±1 with probability 1/2. In contrast 2 to using a truly random rotation or an i.i.d. P Gaussian matrix, where zi distributed as N (0, ∥x∥2 ), our case is more delicate, as distribution of j εj xj does not depend only on ∥x∥2 , but also on individual coordinates. It means that our oblivious P scalar quantizer quant should provide guarantees for any input distribution of the form zi = j εj xj , where ∥x∥2 = 1. We therefore drop index i in what follows. Recall that B = 2b is the number of buckets. Our main guarantee for quant is the following. d−1 Lemma define P 3.1 (Restated Lemma A.1). For every dimension d, every unit vector x ∈ S z = j εj xj where i.i.d. εj = ±1 with probability 1/2. Then √ π 3/2 + o(1) Eε,U |z − quant(z)|2 ≤ , B → ∞, B2 where the o(1) term is uniform in d and x. As we described above, Theorem 1.1 follows directly from Lemma 3.1. The rest of this section is dedicated to Lemma 3.1. Lemma 3.1 is a bit surprising - the codebook of quant is built from the optimal quantization nodes for N (0, 1), butP we prove that the same error rate is achieved for a different distribution: the Rademacher 2 sums z = j εj xj . This distribution can be quite different from N (0, ∥x∥2 ) for worst-case x. For example if x = (1, 0, . . . 0) then z only takes values ±1. However, it turns out that to prove Lemma 3.1, we only need the fact that z is 1-subgaussian. This is captured by the following claim. P Lemma 3.2. For every dimension d, every unit vector x ∈ S d−1 define z = j εj xj where i.i.d. εj = ±1 with probability 1/2. Then z is a 1-subgaussian random variable, i.e. 2
Eeλz ≤ eλ /2
for all λ ∈ R.
Note that subgaussianity is a powerful property that in some cases allows us to simply substitute the distribution with the standard Gaussian. More formally, we will use the following (see Lemma A.2): 2
2
Claim 3.3. If α > 0, z is 1-subgaussian and ξ ∼ N (0, 1), then Eeαz ≤ Eeαξ . Unfortunately, there is no straightforward way to apply this property to bound the expectation of the quantization error because the error function minqj |t − qj |2 is highly non-monotone – it could be that subgaussian distribution tends to concentrate around highs of the error function. We now move on to outline our proof for Lemma 3.1. In fact, we will prove a bit more general version of Lemma 3.1 with any 1-subgaussian input.2 From now on, we will write Ez instead of Eε . We separate the analysis of Ez,U |z − quant(z)|2 according to whether z lies in a “central interval” [−M, M ], i.e. we separately consider √ a tail event |z| > M and a central event |z| ≤ M , for some carefully chosen threshold M = C log B, C ∈ (4, 6). Such a narrow choice of values of C is due to the following tension: we need to guarantee that a O( B1 ) shift in quantiles of F (see Algorithm 1) results in a o(1) shift in centroids in the central interval; this forces M not to be too large. But with the same choice of M we need the tail event to be unlikely enough that we can ignore the centroids construction outside of the central interval completely; this forces M to be not too small. 2 Note that N (0, 1) appearing from a truly random rotation is also 1-subgaussian.
6
3.1
Central event
In the central event, we argue that buckets are narrow enough to treat standard Gaussian density on them as uniform. Then, to recover optimal error rate for our arbitrary 1-subgaussian distribution, we induce uniformity by dithering, i.e. applying random shift on the quantization grid. More specifically, U ∼ Unif[0; 1/B) as we show in Lemma A.3, for our choice of M , any |t| < M and quantile shift B we have the following h i 1 1 • T := F (t) − F (quant(t)) is uniform on [− 2B ; 2B ]. ′
• FF ′(s) (t) = 1 + oB (1) for all s ∈ [t; quant(t)] where oB (1) term is uniform in s and U . Then we can use first-order approximation and write T T /B quant(t) − t = F −1 F (t) + − t = (1 + oB (1)) ′ . B F (t) And, integrating over T , we bound EU |t − quant(t)|2 ≤ (1 + oB (1))
1 1 . 12B 2 F ′ (t)2
1 1 1 Note that the error FT ′/B (t) , T ∼ Unif[− 2 , 2 ] matches the typical error in a bucket of width BF ′ (t) with a centroid placed in the middle. Since F ′ (s) is almost constant over the bucket, this calculation differs from an actual error only by lower order terms.
To get the total error bound we first take expectation over U Ez,U |z − quant(z)|2 ≤ (1 + oB (1))
1 1 Ez ′ 2 2 12B F (z)
and then, by Claim 3.3, since F ′ (x) is a Gaussian density and z is 1-subgaussian, 1 Ez
F ′ (z)2
≤ Eξ
1 F ′ (ξ)2
,
Finally, Ez,U |z − quant(z)|2 ≤ (1 + oB (1)) 3.2
where ξ ∼ N (0, 1). √ 1 1 π 3/2 + o(1) E = ξ 12B 2 F ′ (ξ)2 B2
Tail event
In the tail event, we give a simple bound |z − quant(z)|2 ≤ 2|z|2 + 2|quant(z)|2 2
and argue that both terms on the RHS are bounded in expectation by O(poly log B ·e−M /2 ) = o( B12 ) using subgaussianity of z and our choice of M . A little more work is required to carefully bound |quant(z)| since the centroid construction is randomized. For more details, see Lemma A.6.
4
Inner product quantizer
In this section we present our inner product quantizer and prove Theorem 1.2. For a vector y ∈ Rd , 2 in order to achieve approximation error for (⟨y, x⟩ − ⟨y, x e⟩)2 that scales as O(1) dB 2 ∥y∥2 , we augment our quantizer for x with another basic quantizer that decorrelates the residual r = x − x e with y. This is achieved by a single application of a fresh HD matrix to the residual followed by a simple quantization procedure that uses a constant number of bits per coordinate in expectation. To obtain an explicit bound on the norm of the residual ∥r∥2 , x e is projected onto the unit ball; such a projection Π : Rd → Rd can be implemented simply as Π(v) = v if ∥v∥2 ≤ 1 and Π(v) = v/∥v∥2 otherwise. Concretely, let r = x − x e be the residual vector, where x e is the result of quantization using our main V ECTOR Q UANT procedure followed by projecting onto the unit ball. Define the residual scale by 7
√ ∈ [0, √2 ]. We first quantize the scale using a basic scalar quantizer S CALAR Q UANT (s) s = ∥r∥ d d (Algorithm 2 below) and then quantize the residual’s coordinates based on the quantized scale (Algorithm 3 below).
Algorithm 2 Scalar quantization 1: input: scalar s ∈ [0, √2 ], dimension d, scale parameter B ≥ 2 d
2: public parameter: minimum encoded scale τB ← 1/(dB). 3: procedure S CALAR Q UANT(s) 4: if s < τB then 5: return idxσ ← 0 6: k ← ⌈log2 (s/τB )⌉ 7: idxσ ← k + 1 8: return idxσ 9: procedure S CALAR D E Q UANT(idxσ ) 10: if idxσ = 0 then 11: return σ ← 0 12: return σ ← τB 2idxσ −1
The intuition behind Algorithm 2 is that if the residual scale exceeds a minimum cutoff, i.e., s ≥ τB , then the quantized scale is σ = τB 2idxσ −1 satisfying s ≤ σ < 2s. On the other hand if s < τB , then the quantized scale is set to σ = 0 indicating that the residual is negligibly small (thus the residual quantization stage can be skipped). The quantized scales are indexed by idxσ , which can be encoded using ⌈log2 (⌈log2 ( √2d /τB )⌉ + 2)⌉ = O(log log(dB)) bits when s ∈ [0, √2d ]. We next describe the residual quantizer in Algorithm 3, which uses Algorithm 2 as a subroutine. Algorithm 3 Residual Quantization 1: input: dimension d, scale parameter B ≥ 2 2: Let H ∈ Rd×d be a normalized Hadamard matrix and D be a diagonal matrix whose entries are i.i.d.
Rademacher random variables. 3: procedure R ESIDUAL Q UANT(r ∈ √ Rd ) 4: idxσ ← S CALAR Q UANT(∥r∥ / d) 5: if idxσ = 0 then 6: return idxσ , ℓ = (0, . . . , 0), and λ = (0, . . . , 0) 7: 8: 9: 10: 11: 12: 13:
σ ← S CALAR D E Q UANT(idxσ ) v ← HDr for i ∈ [d] do ℓi ← min{ℓ ∈ {0, 1, 2, . . .} : |vi | ≤ σ · 2ℓ } ▷ ℓi can be stored, e.g., as unary word 1ℓi 0 ℓi Ri ← σ · 2 Sample a sign bit λi ∈ {−1, 1} such that P(λi = 1 | D, r) = 1+(v2i /Ri ) return idxσ , ℓ = (ℓ1 , . . . , ℓd ), and λ = (λ1 , . . . , λd )
14: procedure R ESIDUAL D E Q UANT(idxσ , ℓ, λ) 15: σ ← S CALAR D E Q UANT(idxσ ) 16: for i ∈ [d] do 17: Ri ← σ · 2ℓi 18: qi ← Ri λi 19: rb ← DH ⊤ q 20: return rb
In English, for each coordinate i ∈ [d], Algorithm 3 records the level ℓi , for instance using the unary word 1ℓi 0, and sample one randomized sign bit λi ∈ {−1, 1} with P(λi = 1 | D, r) = 1+(v2i /Ri ) . This probability is valid because |vi | ≤ σ2ℓi = Ri . 8
Finally, our two-stage inner product quantizer is present below as Algorithm 4. Its analysis, namely the proof of Theorem 1.2, is presented in the appendix (Section B). Algorithm 4 Two-Stage Inner Product Quantizer 1: input: dimension d, base bit-width b 2: Let H ∈ Rd×d be a normalized Hadamard matrix, let B ← 2b , and let Π : Rd → Rd be a projection to the
unit ball. 3: Sample independent Rademacher random variables ε1 , . . . , εd and set Dbase ← diag(ε1 , . . . , εd ). 4: Sample independent Rademacher random variables η1 , . . . , ηd and set Dres ← diag(η1 , . . . , ηd ). 5: Sample an offset U ∼ Unif[0, 1). 6: C ONSTRUCT S CALAR C ODEBOOK(B, U ) ▷ Defined in Algorithm 1. This constructs Bj and qj for j ∈ [B] 7: procedure Q UANTIZE(x ∈ S d−1 ) 8: 9: y ← HDbase x 10: for i ∈ [d]√do 11: zi ← d yi 12: idxi ← index √ j ∈ [B] such that zi ∈ Bj 13: yei ← (1/ d) · qidxi 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
idx ← (idx1 , . . . , idxd ) ∈ [B]d x e ← ΠDbase H ⊤ ye
▷ Stage 1: Base Dithered Quantization
▷ Local dequantization for residual ▷ Base reconstructed vector ▷ Stage 2: Residual Quantization, repeated from Algorithm 3 ▷ Compute the residual vector
r ←x−x e √ idxσ ← S CALAR Q UANT(∥r∥ / d) if idxσ = 0 then return idx, idxσ , ℓ = (0, . . . , 0), λ = (0, . . . , 0) σ ← S CALAR D E Q UANT(idxσ ) v ← HDres r for i ∈ [d] do ℓi ← min{ℓ ∈ {0, 1, 2, . . .} : |vi | ≤ σ2ℓ } ▷ ℓi can be stored, e.g., as unary word 1ℓi 0 Ri ← σ · 2ℓi Sample sign bit λi ∈ {−1, 1} such that P(λi = 1 | Dres , r) = 1+v2i /Ri return idx, idxσ , ℓ = (ℓ1 , . . . , ℓd ), and λ = (λ1 , . . . , λd )
28: procedure D E Q UANTIZE(idx, idxσ , ℓ, λ) 29: 30: for i ∈ [d] do√ 31: yei ← (1/ d) · qidxi 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42:
x e ← ΠDbase H ⊤ ye
▷ Stage 1: Base Reconstruction
▷ Stage 2: Residual Reconstruction, repeated from Algorithm 3
σ ← S CALAR D E Q UANT(idxσ ) if σ = 0 then rb ← 0 else for i ∈ [d] do Ri ← σ2ℓi qires ← Ri λi rb ← Dres H ⊤ q res return x b←x e + rb
▷ Final reconstructed vector
Limitations This paper is primarily theoretical and studies a specific class of data-oblivious quantizers based on a single randomized Hadamard transform and randomized dithering. The results characterize worst-case mean-squared error and inner-product error, but do not attempt to optimize all finite-bit constants or evaluate performance empirically across downstream systems. Extending the analysis to broader structured transforms, alternative scalar quantizers, and more implementation-specific bit accounting would be interesting directions for future work.
9
References [AAH+ 24] Krish Agarwal, Rishi Astra, Adnan Hoque, Mudhakar Srivatsa, Raghu Ganti, Less Wright, and Sijia Chen. HadaCore: Tensor core accelerated Hadamard transform kernel. https://pytorch.org/blog/hadacore/, 2024. IBM and Meta. PyTorch Blog, December 2, 2024. [AC09] Nir Ailon and Bernard Chazelle. The fast Johnson–Lindenstrauss transform and approximate nearest neighbors. SIAM Journal on Computing, 39(1):302–322, 2009. [AIL+ 15] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. Advances in Neural Information Processing Systems, 28, 2015. [AL13] Nir Ailon and Edo Liberty. An almost optimal unrestricted fast johnson-lindenstrauss transform. ACM Transactions on Algorithms (TALG), 9(3):1–12, 2013. [AMC+ 24] Saleh Ashkboos, Amirkeivan Mohtashami, Maximilian L Croci, Bo Li, Pashmina Cameron, Martin Jaggi, Dan Alistarh, Torsten Hoefler, and James Hensman. Quarot: Outlier-free 4-bit inference in rotated llms. In Advances in Neural Information Processing Systems, volume 37, 2024. [BBBIM+ 26] Ran Ben-Basat, Yaniv Ben-Itzhak, Gal Mendelson, Michael Mitzenmacher, Amit Portnoy, and Shay Vargaftik. A note on turboquant and the earlier drive/eden line of work. arXiv preprint arXiv:2604.18555, 2026. [BBPE+ 24] Ran Ben-Basat, Amit Portnoy, Gil Einziger, Yaniv Ben-Itzhak, Michael Mitzenmacher, et al. Accelerating federated learning with quick distributed mean estimation. In Forty-First International Conference on Machine Learning, 2024. [Cha02] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 380–388, 2002. [Chr25] Tobias Christiani. 8-bit rotational quantization: How to compress vectors by 4x and improve the speed-quality tradeoff of vector search. https://weaviate.io/blog/ 8-bit-rotational-quantization, 2025. Weaviate Blog, August 26, 2025. [CN22] Yeshwanth Cherapanamjeri and Jelani Nelson. Uniform approximations for randomized hadamard transforms with applications. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 659–671, 2022. [DCL08] Wei Dong, Moses Charikar, and Kai Li. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, pages 123–130, 2008. [DIIM04] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, pages 253–262, 2004. [DKS11] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. Fast locality-sensitive hashing. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1073–1081, 2011. [GGX+ 25] Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. Practical and asymptotically optimal quantization of highdimensional vectors in euclidean space for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 3(3):1–26, 2025. [GKD+ 22] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. A survey of quantization methods for efficient neural network inference. In Low-power computer vision, pages 291–326. Chapman and Hall/CRC, 2022. 10
[GL24] Jianyang Gao and Cheng Long. RaBitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 2(3):1–27, 2024. [HMT11] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288, 2011. [JDS10] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2010. [KW11] Felix Krahmer and Rachel Ward. New and improved Johnson–Lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 43(3):1269–1281, 2011. [KW16] Christopher Kennedy and Rachel Ward. Fast cross-polytope locality-sensitive hashing. arXiv preprint arXiv:1602.06922, 2016. [LSS14] Quoc Viet Le, Tamás Sarlós, and Alexander Johannes Smola. Fastfood: Approximate kernel expansions in loglinear time. arXiv preprint arXiv:1408.3060, 2014. [OP25] Or Ordentlich and Yury Polyanskiy. Optimal quantization for matrix multiplication. IEEE Transactions on Information Theory, 2025. [Sar06] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06), pages 143–152. IEEE, 2006. [Sch64] Leonard Schuchman. Dither signals and their effect on quantization noise. IEEE Transactions on Communication Technology, 12(4):162–165, 1964. [SFKM17] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International Conference on Machine Learning, pages 3329–3337. PMLR, 2017. [TCS+ 24] Albert Tseng, Jerry Chee, Qingyao Sun, Volodymyr Kuleshov, and Christopher De Sa. QuIP$\#$: Even better LLM quantization with hadamard incoherence and lattice codebooks. In Forty-first International Conference on Machine Learning, 2024. [Tro11] Joel A Tropp. Improved analysis of the subsampled randomized Hadamard transform. Advances in Adaptive Data Analysis, 3(01n02):115–126, 2011. [VBBP+ 21] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. DRIVE: One-bit distributed mean estimation. Advances in Neural Information Processing Systems, 34:362–377, 2021. [VBP+ 22] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben Itzhak, and Michael Mitzenmacher. EDEN: Communication-efficient and robust distributed mean estimation for federated learning. In International Conference on Machine Learning, pages 21984–22014. PMLR, 2022. [WLRT08] Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. A fast randomized algorithm for the approximation of matrices. Applied and Computational Harmonic Analysis, 25(3):335–366, 2008. [ZDHM25] Amir Zandieh, Majid Daliri, Majid Hadian, and Vahab Mirrokni. TurboQuant: Online vector quantization with near-optimal distortion rate. arXiv preprint arXiv:2504.19874, 2025. [ZF92] Ram Zamir and Meir Feder. On universal quantization by randomized uniform/lattice quantizers. IEEE Transactions on Information Theory, 38(2):428–436, 1992. 11
[ZM26] Tomer Zilca and Gal Mendelson. Approximating uniform random rotations by two-block structured Hadamard rotations in high dimensions. arXiv preprint arXiv:2604.23418, 2026. [ZS21] Jinjie Zhang and Rayan Saab. Faster binary embeddings for preserving Euclidean distances. In International Conference on Learning Representations, 2021.
12
A
Full proof of Theorem 1.1
A.1
Scalar Estimate
In this section, we prove Lemma A.1, the scalar estimate that controls the coordinate-wise mean squared error. In the next section, we then use it to bound the error of vector quantization. For any unit vector a ∈ Rd , we define a random variable Xa :=
d X
ai εi ,
i=1
where ε1 , . . . , εd are independent Rademacher random variables. We abbreviate ε = (ε1 , . . . , εd ). For the scalar quantizer appearing in Algorithm 1, we write when t ∈ Bj ,
quant(t) := qj
i.e. quant(·) maps any scalar t ∈ R to the corresponding reconstruction value, which is the preimage of the midpoint of the bucket in which F (t) lands. We recall that quant depends on U, B in the following ways: U is a random offset that determines the shift of buckets, and B = 2b is the number of buckets. The rest of this section devotes to proving Lemma A.1, which bounds the mean squared quantization error for quant applied to Xa . P Lemma A.1. Uniformly over all d ≥ 1 and all a ∈ Rd satisfying i a2i = 1, √ 2 π 3/2 + o(1) , B → ∞. Eε,U Xa − quant(Xa ) ≤ B2 As outlined in the proof sketch, the proof proceeds by separating the behavior of the scalar √ quantizer according to whether the input lies in a “central” interval [−MB , MB ], where MB := 5 log B. We first show in Lemma A.2 that every normalized Rademacher sum has Gaussian-type tail and moment bounds. Inside the central interval, Lemma A.3 shows that the random shift U makes the displacement in the F -coordinate uniform at scale 1/B, and that F −1 can be replaced by its first-order approximation on this scale. Outside the central interval, Lemma A.6 gives a rough bound on the squared quantization error; the tail bound from Lemma A.2 then makes this rough estimate negligible. Combining these two regimes gives Lemma A.1. The following lemma is standard (see e.g., [AC09], proof of Lemma 1), but we reprove it here for completeness. Lemma A.2. For every unit vector a ∈ Rd , the random variable Xa satisfies 2
EeλXa ≤ eλ /2
for all λ ∈ R.
Consequently, 2
P(|Xa | > s) ≤ 2e−s /2
for all s > 0.
Moreover, if G ∼ N (0, 1), then 2
2
EeXa /3 ≤ EeG /3 =
√
3.
Proof. By the definition of Xa and the independence between εi ’s, EeλXa = Eeλ
Pd
i=1 ai εi
=
d Y
Eeλai εi .
i=1
For each Rademacher random variable εi , Eeλai εi =
2 1 λai 1 −λai e + e = cosh (λai ) ≤ e(λai ) /2 . 2 2
Thus EeλXa ≤
d Y
2
Pd
e(λai ) /2 = e
i=1
13
2 2 i=1 ai λ /2
2
= eλ /2 .
(3)
The tail bound follows from Markov’s inequality applied to both eλXa and e−λXa and optimize over λ > 0. 2
For the last argument, since EG∼N (0,1) eτ G = eτ /2 for any τ ∈ R, conditioning on Xa and taking p τ = 2/3Xa gives √ 2
2
eXa /3 = EG e 3 GXa . Let G be independent of ε1 , . . . εd , we obtain √2 √ 2 2 EeXa /3 = EG Eε e 3 GXa ≤ EG eG /3 = 3. where the inequality follows from the earlier MGF bound Eq. (3).
We next state our main lemma for the central event. It controls the quantization error for all real t (in particular, our random variable Xa ) that lies in the central interval [−MB , MB ]. √ Lemma A.3. Let MB := 5 log B. For all |t| ≤ MB , EU t − quant(t)
2
≤ (1 + oB (1))
2 A2 (2π)1/3 et /3 . 12B 2
where the oB (1) term is uniform for |t| ≤ MB . Before proving Lemma A.3, we state the following fact about F , which will be helpful for our proof. Let Φ denote the CDF of the standard normal distribution. √ Claim A.4. For any t ∈ R, F (t) = Φ(t/ 3). Proof. Recall that F (t) := where A =
R
1 A
Z t
φ(s)1/3 ds.
−∞
φ(t)1/3 dt is the normalization factor. Since R 2
φ(s)1/3 = (2π)−1/6 e−s /6 is proportional to the density of N (0, 3), F (t) is exactly the CDF of N (0, 3). Thus for G ∼ N (0, 1), √ √ √ F (t) = P[ 3G ≤ t] = P[G ≤ t/ 3] = Φ(t/ 3). √ Corollary A.5. Let MB = 5 log B. We have F (−MB ), 1 − F (MB ), F (MB + 1) − F (MB ), and F (−MB ) − F (−MB − 1) ≫ B −1 . Proof. By Claim A.4 and the symmetry of the Gaussian distribution, √ F (−MB ) = 1 − F (MB ) = Φ(−MB / 3). Since MB2 = 5 log B, the Gaussian tail estimate gives √ Φ(−MB / 3) = B −5/6+o(1) . which is in particular ω(B −1 ). For the two increments, Z MB +1 F (MB + 1) − F (MB ) = F ′ (t) dt MB
Z MB +1 = MB
(2π)−1/6 exp(−t2 /6) dt A
(2π)−1/6 exp(−(MB + 1)2 /6) A where the second equality follows from the definition of F . Since MB2 = 5 log B and A is a constant, this is B −5/6−o(1) = ω(B −1 ) as claimed. By the symmetry, the same bound holds for F (−MB ) − F (−MB − 1). ≥
14
Proof of Lemma A.3. Recall that when defining the grid points in Algorithm 1, we set h1 = (1 + U )/B and hB−1 = (B − 1 + U )/B. As U varies in [0, 1), we always have h1 ≤ 2/B and hB−1 ≥ 1 − (1/B). On the other hand, since F is increasing, for |t| ≤ MB , we have F (−MB ) ≤ F (t) ≤ F (MB ). Applying Corollary A.5, we get ω(B −1 ) ≤ F (t) ≤ 1 − ω(B −1 ). So for all sufficiently large B, h1 < F (t) < hB−1 , i.e. F (t) never falls in one of the two endpoint buckets. Therefore the effect of the random offset U is to uniformly choose the relative position of F (t) inside a bucket. Equivalently, the midpoint of the bucket containing F (t) can be written as a random variable T F (t) + , B where T is uniformly distributed on [−1/2, 1/2]. And its preimage is T quant(t) = F −1 F (t) + . B We next estimate quant(t) − t using the first-order Taylor expansion of F −1 at the point F (t). Formally, we claim that, uniformly over |t| ≤ MB and |T /B| ≤ 1/(2B), T T /B quant(t) − t = F −1 F (t) + − t = (1 + oB (1)) ′ . B F (t) To show this, we observe that for s ∈ [0, T /B], the point F −1 (F (t) + s) lies in the interval [−MB − 1, MB + 1], for all sufficiently large B. Indeed, F (MB + 1) − F (MB ) and F (−MB ) − F (−MB − 1) ≫ B −1 by Corollary A.5. So for |s| ≤ |T /B| ≤ 1/(2B), moving by s in the F -coordinate cannot move the preimage past MB + 1 or −MB − 1. Now let y = F −1 (F (t) + s). The mean value theorem gives s = F ′ (ξ)(y − t) for some ξ between y and t. By the previous argument, both endpoints lie in [−MB − 1, MB + 1], and hence so does ξ. Therefore, 1 (MB + 1)2 −1 |y − t| ≤ |s| sup ≤ Θ B exp = B −1/6+o(1) ′ 6 |ξ|≤MB +1 F (ξ) −1/6
where the second step follows from F ′ (ξ) = (2π)A
2
e−ξ /6 . This implies
p |y 2 − t2 | = |y − t| |y + t| ≤ B −1/6+o(1) · O(MB ) = B −1/6+o(1) · O( log B) = oB (1) thus
2 2 F ′ (t) e−t /6 y − t2 = = exp = 1 + oB (1) F ′ (y) 6 e−y2 /6 uniformly over |t| ≤ MB and |s| ≤ 1/(2B). Equivalently, 1 1 = (1 + oB (1)) ′ . F ′ (F −1 (F (t) + s)) F (t) Finally, integrating from 0 to T /B gives Z T /B 1 T /B T F −1 F (t) + −t= ds = (1 + oB (1)) ′ . ′ −1 B F (F (F (t) + s)) F (t) 0 −1/6
Using ET 2 = 1/12 and F ′ (t) = (2π)A
2
e−t /6 , we obtain
EU (t − quant(t))2 ≤ (1 + oB (1))
2 1 1 A2 = (1 + o (1)) (2π)1/3 et /3 . B 12B 2 F ′ (t)2 12B 2
15
(4)
Next we consider the tail event when |t| = |Xa | > MB . In this event, we use the following crude error bound, which suffices for the entire proof due to the small probability of the tail event. Lemma A.6. There is an absolute constant C such that, for every B ≥ 2 and every t ∈ R, EU (t − quant(t))2 ≤ C(t2 + log B). Proof. Fix the value of U . Since F −1 is increasing, the reconstruction values q0 , . . . , qB−1 are increasing. Hence every reconstruction value lies between the two endpoint reconstruction values, and therefore |quant(t)| ≤ RB (U ), where 1−U 1+U RB (U ) := max F −1 , F −1 1 − . 2B 2B √ By Claim A.4, we have F −1 (p) = 3 Φ−1 (p). Using the standard Gaussian quantile bound |Φ−1 (r)|2 + |Φ−1 (1 − r)|2 ≤ C log(1/r), 0 < r ≤ 1/2, we obtain 2B 2B 2 RB (U ) ≤ C log + C log . 1+U 1−U Taking expectation over U , Z 1 Z 1 2B 2 dU ≤ C log B. EU RB (U ) ≤ C log(2B) dU + C log 1−U 0 0 Thus EU (t − quant(t))2 ≤ 2t2 + 2EU q(t)2 ≤ 2t2 + 2EU RB (U )2 ≤ C(t2 + log B).
With Lemma A.2, Lemma A.3, and Lemma A.6, we can now prove the scalar guarantee. P Proof of Lemma A.1. Fix a ∈ Rd with i a2i = 1, and write X = Xa . We split the expectation according to the central event |X| ≤ MB . We first consider the central contribution, i.e. when |X| ≤ MB . By Lemma A.3, and using the uniformity of the oB (1) term, there exists a deterministic sequence αB → 0 such that 2 A2 B 2 Eε,U (X − quant(X))2 1{|X|≤MB } ≤ (1 + αB ) (2π)1/3 Eε eX /3 12 √ A2 ≤ (1 + αB ) (2π)1/3 3 12 A3 = (1 + αB ) 12 √ X 2 /3 where the second inequality follows from E e ≤ 3 as shown in Lemma A.2. Since A = ε √ √ π 3 1/3 (2π) 3, this is (1 + αB ) 2 . It remains to show that the complement of the central event contributes o(B −2 ). We use Lemma A.6: B 2 Eε,U (X − quant(X))2 1{|X|>MB } ≤ CB 2 Eε (X 2 + log B)1{|X|>MB } . Then using the tail bound from Lemma A.2, Z ∞ 2 2 2 Eε X 1{|X|>MB } = MB Pr[|X| > MB ] + Pr[X 2 > v] dv ≤ C(MB2 + 1)e−MB /2 . 2 MB
Also, 2
(log B) Pr[|X| > MB ] ≤ C(log B)e−MB /2 . Since MB2 = 5 log B, this gives B 2 Eε,U (X − quant(X))2 1{|X|>MB } ≤ CB 2 (log B)e−5 log B/2 = C(log B)B −1/2 = o(1). Combining the central and tail contributions, √ π 3 2 2 B Eε,U (Xa − quant(Xa )) ≤ + o(1), 2 where the o(1) term is uniform over d and a. 16
A.2
Proof of Theorem 2.2
We now return to the vector quantizer in Algorithm 1 and prove Theorem 2.2. The following lemma is the only property of the randomized Hadamard transform that we need: after the normalization, each coordinate is exactly a Rademacher sum with a unit coefficient vector. √ Lemma A.7. Fix x ∈ S d−1 , and let y = HDx and zi = dyi for i ∈ [d] as in Algorithm 1. For every i ∈ [d], there exists a unit vector a(i) ∈ Rd such that zi = Xa(i) . Proof. By the definition of D, we have D = diag(ε1 , . . . , εd ). Thus √ zi =
d (HDx)i =
d √ X
d Hi,j xj εj .
j=1
Define
√
(i)
aj :=
d Hi,j xj .
2 = 1/d for every i, j. Hence Since H is a normalized Hadamard matrix, Hi,j d X j=1
Therefore zi =
(i)
(aj )2 =
d X
2 2 dHi,j xj =
d X
x2j = 1.
j=1
j=1
(i) j aj εj = Xa(i) , as claimed.
P
With this, we can directly apply our scalar estimate for each coordinate and obtain the mean squared error bound for the vector quantizer. √ Proof of Theorem 1.1. Fix x ∈ S d−1 . Let y = HDx, and let zi = d yi be the scalar input quantized in coordinate i. If ye denotes the vector reconstructed in the Hadamard domain, then, by the scaling in Algorithm 1, 1 yei = √ quant(zi ). d Since H and D are orthogonal, d
∥x − x e∥22 = ∥HDx − ye∥22 =
1X (zi − quant(zi ))2 . d i=1
Taking expectation over D and U , and using linearity of expectation, d
ED,U ∥x − x e∥22 =
1X ED,U (zi − quant(zi ))2 . d i=1
By the Lemma A.7, each zi is equal to Xa(i) for a unit vector a(i) . Applying Lemma A.1 to each coordinate gives √ π 3/2 + o(1) 2 ED,U (zi − quant(zi )) ≤ . B2 Then averaging over i, we obtain π ED,U ∥x − x e∥22 ≤
17
√
3/2 + o(1) . B2
A.3
An unbiased variant of Algorithm 1
In this section we modify the scalar quantizer, in particular the scalar reconstruction rule, so that the resulting vector estimator is unbiased, while preserving the same asymptotic distortion bound. Recall that Z Z 1 t 1/3 F (t) = ϕ(s) ds, A= ϕ(s)1/3 ds. A −∞ R Previously in Algorithm 1, we define buckets with 1/B spacing in the F -coordinates, and reconstruct each bucket at the inverse image (F −1 ) of its midpoint. In this section, we will use buckets with 1 ,1 + spacing 1/(B − 1), and we will replace F −1 with a reconstruction function G : [− 2(B−1) 1 ] → R satisfying 2(B−1) 1 Z r+ 2(B−1)
(B − 1)
G(s) ds = F −1 (r)
for every r ∈ (0, 1).
(5)
1 r− 2(B−1)
√ √ Moreover, we will choose G such that in the central region [− 5 log B, 5 log B], G is close to F −1 . Formally: 1 1 Lemma A.8. There exists an explicitly defined function G : [− 2(B−1) , 1 + 2(B−1) ] → R that √ satisfies Eq. (5). Moreover, it can be chosen so that for all |t| ≤ 5 log B and all |v| ≤ 1/2, v v 1 G F (t) + =t+ + o(1) . (6) ′ B−1 (B − 1)F (t) (B − 1)F ′ (t) 1 Proof. We denote the spacing of the grid buckets δ := B−1 . We start by defining G on the open δ δ 1−δ 1+δ interval I := (− 2 , 1 + 2 ) as follows: for u ∈ ( 2 , 2 ] and k ∈ Z, whenever u + kδ ∈ I, we define G as
P k−1 −1 ′ δ j=0 (F ) u + (j + 1/2) · δ G(u + k · δ) := F −1 (u) + 0 −δ P−1 (F −1 )′ u + (j + 1/2) · δ j=k
if k > 0 if k = 0 . if k < 0
The key idea behind this definition is to enforce the recurrence G(u + (k + 1)δ) − G(u + kδ) = δ(F −1 )′ u + (k + 1/2)δ . We first argue that G satisfies Eq. (5). For every r ∈ (0, 1), there is a unique pair of u and k such that we can write r − δ/2 = u + k · δ, it follows that G(r + δ/2) − G(r − δ/2) = δ(F −1 )′ (r). Therefore, ! Z d 1 r+δ/2 1 G(s) ds = (G(r + δ/2) − G(r − δ/2)) = (F −1 )′ (r), dr δ r−δ/2 δ i.e. 1 C := δ
Z r+δ/2
G(s) ds − F −1 (r)
r−δ/2
1+δ −1 is constant in r. Evaluating this at r = 1/2 shows that C = 0. Indeed, on ( 1−δ , and 2 , 2 ], G = F √ −1 −1 −1 F (t) = Φ(t/ 3) (Claim A.4) implies that F (1/2) = 0 and F (1 − r) = −F (r) for every r.
This shows that G satisfies Eq. (5) on the open interval I. We extend it arbitrarily to the endpoints for notational convenience in the codebook. These endpoint values are irrelevant for Eq. (5) since they are measure-zero for the integral. It remains to show Eq. (6). We first compare G with F −1 . Fix r ∈ I, and write r = u + kδ again 1+δ with the unique pair of u ∈ ( 1−δ 2 , 2 ] and k ∈ Z. In the following, we focus on k ≥ 0, with the P−1 convention that j=0 (·) = 0. The case k < 0 holds symmetrically. By the definition of G, " # Z u+(j+1)δ k−1 X −1 −1 ′ −1 ′ G(r) − F (r) = δ(F ) u + (j + 1/2)δ − (F ) (s) ds . u+jδ
j=0
18
Hence, by the midpoint rule error bound, |G(r) − F −1 (r)| ≤ O δ 3
k−1 X
(F −1 )′′′ (s) .
sup
j=0 s∈[u+jδ,u+(j+1)δ]
Equivalently, for J denoting the interval between u and r, Z |G(r) − F −1 (r)| ≤ O δ 2 (F −1 )′′′ (s) ds + O δ 3 sup (F −1 )′′′ (s) . s∈J
J
It remains to bound this RHS plus F −1 (r) − t, using our parameters from Eq. (6): |t| ≤ MB ,
r = F (t) + vδ,
|v| ≤ 1/2.
In Lemma A.3 (Eq. (4)), we have shown that F −1 (r) − t = (1 + o(1)) Fvδ ′ (t) . Also, we have shown that F −1 (r) ∈ [−MB − 1, MB + 1] for all sufficiently large B. Combining this with the fact that 1+δ −1 F −1 (u) = O(δ) for u ∈ ( 1−δ (s)| ≤ MB + 1. And by 2 , 2 ], we have that for every s ∈ J, |F the definition of F , one can observe that (F −1 )′ (s) =
1 F ′ (F −1 (s))
and (F
−1 ′′′
) (s) =
,
(F −1 )′′ (s) =
1 2(F −1 (s))2 + 3 9
Combining all these, we get Z MB −1 ′′′ (F ) (s) ds ≤ O , F ′ (t)2 J
F −1 (s) 3F ′ (F −1 (s))2
1 F ′ (F −1 (s))3
sup (F
−1 ′′′
.
) (s) ≤ O
s∈J
,
MB2 F ′ (t)3
.
Returning to Eq. (6), we get that 3 −1 ′′′ G(r) − t ≤ F (r) − t + O δ (F ) (s) ds + O δ sup (F ) (s) s∈J J 2 vδ M M B B ≤ (1 + o(1)) ′ + δ2 O + δ3 O F (t) F ′ (t)2 F ′ (t)3 vδ δ = (1 + o(1)) ′ + poly log B · (B −1/6+o(1) + B −1/3+o(1) ) · ′ F (t) F (t) vδ δ = ′ + o(1) ′ F (t) F (t) √ where in the third step we used MB = 5 log B and F ′δ(t) ≤ Θ(δ exp(MB2 /6)) = B −1/6+o(1) . −1
2
Z
−1 ′′′
We now describe the unbiased variant of Algorithm 1 in Algorithm 5. The only change is the procedure of C ONSTRUCT S CALAR C ODEBOOK, so we omit repeating the procedures V ECTOR Q UANT and V ECTOR D EQUANT. Algorithm 5 Unbiased dithered scalar Gaussian quantization 1: input: dimension d and bit-width b 2: Let H ∈ Rd×d be a normalized Hadamard matrix and let B ← 2b . 3: Sample independent Rademacher random variables ε1 , . . . , εd and set D ← diag(ε1 , . . . , εd ). 4: Sample an offset U ∼ Unif[0, 1). 5: procedure C ONSTRUCT S CALAR C ODEBOOK(B, U ) 6: Define buckets Bj ← {t ∈ R : ⌊(B − 1)F (t) − U ⌋ + 1 = j} for j = 0, . . . , B − 1. 7:
−1/2 Define reconstruction values qj ← G( j+U ) for j = 0, . . . , B − 1. B−1
19
In English, we use a shifted grid in the F -coordinate with spacing 1/(B − 1). For r ∈ (0, 1), define grid points h(r) = ⌊(B − 1)r − U ⌋ , where U ∼ Unif[0, 1). We only need to focus on r ∈ (0, 1) since later we will take r = F (t), which is in (0, 1) for any real t. Since 0 < r < 1, the index satisfies h(r) ∈ {−1, 0, 1, . . . , B − 2}. Thus h(r) + 1 ∈ {0, 1, . . . , B − 1}, so the index is still encodable using log2 B = b bits. We denote the midpoint of the shifted cell containing r m(r) =
h(r) + U + 1/2 . B−1
Then for every fixed r ∈ (0, 1), m(r) = r +
V , B−1
where V is a random variable V ∼ Unif − 21 , 12 . In the following, we again denote the scalar quantizer: quant(t) := qj when t ∈ Bj . Then by definition,
⌊(B − 1)F (t) − U ⌋ + U + 1/2 B−1 V 1 1 = G F (t) + , V ∼ Unif − , B−1 2 2
quant(t) = G
(7)
Combining this with the requirements on G (Lemma A.8) gives both the unbiasedness and the scalar estimate bound. Pd Lemma A.9. For every t ∈ R, EU [quant(t)] = t. Moreover, let Xa = i=1 ai εi where ε1 , . . . , εd are independent Rademacher random variables and a ∈ Rd be a unit vector. Then, uniformly over d ≥ 1 and a, ! √ 2 π 3 Eε,U Xa − quant(Xa ) ≤ + o(1) B −2 . 2 1 Proof. We denote the spacing of grid buckets δ := B−1 . Fix t ∈ R. By Eq. (5) and Eq. (7),
1 EU [quant(t)] = δ
Z F (t)+δ/2
G(s) ds = F −1 (F (t)) = t.
F (t)−δ/2
This proves the unbiasedness. It remains √ to prove the mean squared error bound, which parallels the proof to Lemma A.1. Let MB := 5 log B. We first consider the contribution from |X| ≤ MB . By Lemma A.8,(Eq. (6)), uniformly over |t| ≤ MB and |v| ≤ 1/2, G(F (t) + vδ) = t +
vδ δ + o(1) ′ . F ′ (t) F (t)
1 In our case, v = V is uniform on [− 21 , 12 ], therefore, EV 2 = 12 and thus
EU (t − quant(t))2 = EU (t − G(F (t) + V δ))2 =
δ2 F ′ (t)2
E(V + o(1))2
≤ (1 + o(1))
20
δ2 , 12F ′ (t)2
2
uniformly for |t| ≤ MB . Now we take the expectation over Xa . Using F ′ (t) = A−1 (2π)−1/6 e−t /6 , √ 2 1 δ = B−1 , and Eε eXa /3 ≤ 3, this becomes 2 δ 2 A2 Eε,U (Xa − quant(Xa ))2 1{|Xa |≤MB } ≤ (1 + o(1)) (2π)1/3 Eε eXa /3 12! √ π 3 + o(1) B −2 = 2 which concludes the central contribution. We now bound the tail contribution. Similar to Lemma A.6, we use a crude bound following from the construction of G. For every t ∈ R and every |v| ≤ 1/2, δ |G(F (t) + vδ)| ≤ C 1 + |t| + ′ . F (t) where C is a constant. Indeed, suppose first that t ≥ 0. In the definition of G in Lemma A.8, the values are obtained from the interval around 1/2 by summing midpoint values of (F −1 )′ . Since (F −1 )′ is increasing on [1/2, 1), the sum up to F (t) + vδ is bounded by the corresponding integral up to F (t), plus one endpoint term. This gives C(1 + t + δ/F ′ (t)). The case t < 0 is symmetric, using that F −1 (1 − s) = −F −1 (s) and that (F −1 )′ is symmetric around 1/2. Consequently, EU (t − quant(t))2 ≤ C 1 + t2 +
δ2 ′ F (t)2
.
Applying this with t = Xa gives Eε,U (Xa − quant(Xa ))2 1{|Xa |>MB } h 2 i ≤ O Eε (1 + Xa2 )1{|Xa |>MB } + Eε eXa /3 1{|Xa |>MB } B −2 . Using Lemma A.2 and the same argument in Lemma A.1, this tail contribution is at most O(poly log B · e−5 log B/2 ) = o(1)B −2 . Combining the central and tail estimates, we obtain 2
Eε,U (Xa − quant(Xa )) ≤
! √ π 3 + o(1) B −2 . 2
uniformly over all d ≥ 1 and all unit vectors a ∈ Rd . Using Lemma A.9, we immediately obtain our main theorem (Theorem 1.1), that x e is unbiased with the claimed mean squared error bounded. Proof of Theorem 1.1. Regarding the mean squared error bound, as in the proof of 2.2, fix x ∈ S d−1 , we have that d 1X ED,U ∥x − x e∥22 = ED,U (zi − quant(zi ))2 . d i=1 √ √ where zi = dyi = d(HDx)i follows the distribution of Xa for some unit vector a. Applying Lemma A.9 to each coordinate gives √ π 3/2 + o(1) 2 ED,U (zi − quant(zi )) ≤ . B2 Then averaging over i, we obtain √ π 3/2 + o(1) 2 ED,U ∥x − x e∥2 ≤ . B2 For the √ unbiasedness, we condition on D. Once D is fixed, the vector y = HDx and hence all zi = d yi are deterministic. By the unbiasedness part of Lemma A.9, EU [quant(zi ) | D] = zi . 21
Thus
zi 1 EU [e yi | D] = √ EU [quant(zi ) | D] = √ = yi . d d Since this holds for every coordinate, EU [e y | D] = y = HDx.
Therefore
EU [e x | D] = DH ⊤ EU [e y | D] = DH ⊤ HDx = x. Finally, taking expectation over D gives ED,U [e x] = x.
B
Analysis of the inner product quantizer
We present the analysis of the inner product quantizer in this section, proving Theorem 1.2. Similarly to how the analysis of our vector quantizer relied on a moment generating function bound for Rademacher random variables, the analysis of the inner product quantizer hinges on the following fourth moment bound satisfied by Rademacher random variables: Lemma B.1 (Mixed fourth moment). Let η1 , . . . , ηd be independent Rademacher signs. Let X=
d X
aj ηj ,
d X
Y =
j=1
bj η j ,
j=1
where ∥a∥ = ∥b∥ = 1. Then 2
E[X 2 Y 2 ] = 1 + 2 ⟨a, b⟩ − 2
d X
a2j b2j ≤ 3.
j=1
Consequently, E X 2 (A2 + 3Y 2 ) ≤ A2 + 9. Proof. Write X2 =
X
a2j + 2
j
X
aj ak ηj ηk = 1 + 2
j<k
X
aj ak ηj ηk ,
j<k
and similarly Y2 =1+2
X
bj bk ηj ηk .
j<k
Multiplying and taking expectations, all terms vanish except those with the same pair {j, k}. Therefore X E[X 2 Y 2 ] = 1 + 4 aj ak bj bk . j<k
Since
2
⟨a, b⟩ =
X
a2j b2j + 2
j
we obtain 4
X
X
aj ak bj bk ,
j<k 2
aj ak bj bk = 2 ⟨a, b⟩ − 2
X
a2j b2j .
j
j<k
2
This proves the identity. The upper bound follows because ⟨a, b⟩ ≤ 1 and
2 2 j aj bj ≥ 0.
P
Finally, since EX 2 = 1, for any κ > 1, we have E X 2 (A2 + (κ2 − 1)Y 2 ) ≤ A2 + 3(κ2 − 1) Setting κ = 2 gives the conclusion. Roadmap. In what follows we prove an upper bound on the rate of the quantizer, i.e. show that it uses constant number of bits per coordinates, in Section B.1. We then analyze the error of the quantizer and prove Theorem 1.2 in Section B.2. 22
B.1
Rate Bound
In this section, we show that the output of the residual quantizer from Algorithm 3 can be stored in O(d) bits. Lemma B.2. Let B ≥ 2 and let r ∈ Rd such that ∥r∥2 ≤ 2. Run the R ESIDUAL Q UANT procedure of Algorithm 3, using Algorithm 2 for the residual scale. Then the output idxσ , ℓ, λ can be stored 1 using 3 + 2 ln 2 d + O(log log(dB)) total bits. Proof. We consider the non-trivial case idxσ > 0. Recall that v = HDr. Also recall that S CALAR D∥r∥ EQUANT outputs σ = τB 2idxσ −1 = τB 2⌈log2 (s/τB )⌉ . By this definition, σ ≥ s := √ 2 . Therefore, if d we write Zi := |vσi | , then d X
2
2
Zi2 =
i=1
∥r∥ ∥HDr∥2 = 22 ≤ d σ2 σ
where the second step follows from the fact that HD is orthogonal. Then by the definition of the level, ℓi ≤ 1 + log+ 2 (Zi ), 2 where log+ 2 (s) = max{0, log2 s}. Since log s ≤ s /2 for s ≥ 1,
log+ 2 (Zi ) ≤
Zi2 . 2 ln 2
Thus d X
(ℓi + 1) ≤
2+
i=1
1 2 ln 2
d.
√ 2 ∈ This bounds the bit usage of recording the levels ℓ1 , . . . , ℓd . Finally, when ∥r∥2 ≤ 2, s = ∥r∥ d 2 [0, √d ], thus as mentioned in Section 4, idxσ can be encoded using
2 ⌈log2 (⌈log2 ( √ /τB )⌉ + 2)⌉ = O(log log(dB)) d bits. λ1 , . . . , λd can be stored trivially in d total bits. Combining these give the claimed bound.
Remark B.3 (Expected bits per level). Lemma B.2 gives a deterministic O(d) bound on the total number of bits. Alternatively, we can also show that each level ℓi can be stored in O(1) bits in expectation. To that effect, define vi (HDr)i Yi = = . s s √ The coefficient vector of Yi has norm one, since |Hij | = d−1/2 and s = ∥r∥ / d. Hence 2
P(|Yi | > t) ≤ 2e−t /2 . For k ≥ 1, the event {ℓi ≥ k} implies |vi | > σ2k−1 ≥ s2k−1 . Therefore 2(k−1) 2 P(ℓi ≥ k) ≤ 2 exp − , 2 so the expected unary length of each level is bounded by an absolute constant. Remark B.4 (Entropy coding the levels). One could replace the unary encoding of the levels ℓi by a Huffman (or other entropy) code. This only gives a small improvement: since Pr(ℓi ≥ k) ≤ 2 exp −22(k−1) /2 (k ≥ 2), 23
the level distribution has doubly-exponential tails, and its entropy is bounded by a small absolute constant. In particular, X 2 H(ℓi ) ≤ + ak log2 (1/ak ) < 1.579, ak = 2 exp −22(k−1) /2 . e ln 2 k≥2
Thus a prefix code would use, on average, fewer than (H(ℓi ) + 1) + 1 < 3.579 bits per coordinate including the sign bit, compared with the unary deterministic bound 3 + 1/(2 log 2) ≈ 3.72. B.2
Error Bounds for the Residual Quantizer
In the next lemma, we bound the error of the residual quantizer (Algorithm 3). This guarantee will later be used in the analysis of our inner product quantizer (Algorithm 4). Lemma B.5. Let B ≥ 2 and let r, y ∈ Rd . Run the quantization procedure of Algorithm 3, using Algorithm 2 for the residual scale. Then 2
E| ⟨y, rb − r⟩ |2 ≤ 13
2
∥y∥ (∥r∥ + B −2 ) . d
Proof. If y =√0, the claim is immediate. So we consider the non-trivial case where y ̸= 0. Let s = ∥r∥/ d. Also, let idxσ be the output of S CALAR Q UANT(s) and let σ be the output 2 of S CALAR D EQUANT(idxσ ). If σ = 0, then rb = 0 and s < 1/(dB), so ∥r∥ < 1/(dB 2 ). Hence 2
2
2
2
| ⟨y, rb − r⟩ |2 ≤ ∥y∥ ∥r∥ ≤
2
∥y∥ (∥r∥ + B −2 ) ∥y∥ ≤ 13 . dB 2 d
Now assume σ > 0. Set A = σs . As mentioned in Section 4, by the definition of σ we have 1 ≤ A < 2. Let u = HDy and v = HDr. Conditional on D, r, the variables qi − vi are independent and centered, and d X E | ⟨y, rb − r⟩ |2 | D, r = u2i (Ri2 − vi2 ). i=1
Define
√ Xi =
d ui , ∥y∥
Yi =
vi . s
Since Ri = σ2ℓi = As2ℓi and ℓi is chosen to be the smallest level such that |vi | ≤ R, either ℓi = 0 in which case Ri = As, or ℓi ≥ 1, in which case |vi | > As2ℓi −1 and multiplying by 2 gives Ri < 2|vi |. In both cases, we have Ri2 − vi2 ≤ s2 A2 + (22 − 1)Yi2 . Therefore E| ⟨y, rb − r⟩ |2 ≤
2 2 d ∥y∥ ∥r∥ X 2 2 E Xi A + 3Yi2 . d2 i=1
For each i, the coefficient vectors defining Xi and Yi have norm one, so the mixed fourth-moment lemma gives E Xi2 A2 + 3Yi2 ≤ A2 + 9. Since A < 2, this yields 2
E| ⟨y, rb − r⟩ |2 ≤ 13
2
2
2
∥y∥ (∥r∥ + B −2 ) ∥y∥ ∥r∥ ≤ 13 . d d
24
B.3
Proof of Theorem 1.2
We now prove Theorem 1.2, restated here for convenience of the reader: Theorem B.6 (Repeating Theorem 1.2). Let x ∈ S d−1 be a unit vector and let y ∈ Rd . Let x b be the reconstructed vector produced by Algorithm 4 with a base bit-width b. Then ! √ 2 π 3 ∥y∥ E| ⟨y, x b − x⟩ |2 ≤ 13 , + 1 + o(1) 2 d · 4b where the o(1) term vanishes as b → ∞, uniformly over d and x. Moreover, the output of Q UANTIZE(x) from Algorithm 4 can be stored using db + (3 +
1 )d + O(log(b + log d)) 2 ln 2
total bits. b=x e + rb, where r = x − x e. Proof. We write B = 2b . Recall that the two-stage quantizer outputs x Condition on the randomness of the first stage, so that r is fixed. By Lemma B.5, 2 2 ∥y∥ (∥r∥ + B −2 ) EDres | ⟨y, rb − r⟩ |2 | Dbase , U ≤ 13 . d Taking expectation over the first stage gives
E| ⟨y, x b − x⟩ |2 ≤ 13
2 ∥y∥ 2 EDbase ,U ∥x − x e∥2 + B −2 . d
e before projecting to the unit ball via Π, then by Theorem 2.2, we have If we use x to denote x √ π 3/2 + oB (1) 2 EDbase ,U ∥x − x∥2 ≤ . B2 Since the unit ball is a closed convex set and x ∈ S d−1 , point-wise it always hold that ∥x − x e∥22 = ∥x − Πx∥22 ≤ ∥x − x∥22 thus
√ π 3/2 + oB (1) . B2 Substituting this bound proves the theorem. The total bit usage is db bits for idx plus the bit usage from Lemma B.2. Note that we have ∥r∥ ≤ 2 because after projecting onto the unit ball, both ∥x∥, ∥e x∥ ≤ 1. 2
EDbase ,U ∥x − x e∥2 ≤
25