This paper tackles a fundamental bottleneck in large-scale data analysis: the quadratic cost of distance matrices. By exploiting the geometric structure of these matrices, the authors provide a suite of algorithms that perform essential linear algebra operations in near-linear time, bypassing the need to ever store or fully compute the massive $n \times n$ matrix.
The Quadratic Bottleneck
In many fields—from image processing to biological analysis—we work with a dataset $X$ of $n$ points. To understand the relationships between these points, we often use a distance matrix, where every entry $(i, j)$ is the distance between point $i$ and point $j$.
The problem is scale. A distance matrix has $n^2$ entries. If you have a million points (a common scenario today), the matrix has a trillion entries. Storing it would require terabytes of RAM, and performing even a simple matrix-vector multiplication would take days. However, these matrices aren't "random"—they are generated from points in a much lower-dimensional space ($d$). The authors ask: Can we perform linear algebra on these matrices in time proportional to $n$ and $d$, rather than $n^2$?
Algorithmic Innovations
The authors develop fast algorithms for fundamental linear algebra operations (like matrix-vector multiplication and low-rank approximation) specifically tailored for distance matrices. Their core insight is that the triangle inequality and coordinate-wise structure of distances allow us to "skip" exhaustive comparisons.
Key strategies include:
- Sorting and Partial Sums for $\ell_1$: For the Manhattan distance ($\ell_1$), sorting the points along each dimension allows the sum of absolute differences to be computed using prefix sums. This turns an $O(n^2)$ operation into an $O(nd)$ query.
- Polynomial Expansion for $\ell_p$: For even integers $p$, they expand the distance function $\|x-y\|_p^p$ into a sum of monomials. This allows the matrix-vector product to be decomposed into several simpler products that can be computed quickly.
- Metric Compression: To speed up the construction of approximate $\ell_2$ matrices, they use tools from metric compression to reuse distance calculations, effectively beating the standard runtime bound implied by the famous Johnson-Lindenstrauss (JL) lemma.
One of the most interesting theoretical findings is the "separation" between metrics. While $\ell_1$ is "easy" (linear time), $\ell_\infty$ is fundamentally "hard" (quadratic time). This is proven using a reduction from the Orthogonal Vector Problem (OVP), a standard hard problem in complexity theory.
Key Results and Downstream Applications
The theoretical speedups translate to massive improvements for downstream tasks like low-rank approximations and matrix multiplication.
Empirically, the results are striking, particularly on large-scale datasets. The authors evaluated their $\ell_1$ algorithm on datasets including a synthetic Gaussian Mixture, MNIST, and Glove (a large-scale dataset of 1.2 million word embeddings in 50 dimensions).
For the Glove dataset:
- Memory Efficiency: A naive approach would require 5.8 terabytes of RAM to store the distance matrix. The authors' algorithm requires less than 0.3 gigabytes (the size of the raw dataset).
- Speedup: A naive matrix-vector query was estimated to take 2.6 days. The authors' algorithm completed the same task in just 3.4 seconds.
- Preprocessing: Preprocessing the 1.2 million points took only 16.8 seconds, compared to the impossible task of building the full matrix for the naive version.
Limitations and Future Work
While the algorithms are linear in $n$, some (like the polynomial expansion for $\ell_p$) have an exponential dependence on $p$ or $d$. This makes them less suitable for very high-dimensional data with complex distance functions. Additionally, the techniques work best for functions that can be transformed into a "linear structure." Extending this to more exotic, non-linear kernels remains an open challenge.
Finally, while the authors provide exact algorithms for $\ell_1$ and even $\ell_p$, many other metrics still require approximation to achieve sub-quadratic runtimes. Refining these approximations for better accuracy-speed tradeoffs is a promising path forward.
Summary updated