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.
Introduction
In machine learning, computational biology, and manifold learning, the distance matrix is a ubiquitous structure. For a dataset $X$ containing $n$ points, the distance matrix $A$ is an $n \times n$ table where each entry $A_{i,j}$ represents the distance between point $i$ and point $j$ under a specific metric $f$. While these matrices are essential for downstream tasks like dimensionality reduction and spectral clustering, they present a massive scalability challenge: the $n^2$ entries grow quadratically with the number of points. For large-scale datasets, such as word embeddings with millions of entries, storing or even explicitly computing the matrix becomes mathematically and computationally prohibitive.
This paper addresses this bottleneck by asking whether fundamental linear algebraic operations—such as matrix-vector multiplication ($Az$) and low-rank approximations—can be performed without ever explicitly constructing the full $n \times n$ matrix. By exploiting the underlying geometric structure of common distance metrics, the authors demonstrate that it is possible to bypass the traditional $\Omega(n^2)$ complexity.
Methodology: The Matrix-Free Approach
The authors utilize a "matrix-vector query model," treating the distance matrix as an operator rather than a static data structure. Several key techniques enable this near-linear performance:
1. Linearization of Even Powers
For squared Euclidean distance ($\ell_2^2$) and other even $\ell_p$ norms, the distance formula can be expanded into a polynomial. This expansion allows the points $x_i$ and $x_j$ to be "decoupled." Consequently, a massive sum over $n^2$ entries can be refactored into a few independent sums that can be computed in $O(nd)$ time, where $d$ is the dimensionality of the points.
2. Sorting and Prefix Sums for $\ell_1$
The $\ell_1$ metric, which involves absolute values $|x_i - x_j|$, does not linearize as easily as squared distances. To solve this, the authors employ a sorting-based approach. By sorting coordinates and using prefix sums, they can compute the "left side" and "right side" of the absolute value separately. This technique reduces the complexity of a matrix-vector product to $O(nd)$ (or $O(nd \log n)$ depending on the implementation), a significant improvement over the naive quadratic approach.
3. Metric Compression Trees
For the construction of approximate distance matrices, the authors introduce specialized tree structures. These structures group points geometrically, allowing for the reuse of distance calculations. This approach is shown to be faster than the standard runtime bounds implied by the Johnson-Lindenstrauss (JL) lemma, which is the traditional "gold standard" for dimensionality reduction.
Theoretical Boundaries: The $\ell_1$ vs. $\ell_\infty$ Gap
A major theoretical contribution of this work is the identification of a sharp complexity divide between metrics. While $\ell_1$ and $\ell_2$ allow for near-linear time operations, the authors use the Strong Exponential Time Hypothesis (SETH) to prove that the $\ell_\infty$ (Chebyshev) distance is fundamentally harder. Specifically, they establish an $\Omega(n^2)$ lower bound for exact matrix-vector products in the $\ell_\infty$ case, suggesting that quadratic time is likely unavoidable for this metric.
Empirical Results and Applications
The theoretical speedups were validated across several datasets, including synthetic Gaussian Mixtures, MNIST, and the Glove word embedding dataset (1.2 million points, 50 dimensions).
- Computational Efficiency: On the Glove dataset, a naive matrix-vector product was estimated to require 2.6 days of computation. Using the authors' optimized $\ell_1$ algorithm, the same task was completed in just 3.4 seconds.
- Scaling: Preprocessing and query times for $\ell_1$ and $\ell_2$ were confirmed to scale linearly with $n$, matching the theoretical $O(nd)$ predictions.
- Downstream Primitives: These fast matrix-vector products enable the fastest known algorithms for relative-error low-rank approximations for $\ell_1$ and $\ell_2^2$ matrices, as well as additive-error approximations for $\ell_2$ matrices.
Conclusion and Future Work
This research demonstrates that the geometric structure of distance matrices can be leveraged to achieve massive algorithmic speedups. By shifting from explicit matrix representation to implicit geometric operators, the authors enable large-scale linear algebra that was previously impossible.
Future research directions include extending these "matrix-free" techniques to other kernel matrices, such as Gaussian kernels, and investigating whether subquadratic approximations for the $\ell_\infty$ metric can be further improved to bridge the gap between theoretical hardness and practical utility.
Summary updated