Scalable Methods for Nonnegative Matrix Factorizations of Near-separable Tall-and-skinny Matrices

Austin R. Benson, Jason D. Lee, Bartek Rajwa, David F. Gleich

Abstract

Nonnegative Matrix Factorization (NMF) is a critical tool for identifying interpretable, parts-based representations in large-scale datasets. However, standard NMF is computationally intensive and NP-hard. This paper presents a highly scalable approach specifically designed for "tall-and-skinny" matrices—datasets with billions of rows but relatively few columns. By combining the separability assumption with orthogonal transformations (such as QR decomposition), the proposed method reduces massive terabyte-scale problems into small $n \times n$ computations that can be solved in a single pass over the data. We demonstrate the effectiveness of this approach on synthetic data, heat transfer simulations, and flow cytometry datasets, processing up to 2 TB of data.

Introduction

In modern data science, Nonnegative Matrix Factorization (NMF) is prized for its ability to decompose complex data into meaningful components, such as topics in text or features in images. Despite its utility, the computational cost of NMF becomes prohibitive as datasets scale to the terabyte level.

This research addresses the challenge of performing NMF on tall-and-skinny matrices, where the number of observations ($m$) vastly exceeds the number of features ($n$). Such data structures are prevalent in scientific fields like bioinformatics and physical simulations. The authors leverage the separability assumption, which posits that the data can be reconstructed using a subset of its own columns as a basis. While this assumption is restrictive, it transforms NMF into a geometrically tractable problem of identifying the "extreme" columns of the data's convex hull.

Comparison of columns selected by SPA, XRAY, and GP against the ground truth (Generation).

Methodology: Dimension Reduction via Orthogonal Transformation

The core innovation of this work is a dimension reduction technique that preserves the geometric structure necessary for separable NMF while drastically reducing the data volume.

  1. Orthogonal Transformation: The authors demonstrate that applying an orthogonal matrix (derived from a QR or SVD factorization) to the data preserves the extreme columns required for separable NMF. Because orthogonal transformations are essentially rotations or reflections, they do not alter the relative geometric relationships between columns.
  2. Tall-and-Skinny QR (TSQR): By performing a TSQR factorization, an $m \times n$ matrix (with billions of rows) is reduced to a small $n \times n$ upper triangular matrix $R$.
  3. Small-Scale NMF: Once the data is reduced to the $n \times n$ matrix $R$, standard separable NMF algorithms—such as the Successive Projection Algorithm (SPA) or XRAY—can be executed almost instantaneously in main memory.
  4. Scalability and MapReduce: This workflow requires only a single pass over the original data. The authors implemented the TSQR kernel using MapReduce (Hadoop), making it highly suitable for distributed clusters and streaming data architectures.

Experimental Evaluation

The methods were evaluated using three distinct datasets to test scalability and accuracy:

  • Synthetic Data: A 286 GB dataset (200 million rows, 200 columns) used to verify ground-truth recovery.
  • Heat Transfer Simulations: A massive 2 TB dataset containing 4.9 billion rows, representing temperature simulations in steel blocks.
  • Flow Cytometry (FC): A 345 GB dataset used to identify redundancies in biological markers.
Relative error of different NMF algorithms (SPA, XRAY, GP) as a function of separation rank.

Key Results and Insights

Performance and Scalability

The proposed framework successfully processed a 2 TB dataset, representing one of the largest separable NMF computations reported at the time. By offloading the heavy computational lifting to the highly optimized TSQR kernel, the algorithm minimizes communication overhead in distributed environments. As shown in the experimental results, the XRAY algorithm consistently provided lower relative errors compared to SPA and GP across various separation ranks.

Scientific Interpretability

Beyond computational efficiency, the method yielded significant scientific insights. In the heat transfer application, NMF revealed that complex simulations could be represented as conic combinations of just two "extreme" simulations, providing a simplified physical model of heat propagation. In flow cytometry, the algorithm identified redundant markers, suggesting that future experiments could be streamlined without losing critical phenotypic information.

Conclusion and Future Work

This work provides a robust framework for scaling NMF to massive tall-and-skinny datasets. By reducing the problem to an $n \times n$ core, the authors enable the use of sophisticated NMF algorithms on datasets that were previously inaccessible. While the method is limited to "skinny" matrices (where $n$ fits in memory) and relies on the near-separability of data, it offers a powerful tool for large-scale scientific discovery. Future research may explore the application of this framework to a wider variety of NMF algorithms and even more diverse high-dimensional datasets.

Summary updated

Abstract

Numerous algorithms are used for nonnegative matrix factorization under the assumption that the matrix is nearly separable. In this paper, we show how to make these algorithms scalable for data matrices that have many more rows than columns, so-called tall-and-skinny matrices." One key component to these improved methods is an orthogonal matrix transformation that preserves the separability of the NMF problem. Our final methods need to read the data matrix only once and are suitable for streaming, multi-core, and MapReduce architectures. We demonstrate the efficacy of these algorithms on terabyte-sized matrices from scientific computing and bioinformatics."
BibTeX
@inproceedings{benson2014scalable,
  author = {Austin R. Benson and Jason D. Lee and Bartek Rajwa and David F. Gleich},
  title = {{Scalable Methods for Nonnegative Matrix Factorizations of Near-separable Tall-and-skinny Matrices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=Bybr-DWObB},
}
Figure