🤖 machine learning

Provable Quantization with Randomized Hadamard Transform

This paper introduces a dithered quantization method using a single randomized Hadamard transform that achieves unbiased, provable mean squared error bounds asymptotically matching those of dense random rotations while maintaining an efficient $O(d \log d)$ computational cost.

Original authors: Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Compressing Data Without Losing the Plot

Imagine you have a massive library of books (data), but you only have a tiny suitcase to carry them on a trip. You need to shrink the books down to fit, but you also need to make sure that when you unpack them later, they still make sense and haven't turned into gibberish.

In the world of machine learning, this "shrinking" is called quantization. It's the process of turning complex, precise numbers (like 3.14159265) into simple, short codes (like "3" or "A") to save space and speed up calculations.

The problem is: if you shrink them too aggressively or carelessly, the "books" get distorted. The paper proposes a new, clever way to shrink these numbers that is both fast and mathematically guaranteed to keep the distortion very low.

The Old Way: The Slow, Perfect Shrinker

For a long time, the best way to shrink data involved a "magic shuffle." Imagine you have a deck of cards (your data points). To compress them, you first shuffle the deck perfectly randomly so that every card is mixed with every other card. Then, you take a snapshot of each card and write down a simple note about it.

The Good: This shuffle (called a "random rotation") guarantees that the notes you write down are very accurate.
The Bad: Shuffling a deck of 1 million cards perfectly randomly takes an incredibly long time. It's like trying to mix a swimming pool full of water by hand. It's too slow for modern computers.

The Faster Way: The Hadamard Shuffle

To speed things up, engineers started using a specific, pre-arranged pattern to shuffle the cards, called the Hadamard Transform.

The Good: This is like having a machine that shuffles the deck in a split second. It's incredibly fast.
The Bad: Because the shuffle follows a strict pattern, it's not "truly random." Sometimes, the notes you write down are a little bit biased or inaccurate. It's like using a stamp that always leaves a slightly crooked mark. The math to prove it works perfectly was missing.

The Paper's Solution: The "Dithered" Shuffle

The authors of this paper asked: Can we keep the speed of the Hadamard machine but fix the crooked marks?

Their answer is Dithering.

The Analogy: The Jittery Camera

Imagine you are trying to take a photo of a moving object with a camera that has a slightly sticky shutter. Sometimes the photo comes out a bit blurry or shifted.

The Trick: Before you take the photo, you shake the camera slightly in a completely random direction (this is the "dither" or "random offset").
The Result: Even though the camera is still sticky, that tiny random shake averages out the errors. Over many photos, the blur disappears, and the image becomes sharp again.

In this paper, the "camera" is the quantization process, and the "shake" is adding a tiny, random number to the data before compressing it.

What They Proved

The authors didn't just guess that this would work; they did the heavy math to prove it.

It's Unbiased: They proved that if you use this "shaken" Hadamard method, the average result is exactly the same as if you had used the slow, perfect random shuffle. You aren't systematically losing information in one direction or another.
It's As Accurate as the Best: They showed that as you use more bits (more detail in your notes), the error rate of their fast method gets closer and closer to the error rate of the slow, perfect method. In fact, it matches the theoretical best possible performance.
It's Fast: Because they only use one Hadamard shuffle (plus a tiny random shake), the process remains incredibly fast ( $O(d \log d)$ ), making it suitable for huge datasets.

The Two-Stage Process (For Inner Products)

The paper also tackles a specific, harder task: comparing two vectors (calculating the "inner product"). Think of this as trying to guess how similar two songs are without listening to the whole thing.

They propose a two-step compression:

The Main Compression: Compress the first song using their fast, "shaken" method.
The "Leftover" Compression: Whatever didn't fit perfectly (the "residual" or the difference between the real song and the compressed version) is compressed separately using a second, simpler trick.

They proved that even with this two-step process, the error remains very low, and the total amount of data stored is still very small.

Summary

The Problem: We need to compress data fast, but the fastest methods usually have weak math guarantees.
The Solution: Use a fast, structured shuffle (Hadamard) but add a tiny bit of random noise (dithering) to fix the errors.
The Result: A method that is as fast as the industrial standard but has the same mathematical guarantees as the slow, perfect theoretical standard.

In short: They found a way to make the "fast shuffle" just as good as the "perfect shuffle" by adding a little bit of controlled chaos.

Technical Summary: Provable Quantization with Randomized Hadamard Transform

Problem Statement
Vector quantization is a fundamental primitive for compressing real-valued vectors in $\mathbb{R}^d$ into compact binary representations, with applications ranging from similarity search and federated learning to efficient transformers and model compression. A standard approach involves applying a random rotation matrix $R$ to the input vector $x$ followed by scalar quantization. While dense random rotations provide clean theoretical guarantees (e.g., coordinates of $Rx$ are approximately Gaussian), they require $\Theta(d^2)$ time to apply, which is prohibitive for high-dimensional vectors.

To address this, the randomized Hadamard transform ( $H_D$ ), which applies in $O(d \log d)$ time, is often used as a structured alternative. However, $H_D$ is not a uniformly random rotation; it possesses a discrete structure that complicates theoretical analysis. Existing results for quantization using a single $H_D$ are either purely empirical or provide provable guarantees that are weaker (requiring higher dimensions or more bits) than those achievable with truly random rotations. The challenge is to achieve the speed of the Hadamard transform ( $O(d \log d)$ ) while retaining the strong theoretical distortion bounds of random rotations.

Methodology
The authors propose a variant of vector quantization that combines a single randomized Hadamard transform with dithering (the injection of random offsets). The core methodology involves:

Transformation: The input vector $x$ is transformed via $y = H_D x$ , where $H$ is a normalized Hadamard matrix and $D$ is a diagonal matrix with independent Rademacher ( $\pm 1$ ) entries.
Dithered Scalar Quantization: Instead of directly quantizing the coordinates of $y$ $y$ , the method applies a scalar quantizer to each coordinate after shifting it by a random offset.
- The scalar quantizer is based on a dithered version of Lloyd quantization.
- It utilizes a specific mapping function $F(t)$ , defined as the cumulative distribution function (CDF) of a Gaussian random variable with mean 0 and variance 3 (derived from the density $\phi(t)^{1/3}$ ).
- A random shift parameter $U \sim \text{Unif}[0, 1)$ is applied to the quantization grid in the quantile space.
Unbiasedness: The paper presents two algorithms. Algorithm 1 provides the mean squared error (MSE) bound but is slightly biased. Algorithm 5 modifies the reconstruction rule (using a specific function $G$ instead of $F^{-1}$ ) to ensure the estimator is unbiased ( $E[\hat{x}] = x$ ) while preserving the asymptotic MSE bounds.
Inner Product Quantization: To support inner product estimation, the authors propose a two-stage quantizer (Algorithm 4). After the base quantization, the residual vector $r = x - \hat{x}$ $r = x - \overset{x}{^}$ is quantized. This involves:
- Quantizing the scale of the residual.
- Applying a fresh randomized Hadamard transform to the residual.
- Quantizing the coordinates of the transformed residual using a level-based scheme and randomized sign bits to decorrelate the error from the query vector.

Key Contributions and Results

Asymptotic Optimality: The primary theoretical contribution is proving that dithered quantization with a single randomized Hadamard transform achieves mean squared error bounds that asymptotically match those of truly random rotation matrices.
- Theorem 1.1: For any unit vector $x$ , the unbiased estimator $\hat{x}$ satisfies:
  $E[\|\hat{x} - x\|_2^2] \le \left(\frac{\pi\sqrt{3}}{2} + o(1)\right) \cdot 4^{-b}$
  where $b$ is the bit-width per coordinate. The $o(1)$ term vanishes uniformly as $b \to \infty$ over all dimensions $d$ and unit vectors $x$ . This constant matches the bound achieved by TurboQuant (which assumes fully random rotations).
Unbiasedness: The proposed quantizer is unbiased, a critical property for applications like federated learning where bias accumulation can degrade model convergence.
Inner Product Guarantees: The paper provides a bound for the error in estimating inner products (Theorem 1.2). It shows that the squared error scales as $O(1/(d \cdot 4^b))$ , utilizing a mixed fourth-moment property of Rademacher variables to handle the correlation between the residual and the query vector.
Bit Complexity: The two-stage inner product quantizer can be stored using $db + (3 + \frac{1}{2\ln 2})d + O(\log(b + \log d))$ bits, maintaining linear storage complexity in $d$ .

Significance and Claims
The paper claims that its approach resolves the trade-off between computational efficiency and theoretical guarantees in vector quantization. By introducing dithering, the authors overcome the analytical difficulties posed by the discrete structure of the Hadamard transform.

Theoretical Justification: The work justifies the use of a single randomized Hadamard matrix in methods like TurboQuant and EDEN, which previously relied on fully random rotations for their theoretical guarantees.
Simplicity vs. Complexity: Unlike prior approaches that require composing multiple Hadamard transforms (e.g., $H_{D_1}H_{D_2}$ ) to approximate random rotations, this method achieves comparable guarantees with a single transform and simple dithering, keeping the implementation complexity low.
Limitations: The authors explicitly state that the work is primarily theoretical. It characterizes worst-case mean-squared error and inner-product error but does not optimize finite-bit constants or provide empirical evaluations across downstream systems. The analysis is specific to data-oblivious quantizers based on a single randomized Hadamard transform and randomized dithering.