The Structural Complexity of Matrix-Vector Multiplication

Emile Timothy Anand, Jan van den Brand, Rose McCarty

Introduction

Matrix-vector multiplication ($Mv$) is a foundational operation in modern computing, serving as the inner loop for tasks ranging from neural network training to massive optimization problems. However, a persistent disconnect exists between theoretical bounds and practical performance. Theoretically, multiplying an $n \times n$ matrix by a vector requires $O(n^2)$ time in the worst and average cases, barring impractical "galactic" algorithms. This limitation forms the basis of the Online Matrix-Vector (OMv) conjecture, which posits quadratic time as a fundamental floor. Yet, in practice, engineers routinely deploy heuristics that execute significantly faster on real-world data.

This paper bridges this gap by demonstrating that real-world data is rarely random; it possesses inherent structure. By parameterizing complexity using the Vapnik-Chervonenkis (VC) dimension—a classic measure from machine learning theory—the authors provide a rigorous subquadratic algorithm for structured data, explaining why practical algorithms frequently outperform worst-case theoretical predictions.

Methodology: Exploiting Structure via VC-Dimension

Traditionally used to measure the capacity of a hypothesis class, the VC-dimension is repurposed here to quantify row redundancy within a matrix. If a matrix exhibits a low VC-dimension, its rows (or columns) share a specific geometric similarity.

Differential Compression

To exploit this similarity, the authors introduce a differential compression algorithm:

  1. Preprocessing: The algorithm constructs a Minimum Spanning Tree (MST) where vertices are matrix rows and edge weights represent the Hamming distance (the number of differing entries) between them.
  2. Compression: Instead of storing each row explicitly, the system stores the root row and the differences ($\Delta$) between each subsequent row and its parent in the MST.
  3. Querying: To compute the matrix-vector product, the algorithm traverses this tree. Because the total "weight" (number of non-zero $\Delta$ entries) of the MST is small for matrices with low VC-dimension, the multiplication process is vastly accelerated.

Handling Noise and Non-Boolean Data

Recognizing that real-world data is rarely pristine, the authors introduce the concept of "Corrupted VC-dimension" to accommodate matrices with noisy entries while preserving subquadratic performance. Furthermore, they extend their framework to non-Boolean matrices utilizing the Pollard pseudodimension.

Empirical Validation

The theoretical framework was validated using numerical simulations designed to test the relationship between VC-dimension ($d$) and runtime:

  • Synthetic Halfspace Matrices: The authors generated $n \times n$ binary matrices ($n=4096$) derived from linear classifiers in $d$-dimensional space, guaranteeing a precise VC-dimension of $d$.
  • Real-World Context: The study aligns with existing literature demonstrating that real-world datasets, such as protein interaction networks or Internet topologies, typically exhibit remarkably low VC-dimensions (often between 3 and 8).

In these simulations, the MST-based algorithm significantly outperformed standard optimized libraries as $d$ remained small, corroborating the theoretical scaling.

Key Results and Implications

The primary theoretical breakthrough is a drastic reduction in query time. For an $n \times n$ Boolean matrix with VC-dimension $d$, the query time drops from $O(n^2)$ to $\tilde{O}(n^{2-1/d})$ after $\tilde{O}(n^2)$ preprocessing. For a VC-dimension of 2, this yields a query time of roughly $O(n^{1.5})$.

Bypassing the OMv Conjecture in Dynamic Graphs

The OMv conjecture has long been a pillar of fine-grained complexity, used to prove conditional lower bounds for numerous dynamic graph problems. By proving that low VC-dimension guarantees the existence of a low-weight spanning tree, this paper demonstrates that these hardness results can be bypassed for structured graphs.

The authors provide the first subquadratic upper bounds in the high-accuracy regime for several dynamic graph problems subject to node insertions and deletions, including:

  • Dynamic Laplacian Solvers: Maintaining solutions to $Lx=b$ as the graph evolves.
  • Effective Resistance: Estimating the electrical distance between nodes.
  • Shortest Paths and Triangle Detection: Efficiently maintaining path lengths and identifying 3-cycles.

Limitations and Future Directions

While groundbreaking, the approach has a few limitations that present avenues for future research:

  • Non-Boolean Scaling: For non-Boolean matrices, the runtime currently scales linearly with $T$ (the number of unique values per column). The authors hypothesize this could be optimized to a logarithmic dependence ($\log T$).
  • Optimality: It remains an open question whether the $\tilde{O}(n^{2-1/d})$ bound is strictly optimal, leaving room for potentially faster algorithms exploiting low VC-dimension.
  • Preprocessing Overhead: The $\tilde{O}(n^2)$ preprocessing time is acceptable for static matrices subject to numerous queries, but reducing this overhead would enhance practicality for highly dynamic datasets.

Summary updated

Abstract

We consider the problem of preprocessing an $n\times n$ matrix $\mathbf{M}$, and supporting queries that, for any vector $v$, returns the matrix-vector product $\mathbf{M} v$. This problem has been extensively studied in both theory and practice: on one side, practitioners have developed algorithms that are highly efficient in practice, whereas on the other side, theoreticians have proven that the problem cannot be solved faster than naive multiplication in the worst-case. This lower bound holds even in the average-case, implying that existing average-case analyses cannot explain this gap between theory and practice. Hence, we study the problem for \emph{structured} matrices. We show that for $n\times n$ Boolean matrices of VC-dimension $d$, the matrix-vector multiplication problem can be solved with $\smash{\tilde{O}(n^2)}$ preprocessing and $\smash{\tilde O(n^{2-1/d})}$ query time. Given the low constant VC-dimensions observed in most real-world data, our results posit an explanation for why the problem can be solved so much faster in practice. Furthermore, we show how to extend this result to the non-Boolean setting with the Pollard pseudodimension. Our results yield the first non-trivial upper bounds for many applications. In previous works, the online matrix-vector (OMv) hypothesis (conjecturing that quadratic time is needed per query, even over the boolean semi-ring) was used to prove many conditional lower bounds, showing that it is impossible to compute and maintain high-accuracy estimates for effective resistance, Laplacian solvers, shortest paths, and triangle detection in graphs subject to node insertions and deletions in subquadratic time. Yet, via a reduction to our matrix-vector-multiplication result, we show we can maintain these problems efficiently if the input is structured, providing the first subquadratic upper bounds in the high-accuracy regime.
BibTeX
@inproceedings{anand2025structural,
  author = {Emile Timothy Anand and Jan van den Brand and Rose McCarty},
  title = {{The Structural Complexity of Matrix-Vector Multiplication}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=tGLZj8GWx3},
}
Figure