A literature survey of matrix methods for data science

Martin Stoll

This literature survey by Martin Stoll provides a comprehensive map of how Numerical Linear Algebra (NLA)—the "old guard" of scientific computing—has become the indispensable engine driving modern data science. While many view data science through the lens of high-level machine learning frameworks, this paper pulls back the curtain to show that the field’s success relies on the elegant manipulation of matrices and tensors.

TL;DR

This survey bridges the gap between classical matrix computations and modern data challenges, illustrating how factorizations, graph-based representations, and randomized algorithms enable large-scale machine learning. It highlights that while "Big Data" is the fuel, Numerical Linear Algebra is the high-performance engine that makes processing that data computationally feasible and interpretable.

What Problem Does This Paper Address?

Data science often deals with massive datasets represented as matrices ($A \in \mathbb{R}^{n,m}$) or high-dimensional tensors. The core challenge is twofold:

  1. Computational Complexity: Standard algorithms that work on small matrices (like a full SVD) become prohibitively expensive ($O(n^3)$) as $n$ grows into the millions.
  2. Interpretability: Classical methods like Principal Component Analysis (PCA) often produce "dense" results with negative values, which are difficult to map back to real-world features (like word counts or pixel intensities).

The paper addresses these gaps by surveying techniques that trade off absolute precision for speed (randomization), preserve the "nature" of the data (interpretable factorizations), or change the data's representation entirely (kernels and graphs) to make patterns easier to spot.

Methods

The paper categorizes the "toolbox" of data science into several key algorithmic families:

  • Interpretable Factorizations: Beyond the standard SVD and QR, the author highlights CUR decompositions and Non-negative Matrix Factorization (NMF). Unlike SVD, which creates abstract "singular vectors," CUR uses actual rows and columns from the original dataset, making the results human-readable.
  • Graph and Kernel Methods: The paper details the Graph Laplacian, a matrix that encodes the relationships between data points. By analyzing the "Fiedler vector" (the first non-zero eigenvector), researchers can perform spectral clustering on data that isn't linearly separable.
  • Randomized Numerical Linear Algebra (RandNLA): This is a relatively new frontier where "skinny" random matrices are used to "sketch" a massive matrix. This allows for approximate SVDs or least-squares solutions at a fraction of the traditional cost.
  • Matrix Functions: The author discusses evaluating $f(A)$ (like the matrix exponential) to calculate network centrality or solve Gaussian processes, often using Krylov subspace methods to avoid computing the function for the entire matrix.
  • Tensor Decompositions: To break the "curse of dimensionality," the paper explores CP, Tucker, and Tensor-train formats, which compress $d$-dimensional data into manageable "cores."

Datasets

As a literature survey, the paper does not introduce a new benchmark. However, it references several iconic datasets and problems used to validate these NLA methods:

  • The Netflix Prize Dataset: Used to illustrate the power of matrix completion and recommender systems.
  • Two-Moons Dataset: A classic synthetic dataset used to show why spectral clustering (via the Graph Laplacian) succeeds where traditional k-means fails.
  • Spatial and Time-Series Data: Mentioned as the primary sources for the matrices encountered in environmental and economic applications.

Key Insights and Ideas

  • The "Aha" of Interpretability: The author points out that a "best" mathematical approximation (like SVD) isn't always the "best" for a practitioner. If your data is non-negative (like image pixels), your factorization should be too (NMF), even if it's slightly less accurate.
  • The Fiedler Vector Magic: In spectral clustering, the sign of the entries in the Fiedler vector acts as a natural classifier, effectively "cutting" a graph into its most distinct components.
  • Randomization is Rigorous: One of the most surprising insights is that random projections aren't just "guesses"—they come with strong theoretical guarantees (like the Johnson-Lindenstrauss lemma) that ensure the "sketch" preserves the essential geometry of the original data.
  • NLA in Deep Learning: The paper notes that NLA isn't just for preprocessing; it's being used to "prune" neural networks by using SVD to compress weight matrices, making models small enough to run on mobile devices.

Key Results

The survey synthesizes decades of research into a few qualitative conclusions:

  • Efficiency Gains: Methods like the Nyström scheme and RandNLA have reduced the bottleneck of kernel-based learning from $O(n^3)$ to $O(nk^2)$, where $k$ is a small rank.
  • Geometric Awareness: Spectral methods are shown to be far superior for "manifold learning," where data lies on a curved surface rather than in flat clusters.
  • Dimensionality Compression: Tensor-train formats are highlighted as a breakthrough for high-dimensional PDEs and machine learning, allowing for the storage of data that would otherwise require more RAM than exists on Earth.

Limitations and Future Work

  • The Curse of Connectivity: While NLA works well for sparse graphs, "fully connected" graphs (where every data point relates to every other) still pose a massive challenge for matrix-vector products.
  • Second-Order Deep Learning: Most deep learning uses simple gradient descent. The author suggests that using the Hessian matrix (second-order info) could revolutionize training speed, but the NLA required to handle such a massive matrix is still in its infancy.
  • Multilayer Networks: The paper identifies "multiplex" or multilayer graphs (where nodes have different types of connections) as a primary area for future NLA research.

Summary updated

Abstract

Abstract Efficient numerical linear algebra is a core ingredient in many applications across almost all scientific and industrial disciplines. With this survey we want to illustrate that numerical linear algebra has played and is playing a crucial role in enabling and improving data science computations with many new developments being fueled by the availability of data and computing resources. We highlight the role of various different factorizations and the power of changing the representation of the data as well as discussing topics such as randomized algorithms, functions of matrices, and high‐dimensional problems. We briefly touch upon the role of techniques from numerical linear algebra used within deep learning.
BibTeX
@inproceedings{stoll2020literature,
  author = {Martin Stoll},
  title = {{A literature survey of matrix methods for data science}},
  booktitle = {GAMM-Mitteilungen},
  year = {2020},
  doi = {10.1002/gamm.202000013},
}

Loading related content...

Figure