Johnson-Lindenstrauss Transform

Computers often describe things through long lists of numbers. A single sentence can thus become a list of 1536 numbers, an image a list of several thousand. How similar two things are is then measured as the distance between their two number lists: a small distance means similar, a large distance means dissimilar. However, such long lists cost a lot of memory and computing time. The Johnson-Lindenstrauss transform shortens them drastically, for example from 1536 numbers to 128. The clever part: the distances between the shortened lists remain almost the same as before. The method is named after the mathematicians William B. Johnson and Joram Lindenstrauss, who proved the underlying theorem in 1984.

Why short number lists save real money

Modern AI systems constantly compare such number lists with one another. A search engine for company documents might hold ten million of them ready. With every search query, it must compare the query with a great many stored lists. If you halve the length of the lists, the computational work per comparison roughly halves as well.

Even more important is memory. Ten million lists of 1536 numbers each occupy several dozen gigabytes. That no longer fits into the fast working memory of a normal server, and accesses to the slower hard drive slow everything down. Shortening to 128 numbers shrinks the requirement to a fraction and everything stays in fast memory.

The real reason for the method’s fame, however, is a surprising claim. How much you are allowed to shorten hardly depends at all on how long the lists originally were. What matters is only the number of objects and the error you are willing to accept. Whether you start from 1000 or from 100,000 numbers changes little about the target.

Random projection instead of clever selection

One might think the method carefully selects the most important numbers. That is exactly what it does not do. Instead, one generates a table of purely random numbers and multiplies each list by it. From this calculation, a new, shorter list emerges for each list. The random table is generated once and then used identically for all objects.

That randomness works here is the actual mathematical core. The theorem of Johnson and Lindenstrauss guarantees: with high probability, every distance deviates from the original distance only by a small percentage after shortening. Typical bounds are around ten percent. A good comparison is the shadow of a wire-frame model on a wall. From most viewing angles, one can still recognize the shape and the rough proportions well, even though one dimension is lost.

There is a price. Anyone who wants to halve the permitted error needs roughly four times the length of the new lists. Very precise results thus quickly become expensive. Moreover, the new numbers are meaningless to humans, because they are mixtures of all the old numbers. And the guarantee applies to distances, not to any arbitrary feature of the data.

Vector databases, recommendations, and image search

Today, the method is most commonly encountered in so-called vector databases. These are storage systems that manage number lists and return the most similar ones on request. They power chatbots that search company-internal documents before answering. Many such systems shorten the lists in advance to reduce memory usage and response time.

Recommendation systems in online shops and streaming services also use similar shortenings. The same applies to image search: two photos are considered similar if their number lists lie close together. In technical texts and product descriptions, the term often appears as random projection or as JL lemma.

A related term is principal component analysis, or PCA for short. It, too, shortens number lists, but specifically searches for the most meaningful directions in the data. This often delivers better results but costs additional computing time and must be redone for new data. The Johnson-Lindenstrauss transform does not need to look at the data at all and is therefore particularly fast and simple.