Final Report: LDRD Project 199986
Abstract
We extended the fundamental capabilities of tensor decomposition to a broader range of problems—handling new data types and larger problems. This has implications for data analysis across a range of applications in sensor monitoring, cybersecurity, treaty verification, signal processing, and more. By identifying latent structure within data, these methods enable anomaly detection, process monitoring, and scientific discovery.
Introduction
Tensor decomposition serves as a cornerstone of unsupervised machine learning, providing a powerful method for identifying hidden patterns within multi-dimensional data. However, as datasets grow in complexity and scale, traditional "black-box" models often fall short. This report summarizes a multi-year effort to modernize tensor decompositions, moving them beyond simple Gaussian assumptions to handle massive, incomplete, and non-Gaussian datasets. By introducing the Generalized Canonical Polyadic (GCP) framework and high-performance software like GenTen, this research enables more transparent and scalable latent structure identification.
The Challenges of Modern Data Analysis
Traditional tensor decomposition methods face three primary hurdles when applied to real-world scenarios:
- Data Heterogeneity: Standard techniques typically assume data follows a Gaussian (normal) distribution. However, real-world data is rarely so uniform. For instance, cybersecurity logs often consist of count data (Poisson distribution), while sensor hits may be binary "yes/no" signals (Bernoulli distribution). Standard methods often fail to extract meaningful patterns from these non-normal distributions.
- Scale and Sparsity: Massive datasets are frequently sparse, meaning they consist mostly of zeros. Processing these at scale on modern supercomputers requires specialized data structures and parallel algorithms that can navigate irregular memory access patterns without sacrificing performance.
- Incompleteness: Missing values are a common reality in field data. Algorithms must be robust enough to "fill in the blanks" (tensor completion) without incurring prohibitive computational costs.
While deep neural networks are often used for similar pattern-recognition tasks, they are frequently criticized as "black boxes." Tensor decompositions offer a more interpretable alternative, providing a transparent structure that remains effective even when data is limited.
Methodology: The GCP Framework and Scalable Optimization
The project’s technical contributions center on four main pillars designed to overcome the limitations of traditional models:
The Generalized Canonical Polyadic (GCP) Framework
The researchers introduced the GCP framework to move beyond the limitations of squared-error minimization. GCP allows for a variety of loss functions tailored to specific statistical distributions. For example, using a Poisson loss function for count data allows the model to respect the discrete nature of the information, leading to more accurate latent structure identification.
Randomized Sampling and Stochasticity
To handle massive sparse tensors, the team developed specialized randomized sampling methods. By utilizing stochastic gradient descent (SGD), the algorithm can estimate gradients using only a fraction of the total data. This approach significantly speeds up the factorization process, making it possible to analyze datasets that were previously computationally untouchable.
High-Performance Computing (HPC) and Data Structures
A significant finding of the project was the validation of the Coordinate (COO) storage format for sparse tensors in HPC environments. While researchers previously believed expensive and complex data structures were necessary for distributed parallelism, this project proved that the simpler COO format is highly viable. This simplifies the engineering requirements for building high-performance tensor tools.
Portable Parallelism with Kokkos
Using the Kokkos programming model, the team developed software that achieves performance portability. This allows the underlying code to run efficiently across diverse architectures—including many-core CPUs and various GPUs—without requiring a complete rewrite for each new hardware generation.
Key Results and Software Impact
The project resulted in a suite of open-source software tools and a significant body of academic literature:
- GenTen & GenTenMPI: These C++ software libraries provide the implementation for GCP tensor decompositions, optimized for many-core, GPU, and distributed memory architectures.
- Tensor Toolbox for MATLAB: The researchers provided significant updates to this industry-standard tool, integrating the new GCP factorization capabilities for the broader research community.
- Spatter Benchmark: The team created Spatter, a new benchmark suite designed to assess memory system performance on sparse and irregular access patterns, effectively acting as a "sparse STREAM" benchmark for the HPC community.
- Academic Impact: The project produced over a dozen publications in top-tier journals and conferences, including SIAM Review and SC, establishing foundational communication lower bounds for tensor operations.
Conclusion and Future Work
While the project successfully modernized tensor decomposition for heterogeneous data, several frontiers remain. The researchers identified specific limitations in current multi-level parallelism models within Kokkos that require further refinement. Additionally, while the foundations for distributed-memory GCP were laid with GenTenMPI, extreme-scale distributed implementation remains an ongoing research area. Future efforts will focus on refining efficient sampling techniques to ensure robustness across an even wider variety of real-world data distributions.
Summary updated