Hadamard and the Random Rotation

A random rotation in d dimensions costs you a d × d matrix. At d = 1536 that is about 2.4 million numbers to store, and a sum over all 1,536 inputs for every output coordinate, which is O(d²) work on every vector you touch. Do that across ten million vectors and the rotation, not the search, becomes your bill.

The Hadamard transform does almost the same job with a matrix made entirely of +1 and -1, in O(d log d), without storing the matrix at all. It is one of those tricks you meet once and then keep finding everywhere: quantization, dimensionality reduction, private aggregation, the residual correction inside turbovec. Worth understanding once.

What the matrix is

A Hadamard matrix is orthogonal and every entry is +1 or -1, scaled by 1/√d so the rows come out unit length. It is built by doubling:

1
H_1 = [1]        H_2n = [ H_n   H_n ]
2
                        [ H_n  -H_n ]

H_2 is [[1, 1], [1, -1]], H_4 is that same pattern of H_2 blocks, and so on up. The size has to be a power of two, so in practice you pad the vector up to the next one.

The reason anyone uses it is that the recursive structure means you never build the matrix. You apply it with the Fast Walsh-Hadamard Transform, which has the same divide-and-conquer shape as the FFT: split the vector in half, add and subtract the halves, recurse. That is where the O(d log d) comes from. A dense matrix product becomes a log-depth tree of additions.

Making it random

Plain Hadamard is a fixed matrix, not a random one. It mixes coordinates, but it mixes them the same way every time, and a vector that lines up with its structure passes through barely scrambled. That is not the rotation you want.

The fix is one diagonal matrix of random signs. Call it D: a diagonal of +1 and -1 picked once from a seed. Flip the signs of the input coordinates first, then run the Hadamard transform. The whole operation is H·D.

That small addition is enough. D is orthogonal and H is orthogonal, so H·D is orthogonal too. It preserves every length, distance, and inner product, which is the only property a rotation has to keep. The random sign flips break the alignment that plain Hadamard couldn’t, so the output now behaves like a real rotation: each input coordinate’s weight spreads across all the outputs, outliers flatten, and the coordinates settle into a predictable distribution. You pay O(d log d) compute and d sign bits of storage, instead of a d × d matrix and O(d²) compute.

You pick the signs once and reuse the same transform for every vector. Encoding and querying have to rotate the same way, and a fixed seed gives you that for nothing.

Where you meet it

The first place most people see it is the fast Johnson-Lindenstrauss transform. The plain JL result says you can project high-dimensional vectors down to far fewer dimensions with a random matrix and keep the distances between them almost intact. Ailon and Chazelle’s version swaps the dense random matrix for a randomized Hadamard plus a subsample, and the projection drops from O(d²) to O(d log d). Same guarantee, a fraction of the cost. Add row subsampling and you have the SRHT, the subsampled randomized Hadamard transform.

After that it is the same idea wearing different clothes. TurboQuant uses it as the rotation that makes embedding coordinates Gaussian before scalar quantization, which is what lets it skip codebook training. QJL uses it to project a residual down to sign bits without biasing the inner product. Differential privacy uses it to spread a value across coordinates before adding noise. The matrix of +1 and -1 shows up wherever someone needs a rotation or a projection and cannot afford the dense version.

What to keep in mind

One pass of H·D is cheap but not a perfect random rotation. It is close enough for the projection guarantees, but when you need it closer to a true uniform rotation you stack two or three rounds of sign-flip-then-Hadamard, still in O(d log d).

The power-of-two requirement means padding, and padding wastes a little work when your dimension sits just above a boundary: 1,030 dimensions pads to 2,048. The transform also mixes globally, so there is no sparsity to exploit, and every output depends on every input. None of this is usually a problem. You reach for it precisely because the costs are predictable and small.

Appendix: the vocabulary, explained simply

Every technical term in this post, in plain language, with the math vocabulary set aside. Read them in any order; each one stands on its own.

Vector and dimensions

A vector is just a list of numbers, and each number in the list is one dimension. You can picture it as an arrow pointing somewhere in space: a list of 2 numbers is an arrow on a flat page, a list of 3 is an arrow in a room, and a list of 1,536 is an arrow in a space too big to imagine but that behaves by the same rules. When this post says d = 1536, it means each item is described by a list of 1,536 numbers. That is normal for the “embeddings” search engines use.

Matrix

A matrix is a grid of numbers, with rows and columns. Its job here is to transform a vector: you feed in one list of numbers, the grid mixes them according to its recipe, and out comes a new list. A d × d matrix has d rows and d columns, so for d = 1536 that is 1,536 × 1,536 ≈ 2.4 million numbers to store and a lot of multiplying to do. That size is exactly the cost this post is trying to avoid.

Random rotation

A rotation spins everything the same way at once, like turning a globe. The important thing is what spinning does not change: the distance between New York and Tokyo is the same before and after, and the angle between any two arrows stays the same too. A random rotation is just a spin by some arbitrary, unpredictable amount. We want one because it scrambles the individual numbers inside each vector into a predictable, well-behaved pattern without disturbing any of the distances or angles that searching depends on.

Orthogonal matrix

Orthogonal is the math word for “this transformation is a pure rotation or mirror-flip, nothing else.” It never stretches, squashes, or skews; it only turns things. That is why an orthogonal matrix preserves every length, distance, and angle. When the post says H and D are orthogonal and therefore H·D is too, it is saying that doing one clean spin after another still gives you a single clean spin.

Inner product (dot product)

The inner product is a single number you get from two vectors that measures how much they point the same way. Big and positive means they line up; near zero means they’re unrelated; negative means they point opposite. Search engines use it as a similarity score: the stored vector with the highest inner product against your query is the best match. Anything that quietly changes these numbers can reshuffle search results, which is why the post cares so much about preserving them.

Big-O notation: O(d²) versus O(d log d)

Big-O is shorthand for how the work grows as the problem gets bigger, ignoring the small stuff. O(d²) means the work grows with the square of the size: double d and the work goes up four-fold. O(d log d) grows almost in step with the size, just a hair faster. The gap is enormous at real sizes: for d = 1536, d² is about 2.4 million operations, while d log d is closer to 17,000 — roughly 140 times less work for the same result. That difference is the whole reason this trick exists.

Hadamard matrix

A Hadamard matrix is a special grid made entirely of +1 and -1, arranged so that it acts as a clean rotation. It is built by doubling: start with a tiny block, then paste four copies into a block twice as wide, flipping the sign of the bottom-right copy, and repeat until it’s big enough. Because every entry is just a plus or minus one, multiplying by it is all additions and subtractions — no real multiplying — which is part of why it’s so cheap.

Fast Walsh–Hadamard Transform

This is the shortcut for applying a Hadamard matrix without ever building or storing it. Instead of the full grid of multiplications, you split the vector in half, add the two halves together and subtract them, then repeat the same move on each half, and again, until you can’t split anymore. All those add-and-subtract passes add up to exactly the same answer the giant matrix would give, but in O(d log d) work instead of O(d²). It’s the difference between computing a result the long way and finding a clever pattern that gets you there in a few quick passes.

Fast Fourier Transform (FFT)

The FFT is the Hadamard shortcut’s famous cousin. It’s the algorithm that makes things like audio processing and image compression fast, and it works by the same trick: split the problem in half, solve each half, and combine. The post mentions it because anyone who has met the FFT will recognize the exact same divide-and-combine shape in the Walsh–Hadamard transform.

Divide and conquer

A general problem-solving pattern: instead of attacking a big job all at once, split it into smaller copies of itself, solve those, and stitch the answers back together. Sorting a huge pile of papers by splitting it into two half-piles, sorting each, then merging them is divide and conquer. Both the FFT and the Walsh–Hadamard transform get their speed from this idea.

Diagonal matrix of random signs (the “D”)

A diagonal matrix is a grid that’s blank everywhere except the line running corner to corner. When that diagonal is filled with a random mix of +1 and -1, multiplying by it simply flips the sign of some of your input’s numbers, chosen at random, and leaves the rest alone. It’s the cheapest possible scramble. The post calls it D, and it’s the small ingredient that turns the fixed, predictable Hadamard transform into something that behaves like a genuinely random rotation.

Seed

A seed is a starting number that makes “random” repeatable. Computer randomness isn’t truly random; it’s a long sequence generated from a seed, so the same seed always produces the same sequence. That’s exactly what you want here: you pick the random signs once from a seed, and as long as you reuse the seed, every vector — whether you’re storing it or searching for it — gets flipped the same way. Without that, the stored data and the query would be scrambled differently and the search would break.

Power of two and padding

The doubling construction means a Hadamard matrix only comes in sizes that are powers of two: 1, 2, 4, 8, 16, … 1,024, 2,048, and so on. If your vector’s length isn’t one of those, you pad it — tack on extra zeros until it reaches the next power of two. The cost is a little wasted work when you land just above a boundary: a vector of length 1,030 has to pad all the way up to 2,048, nearly doubling its size for the transform.

Gaussian distribution (the bell curve)

A Gaussian distribution, or bell curve, is the familiar shape you get when many small random effects add up: lots of values bunched near the middle, fewer and fewer toward the extremes, like the spread of human heights. Roll one die and every number is equally likely; roll twenty and add them, and the totals pile up in the middle, because hitting an extreme needs every die to cooperate. A rotation mixes every coordinate into every output, so each output becomes one of these “sum of many things” numbers — and lands on a bell curve no matter how lopsided the original data was. Predictable shape is what makes the next step easy.

Outliers and dynamic range

An outlier is a value that’s far larger than the rest. Dynamic range is the gap between the smallest and largest values you have to account for. Outliers are a problem for compression: if one coordinate occasionally spikes huge, you have to reserve room for that spike everywhere, which wastes precision on all the normal small values — like sizing every parking space for a bus because one bus might show up. A random rotation flattens outliers into the bell curve, shrinking the dynamic range so every value can be stored with the same modest precision.

Dimensionality reduction

Dimensionality reduction means taking vectors with a huge number of dimensions and squashing them down to far fewer, while keeping the information that matters. The catch is keeping the distances roughly intact: two vectors that were close should stay close, two that were far should stay far, even in the smaller space. It’s like drawing a flat map of the round Earth — you lose a dimension, but a good map still keeps cities that are near each other near each other. Smaller vectors mean less memory and faster comparisons.

Johnson–Lindenstrauss transform

This is the surprising guarantee that powers dimensionality reduction. The Johnson–Lindenstrauss result says: take points in a very high-dimensional space, multiply them by the right random matrix to project them into a much smaller space, and the distances between them barely change. You don’t need to study the data or be clever about which dimensions to keep — a random projection just works, as long as the target size is big enough. It sounds too good to be true, but it’s a proven theorem, and it’s why “just project it down randomly” is a legitimate strategy.

Fast Johnson–Lindenstrauss transform (FJLT)

The plain Johnson–Lindenstrauss projection uses a dense random matrix, which is O(d²) work — the very cost this post complains about. Ailon and Chazelle’s FJLT fixes that by replacing the dense matrix with the cheap combo from this post: flip random signs, run the Hadamard transform, then keep a random subset of the outputs. Same distance-preserving guarantee, but O(d log d) work. It’s the original “use Hadamard instead of a real random matrix” move, and most later tricks are variations on it.

Subsampling and the SRHT

Subsampling just means keeping only some of the outputs and throwing the rest away — for instance, picking 200 of the 1,536 coordinates at random. After a Hadamard rotation has stirred every input into every output, any random handful of outputs is a fair summary of the whole thing, so you can safely drop most of them to get a smaller vector. The combination of random sign flips, a Hadamard transform, and this subsampling step has its own name: the SRHT, or subsampled randomized Hadamard transform.

Quantization (scalar quantization)

Quantization is rounding numbers into a small set of buckets so each one takes less space to store. Instead of a precise decimal, you record which bucket it fell in — like rounding everyone’s age to the nearest ten. Scalar quantization does this to each number on its own, independently. You save a lot of memory, at the price of small rounding errors. The trick to doing it well is choosing good bucket boundaries, and that’s much easier when you already know the numbers follow a predictable bell curve.

Codebook and codebook training

A fancier kind of quantization, product quantization, doesn’t round numbers one at a time; it stores a learned dictionary of typical chunk-patterns called a codebook and replaces each chunk of a vector with the nearest entry in that dictionary. Building that dictionary means studying your specific dataset first — that’s codebook training. It works well but it’s an extra step that depends on your data, has to be redone when the data changes, and adds complexity. A big selling point of the Hadamard-rotation approach is that it makes the data so predictable you can skip training entirely and use buckets worked out in advance by pure math.

Embedding

An embedding is a vector produced by an AI model that captures the meaning of something — a sentence, an image, a product. The model is trained so that similar things get similar vectors, which is what lets you search by meaning instead of by exact keywords. Embeddings are typically long lists (hundreds to a couple thousand numbers), which is why making operations on d-dimensional vectors cheap matters so much in practice.

TurboQuant

TurboQuant is a recent method (Zandieh, Daliri, Hadian, and Mirrokni, 2025) for compressing vectors that leans on exactly this post’s trick. It applies a randomized Hadamard rotation to force every coordinate onto a Gaussian bell curve, then uses plain scalar quantization with bucket boundaries computed in advance. Because the rotation guarantees the shape of the data, there’s no codebook training — and it still lands provably close (within about 2.7×) to the theoretical best compression for its bit budget.

QJL (Quantized Johnson–Lindenstrauss)

QJL is the Johnson–Lindenstrauss idea pushed to the extreme: project a vector down with a random Hadamard rotation, then keep only the sign of each output — a single bit, plus or minus, nothing else. Remarkably, a pile of these crude one-bit readings still gives an unbiased estimate of the inner product (its errors push up and down equally, so they cancel out across many of them rather than skewing the score). Because you store only signs, there are no extra scaling numbers to keep alongside, which is why its inventors describe it as having “zero overhead.” It was introduced to shrink the memory that large language models use during inference.

Residual correction inside turbovec

When you quantize by rounding into buckets, the gap between the true value and the bucket it landed in is the residual — the rounding leftover. Those leftovers are tiny individually but pile up across a thousand-plus coordinates into enough error to flip close search results. Turbovec corrects for this in two ways: it computes a small correction scalar to undo the way rounding systematically shrinks inner products, and it captures the residual itself with a 1-bit QJL transform (the Hadamard-then-sign trick above), recovering roughly an extra bit of accuracy per coordinate for almost no memory.

Differential privacy and private aggregation

Differential privacy is a mathematical way to publish useful statistics about a group while guaranteeing no individual’s data can be singled out, achieved by deliberately adding random noise. Private aggregation is combining many people’s noisy reports into one trustworthy total. The Hadamard transform helps here for the same spreading reason as everywhere else: a single person’s value, which sits in one coordinate, gets smeared across all coordinates by the rotation, so each device can send back just one bit and the signal survives — and the added privacy noise spreads out evenly instead of swamping any one number.

Vector search (nearest neighbor)

Vector search, also called nearest-neighbor search, is the task underneath all of this: given a query vector, find the stored vectors most similar to it (highest inner product or smallest distance). It’s how “search by meaning” works — you turn the query into an embedding and look for the closest embeddings in your collection. Everything in this post is about doing the rotation step of that pipeline cheaply, without changing which neighbors come back.