An Out of Memory tSVD for Big-Data Factorization
Open Access
- 8 June 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 107749-107759
Abstract
Singular value decomposition (SVD) is a matrix factorization method widely used for dimension reduction, data analytics, information retrieval, and unsupervised learning. In general, only singular values of SVD are needed for most big-data applications. Methods such as tensor networks require an accurate computation of a substantial number of singular vectors, which can be accomplished through truncated SVD (tSVD). Additionally, many real-world datasets are too big to fit into the available memory, which mandates the development of out of memory algorithms that assume that most of the data resides on an external disk during the entire computation. These algorithms reduce communication to disk and hide part of the communication by overlapping it with communication on blocks of work. Here, building upon previous works on SVD for dense matrices, we present a method for computation of a predetermined number, K, of SVD singular vectors, and the corresponding K singular values, of a matrix that cannot fit in the memory. Our out of memory tSVD can be used for tensor networks algorithms. We describe ways for reducing the communication during the computation of the left and right reflectors, needed to compute the singular vectors, and introduce a method for estimating the block-sizes needed to hide the communication on parallel file systems.Keywords
Funding Information
- U.S. Department of Energy National Nuclear Security Administration (DE-AC52-06NA25396)
- LANL Laboratory Directed Research and Development (20190020DR)
- U.S. Department of Energy National Nuclear Security Administration (89233218CNA000001)
- Los Alamos National Laboratory Institutional Computing Program
This publication has 21 references indexed in Scilit:
- Distributed non-negative matrix factorization with determination of the number of latent featuresThe Journal of Supercomputing, 2020
- A User-Friendly Hybrid Sparse Matrix Class in C++2018
- Tensor Networks for Dimensionality Reduction, Big Data and Deep Learning2017
- A Framework for Out of Memory SVD Algorithms2017
- High-performance bidiagonal reduction using tile algorithms on homogeneous multicore architecturesACM Transactions on Mathematical Software, 2013
- A Comprehensive Study of Task Coalescing for Selecting Parallelism Granularity in a Two-Stage Bidiagonal Reduction2012
- Tensor-Train DecompositionSIAM Journal on Scientific Computing, 2011
- Tensor Decompositions and ApplicationsSIAM Review, 2009
- The design and implementation of the parallel out-of-core ScaLAPACK LU, QR, and Cholesky factorization routinesConcurrency: Practice and Experience, 2000
- Positive matrix factorization: A non‐negative factor model with optimal utilization of error estimates of data valuesEnvironmetrics, 1994