A Practical Randomized CP Tensor Decomposition
From MaRDI portal
Publication:4643335
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.
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
Cites work
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- A comparison of algorithms for fitting the PARAFAC model
- A continuous analogue of the tensor-train decomposition
- A fast randomized algorithm for overdetermined linear least-squares regression
- A least-squares method for sparse low rank approximation of multivariate functions
- Algorithm 862
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Efficient MATLAB Computations with Sparse and Factored Tensors
- Enhanced Line Search: A Novel Method to Accelerate PARAFAC
- Exact matrix completion via convex optimization
- Extensions of Lipschitz mappings into a Hilbert space
- Faster least squares approximation
- Randomized alternating least squares for canonical tensor decompositions: application to a PDE with random data
- Sketching as a tool for numerical linear algebra
- Tensor Decomposition for Signal Processing and Machine Learning
- Tensor Decompositions and Applications
- Tensor-train decomposition
- Uncertainty principles and ideal atomic decomposition
Cited in
(57)- Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
- A fast algorithm for rank-\((L, M, N)\) block term decomposition of multi-dimensional data
- 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
- Tracking tensor ring decompositions of streaming tensors
- Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Accelerated doubly stochastic gradient descent for tensor CP decomposition
- A random sampling algorithm for fully-connected tensor network decomposition with applications
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- A fast sketching-based algorithm for rank-\((L,L,1)\) block term decomposition
- Provable stochastic algorithm for large-scale fully-connected tensor network decomposition
- A polynomial-time algorithm for computing low CP-rank decompositions
- Tensor methods for the Boltzmann-BGK equation
- Real eigenstructure of regular simplex tensors
- Structured random sketching for PDE inverse problems
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- Tensor-CUR Decompositions for Tensor-Based Data
- Stochastic gradients for large-scale tensor decomposition
- Low-rank Tucker approximation of a tensor from streaming data
- A Higher-Order Generalized Singular Value Decomposition for Rank-Deficient Matrices
- Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
- Parallel tensor methods for high-dimensional linear PDEs
- Randomized tensor wheel decomposition
- Johnson–Lindenstrauss Embeddings with Kronecker Structure
- Sparse low rank approximation of potential energy surfaces with applications in estimation of anharmonic zero point energies and frequencies
- A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes
- An efficient algorithm for computing the approximate t-URV and its applications
- Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC
- The Hanson-Wright inequality for random tensors
- Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
- Parallel Randomized Tucker Decomposition Algorithms
- Fast randomized matrix and tensor interpolative decomposition using countsketch
- Inertial accelerated SGD algorithms for solving large-scale lower-rank tensor CP decomposition problems
- Quantized CP approximation and sparse tensor interpolation of function-generated data.
- Randomized tensor decomposition for large-scale data assimilation problems for carbon dioxide sequestration
- Randomized algorithms for the low multilinear rank approximations of tensors
- Supervised multiway factorization
- Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
- Time-aware tensor decomposition for sparse tensors
- The numerical approximation of nonlinear functionals and functional differential equations
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- An ATLD-ALS method for the trilinear decomposition of large third-order tensors
- Tensor-structured sketching for constrained least squares
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- A block-randomized stochastic method with importance sampling for CP tensor decomposition
- Multiscale co-clustering for tensor data based on canonical polyadic decomposition and slice-wise factorization
- A literature survey of matrix methods for data science
- Numerical CP decomposition of some difficult tensors
- Total variation based tensor decomposition for multi-dimensional data with time dimension.
- Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and Tucker decompositions
- A trust-region-based alternating least-squares algorithm for tensor decompositions
- On Koopman mode decomposition and tensor component analysis
- Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
- Practical leverage-based sampling for low-rank tensor decomposition
- Parallel Candecomp/Parafac decomposition of sparse tensors using dimension trees
- Incremental CP tensor decomposition by alternating minimization method
Describes a project that uses
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)
