Faster Linear Algebra for Distance Matrices

Piotr Indyk, Sandeep Silwal

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.

Table 1: Preprocessing and query times for various distance functions.

Key Results and Downstream Applications

The theoretical speedups translate to massive improvements for downstream tasks like low-rank approximations and matrix multiplication.

Table 2: Runtimes for downstream linear algebra problems compared to prior work.

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

Abstract

The distance matrix of a dataset $X$ of $n$ points with respect to a distance function $f$ represents all pairwise distances between points in $X$ induced by $f$. Due to their wide applicability, distance matrices and related families of matrices have been the focus of many recent algorithmic works. We continue this line of research and take a broad view of algorithm design for distance matrices with the goal of designing fast algorithms, which are specifically tailored for distance matrices, for fundamental linear algebraic primitives. Our results include efficient algorithms for computing matrix-vector products for a wide class of distance matrices, such as the $\ell_1$ metric for which we get a linear runtime, as well as an $\Omega(n^2)$ lower bound for any algorithm which computes a matrix-vector product for the $\ell_{\infty}$ case, showing a separation between the $\ell_1$ and the $\ell_{\infty}$ metrics. Our upper bound results in conjunction with recent works on the matrix-vector query model have many further downstream applications, including the fastest algorithm for computing a relative error low-rank approximation for the distance matrix induced by $\ell_1$ and $\ell_2^2$ functions and the fastest algorithm for computing an additive error low-rank approximation for the $\ell_2$ metric, in addition to applications for fast matrix multiplication among others. We also give algorithms for constructing distance matrices and show that one can construct an approximate $\ell_2$ distance matrix in time faster than the bound implied by the Johnson-Lindenstrauss lemma.
BibTeX
@inproceedings{indyk2022faster,
  author = {Piotr Indyk and Sandeep Silwal},
  title = {{Faster Linear Algebra for Distance Matrices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=y--ZUTfbNB},
}
Figure