A literature survey of matrix methods for data science

Martin Stoll

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.

Introduction

Data science often deals with massive datasets represented as matrices ($A \in \mathbb{R}^{n,m}$) or high-dimensional tensors. As datasets grow into the millions of entries, standard algorithms like the full Singular Value Decomposition (SVD) become prohibitively expensive, scaling at $O(n^3)$. Furthermore, classical methods often lack interpretability; for instance, Principal Component Analysis (PCA) can produce dense results with negative values that are difficult to map back to physical features like word counts or pixel intensities. This survey bridges the gap between classical matrix computations and modern data challenges, illustrating how Numerical Linear Algebra (NLA) serves as the engine for large-scale machine learning.

Interpretable and Scalable Factorizations

Beyond standard SVD and QR decompositions, modern data science relies on factorizations that preserve the "nature" of the data. Non-negative Matrix Factorization (NMF) and CUR decompositions are primary examples. Unlike SVD, which creates abstract singular vectors, CUR uses actual rows and columns from the original dataset, making the results human-readable and preserving sparsity.

Comparison of SVD and CUR vectors. While SVD vectors are orthogonal, CUR vectors align with actual data columns, enhancing interpretability.

To handle the computational complexity of "Big Data," Randomized Numerical Linear Algebra (RandNLA) has emerged as a critical frontier. By using "skinny" random matrices to "sketch" a massive matrix, researchers can compute approximate SVDs or least-squares solutions at a fraction of the traditional cost, backed by theoretical guarantees like the Johnson-Lindenstrauss lemma.

Graph and Kernel Methods

When data is not linearly separable, changing the representation becomes essential. The Graph Laplacian is a matrix that encodes relationships between data points. By analyzing the "Fiedler vector" (the first non-zero eigenvector), spectral clustering can identify complex patterns in data manifolds where traditional methods like k-means fail.

Spectral clustering on the Two-Moons dataset, demonstrating the ability of graph-based methods to identify non-linearly separable clusters.

High-Dimensional Problems and Matrix Functions

To combat the "curse of dimensionality," the survey explores tensor formats such as CP, Tucker, and Tensor-train. These formats compress $d$-dimensional data into manageable "cores," allowing for the storage and processing of data that would otherwise exceed physical memory limits. Additionally, evaluating matrix functions $f(A)$, such as the matrix exponential for network centrality, is made feasible through Krylov subspace methods, which avoid the need to compute the function for the entire matrix.

Key Results and Future Directions

The synthesis of these methods has led to significant efficiency gains. For example, the Nyström scheme and RandNLA have reduced the bottleneck of kernel-based learning from $O(n^3)$ to $O(nk^2)$. NLA is also increasingly used to "prune" neural networks, using SVD to compress weight matrices for mobile deployment.

However, challenges remain. "Fully connected" graphs still pose difficulties for matrix-vector products, and the use of second-order information (the Hessian matrix) in deep learning is still in its infancy due to the massive scale of the required NLA. Future research is likely to focus on these areas, as well as the analysis of multilayer or "multiplex" networks.

Summary updated

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},
}
Figure