A Practical Randomized CP Tensor Decomposition
From MaRDI portal
Publication:4643335
DOI10.1137/17M1112303zbMATH Open1444.65016arXiv1701.06600OpenAlexW3102869303WikidataQ129774144 ScholiaQ129774144MaRDI QIDQ4643335FDOQ4643335
Authors: Casey Battaglino, Grey Ballard, Tamara G. Kolda 
Publication date: 24 May 2018
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1701.06600
Recommendations
- scientific article; zbMATH DE number 7410754
- Incremental CP tensor decomposition by alternating minimization method
- Numerical CP decomposition of some difficult tensors
- An efficient randomized fixed-precision algorithm for tensor singular value decomposition
- A randomized algorithm for a tensor-based generalization of the singular value decomposition
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- Efficient Tensor Decompositions
- Randomized algorithms for the approximations of Tucker and the tensor train decompositions
- On the optimization landscape of tensor decompositions
- Randomized algorithms for the low multilinear rank approximations of tensors
Multilinear algebra, tensor calculus (15A69) Numerical linear algebra (65F99) Randomized algorithms (68W20)
Cites Work
- Efficient MATLAB Computations with Sparse and Factored Tensors
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Extensions of Lipschitz mappings into a Hilbert space
- Tensor Decompositions and Applications
- Exact matrix completion via convex optimization
- Tensor-train decomposition
- Algorithm 862
- Faster least squares approximation
- Uncertainty principles and ideal atomic decomposition
- Title not available (Why is that?)
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- A fast randomized algorithm for overdetermined linear least-squares regression
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- A comparison of algorithms for fitting the PARAFAC model
- Enhanced Line Search: A Novel Method to Accelerate PARAFAC
- A least-squares method for sparse low rank approximation of multivariate functions
- A continuous analogue of the tensor-train decomposition
- Tensor Decomposition for Signal Processing and Machine Learning
- Sketching as a tool for numerical linear algebra
- Randomized alternating least squares for canonical tensor decompositions: application to a PDE with random data
Cited In (57)
- Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
- Two-sided randomized algorithms for approximate \(K\)-term t-SVD
- A fast algorithm for rank-\((L, M, N)\) block term decomposition of multi-dimensional data
- Tracking tensor ring decompositions of streaming tensors
- Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
- Accelerated doubly stochastic gradient descent for tensor CP decomposition
- A random sampling algorithm for fully-connected tensor network decomposition with applications
- Sparse low rank approximation of potential energy surfaces with applications in estimation of anharmonic zero point energies and frequencies
- The numerical approximation of nonlinear functionals and functional differential equations
- An ATLD-ALS method for the trilinear decomposition of large third-order tensors
- An efficient algorithm for computing the approximate t-URV and its applications
- Stochastic gradients for large-scale tensor decomposition
- A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes
- Inertial accelerated SGD algorithms for solving large-scale lower-rank tensor CP decomposition problems
- Title not available (Why is that?)
- Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC
- Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and Tucker decompositions
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Parallel Candecomp/Parafac decomposition of sparse tensors using dimension trees
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- The Hanson-Wright inequality for random tensors
- Quantized CP approximation and sparse tensor interpolation of function-generated data.
- A trust-region-based alternating least-squares algorithm for tensor decompositions
- Real eigenstructure of regular simplex tensors
- Randomized tensor decomposition for large-scale data assimilation problems for carbon dioxide sequestration
- On Koopman mode decomposition and tensor component analysis
- Fast randomized matrix and tensor interpolative decomposition using countsketch
- Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
- Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
- Multiscale co-clustering for tensor data based on canonical polyadic decomposition and slice-wise factorization
- Tensor methods for the Boltzmann-BGK equation
- Parallel Randomized Tucker Decomposition Algorithms
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- Provable stochastic algorithm for large-scale fully-connected tensor network decomposition
- A literature survey of matrix methods for data science
- Practical leverage-based sampling for low-rank tensor decomposition
- A fast sketching-based algorithm for rank-\((L,L,1)\) block term decomposition
- Low-rank Tucker approximation of a tensor from streaming data
- Total variation based tensor decomposition for multi-dimensional data with time dimension.
- Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking
- Structured random sketching for PDE inverse problems
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
- Randomized algorithms for the low multilinear rank approximations of tensors
- A polynomial-time algorithm for computing low CP-rank decompositions
- Johnson–Lindenstrauss Embeddings with Kronecker Structure
- Time-aware tensor decomposition for sparse tensors
- Incremental CP tensor decomposition by alternating minimization method
- Numerical CP decomposition of some difficult tensors
- Tensor-CUR Decompositions for Tensor-Based Data
- A Higher-Order Generalized Singular Value Decomposition for Rank-Deficient Matrices
- Tensor-structured sketching for constrained least squares
- Supervised multiway factorization
- Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
- Randomized tensor wheel decomposition
- Parallel tensor methods for high-dimensional linear PDEs
- A block-randomized stochastic method with importance sampling for CP tensor decomposition
Uses Software
This page was built for publication: A Practical Randomized CP Tensor Decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4643335)
