A Practical Randomized CP Tensor Decomposition

Abstract

The CANDECOMP/PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdetermined linear least squares problems. We extend randomized least squares methods to tensors and show the workload of CP-ALS can be drastically reduced without a sacrifice in quality. We introduce techniques for efficiently preprocessing, sampling, and computing randomized least squares on a dense tensor of arbitrary order, as well as an efficient sampling-based technique for checking the stopping condition. We also show more generally that the Khatri-Rao product (used within the CP-ALS iteration) produces conditions favorable for direct sampling. In numerical results, we see improvements in speed, reductions in memory requirements, and robustness with respect to initialization.

References in corpus (1)

• Sketching as a Tool for Numerical Linear Algebra

Cited by in corpus (18)

• Stochastic Gradients for Large-Scale Tensor Decomposition
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction
• Tensor methods for the Boltzmann-BGK equation
• A literature survey of matrix methods for data science
• Faster Johnson-Lindenstrauss Transforms via Kronecker Products
• Guarantees for the Kronecker Fast Johnson-Lindenstrauss Transform Using a Coherence and Sampling Argument
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• Efficient construction of canonical polyadic approximations of tensor networks
• Fast Randomized Matrix and Tensor Interpolative Decomposition Using CountSketch
• On Koopman Mode Decomposition and Tensor Component Analysis
• Probabilistic methods for approximate archetypal analysis
• TUCKET: A Tensor Time Series Data Structure for Efficient and Accurate Factor Analysis over Time Ranges
• Distributed-Memory Randomized Algorithms for Sparse Tensor CP Decomposition
• Modewise Johnson-Lindenstrauss Embeddings for Nuclear Many-Body Theory
• COVID-19 Multidimensional Kaggle Literature Organization
• Accelerating jackknife resampling for the Canonical Polyadic Decomposition