Data, data everywhere. Is there a better way to keep it manageable? Turns out a decades-old method may actually be the best.
As data processing became more and more complex, computer scientists turned to pure mathematics to help speed algorithmic processing. A solution was found in the Johnson-Lindenstrauss lemma (JL lemma), a theorem proved in the 1980s by mathematicians William B. Johnson and Joram Lindenstrauss. This theorem has been used to reduce the dimensionality of data and speed up algorithms across many different fields – from streaming and search, to statistical and linear algebra to computational biology.
The JL lemma showed that for any finite collection of points in high dimension, there is a collection of points in a much lower dimension which preserves all distances between the points, up to a small amount of distortion. While its original impact was in the area of functional analysis, computer scientists found that it can act as a pre-processing step, allowing data dimensions to be significantly reduced before running algorithms.
Yet as data has grown even larger and more complex, computer scientists have asked whether the JL lemma remains the best approach for pre-processing.
A paper presented at IEEE’s annual Symposium on Foundations of Computer Science (FOCS) indicates that, in fact, it is.
"We have proven that there are 'hard' data sets for which dimensionality reduction beyond what's provided by the JL lemma is impossible," said Jelani Nelson, an engineering and applied sciences professor at the Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS).
To speed things up, the JL lemma uses a system of geometric classification wherein individual dimensions don't matter as much as similarities between them. By mapping these similarities, the geometry of the data and the angles between data points are preserved. As a result, it's reconstructing sparse signals using few linear measurements, clustering high-dimensional data and DNA motif finding. It’s also used for spam filtering.
Noga Alon, professor of Mathematics at Tel Aviv University who has also done research on JL lemma, called the development “a refreshing demonstration of the power of a clever combination of combinatorial reasoning with geometric tools in the solution of a classical problem."
