In many domains of machine learning—from clustering and optimal transport to graph analysis and sequence alignment—the fundamental operation is the comparison of every data point to every other data point. This results in a "pairwise matrix" (affinity, distance, or cost) that captures the global structure of the data.
However, these matrices encounter a hard physical limit known as the quadratic memory bottleneck. Because the number of entries in an $N \times N$ matrix grows with the square of the number of samples ($O(N^2)$), a dataset of just one million points requires a trillion-entry matrix. Storing such a matrix in 32-bit precision would require 4 terabytes of RAM, far exceeding the capacity of modern GPUs and standard workstations.
The Quadratic Wall in Relational Learning
The necessity of storing full dissimilarity or affinity matrices is a recurring theme across diverse research areas. In unsupervised learning, Linli Xu and Dale Schuurmans noted that using equivalence matrices to represent data partitions creates a scalability barrier for large-scale applications Unsupervised and Semi-Supervised Multi-Class Support Vector Machines. Similarly, in computer vision, the SGPN framework for 3D point cloud segmentation is restricted by an $N \times N$ similarity matrix that limits the density of point clouds the network can process in a single pass SGPN: Similarity Group Proposal Network for 3D Point Cloud Instance Segmentation.
This bottleneck isn't just a matter of "waiting longer" for a computation to finish; it is a memory exhaustion event that prevents the algorithm from running at all. As Ehsan Elhamifar and S. Shankar Sastry demonstrate with their DS3 framework, even when computational complexity is linear, the quadratic memory requirement for the dissimilarity matrix itself remains the primary constraint for massive datasets Dissimilarity-Based Sparse Subset Selection.
Symbolic Matrices and Lazy Evaluation
One of the most effective ways to bypass the quadratic wall is to stop treating the matrix as a static block of memory and start treating it as a dynamic computation. This is the core intuition behind symbolic matrices.
Instead of pre-calculating and storing all $N^2$ values, researchers like Jean Feydy and Michael M. Bronstein developed the KeOps library Fast geometric learning with symbolic matrices. KeOps performs "lazy evaluation," where matrix entries are computed on-the-fly during the reduction step (like a sum or a minimum). By fusing the distance calculation directly with the reduction kernel in CUDA, the software eliminates the need to store the intermediate $N \times N$ matrix entirely, reducing memory overhead from $O(N^2)$ to $O(N)$.
Low-Rank and Sparse Approximations
When the full matrix cannot be avoided, researchers look for ways to compress it without losing the underlying signal. This often involves exploiting the fact that real-world data usually lives on a low-dimensional manifold, meaning the $N \times N$ matrix is highly redundant.
- Low-Rank Couplings: In Optimal Transport, Meyer Scetbon and Marco Cuturi introduced methods to compute Gromov-Wasserstein distances using low-rank couplings. This allows for the alignment of massive datasets (like brain tractograms) that would otherwise cause memory exhaustion Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs.
- Sparsification: Algorithms like FINCH (First Neighbor Clustering Hierarchy) by M. Saquib Sarfraz avoid the full matrix by looking only at the "first neighbor" of every data point. This sparse approach discovers natural groupings with extreme speed, scaling to millions of samples where traditional dense methods fail Efficient Parameter-Free Clustering Using First Neighbor Relations.
Vector-Based and Incremental Processing
Another strategy involves changing the data structure of the algorithm itself. For example, in time-series analysis, the IncDTW package transforms Dynamic Time Warping—traditionally an $O(N^2)$ operation—into a vector-based approach. By calculating distances incrementally, it reduces space complexity to linear ($O(N)$), enabling the processing of live data streams IncDTW: An R Package for Incremental Calculation of Dynamic Time Warping.
Similarly, "centerless" clustering frameworks like FKMWC reformulate the clustering objective to rely on manifold learning rather than explicit centroid-to-point distance matrices, aiming to mitigate the scalability bottlenecks inherent in traditional fuzzy k-means Fuzzy K-Means Clustering without Cluster Centroids.
By moving away from dense, static matrix representations toward symbolic, low-rank, or sparse alternatives, this research direction enables the application of sophisticated relational algorithms to the "web-scale" datasets common in modern machine learning.