A Practical Randomized CP Tensor Decomposition
From MaRDI portal
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
- 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
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- 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
(74)- The numerical approximation of nonlinear functionals and functional differential equations
- Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and Tucker decompositions
- Supervised multiway factorization
- Parallel tensor methods for high-dimensional linear PDEs
- Fast randomized matrix and tensor interpolative decomposition using countsketch
- Inertial accelerated SGD algorithms for solving large-scale lower-rank tensor CP decomposition problems
- Tensor methods for the Boltzmann-BGK equation
- An ATLD-ALS method for the trilinear decomposition of large third-order tensors
- A fast sketching-based algorithm for rank-\((L,L,1)\) block term decomposition
- An efficient algorithm for computing the approximate t-URV and its applications
- Time-aware tensor decomposition for sparse tensors
- The Hanson-Wright inequality for random tensors
- 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
- Randomized algorithms for the low multilinear rank approximations of tensors
- Sparse low rank approximation of potential energy surfaces with applications in estimation of anharmonic zero point energies and frequencies
- A polynomial-time algorithm for computing low CP-rank decompositions
- Parallel Candecomp/Parafac decomposition of sparse tensors using dimension trees
- A trust-region-based alternating least-squares algorithm for tensor decompositions
- On Koopman mode decomposition and tensor component analysis
- Incremental CP tensor decomposition by alternating minimization method
- Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
- Tensor-structured sketching for constrained least squares
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- Stochastic gradients for large-scale tensor decomposition
- Low-rank Tucker approximation of a tensor from streaming data
- Numerical CP decomposition of some difficult tensors
- Practical leverage-based sampling for low-rank tensor decomposition
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Structured random sketching for PDE inverse problems
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- Quantized CP approximation and sparse tensor interpolation of function-generated data.
- Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
- Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking
- Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC
- Tensor-CUR Decompositions for Tensor-Based Data
- Total variation based tensor decomposition for multi-dimensional data with time dimension.
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- Johnson–Lindenstrauss Embeddings with Kronecker Structure
- Real eigenstructure of regular simplex tensors
- A literature survey of matrix methods for data science
- Randomized tensor decomposition for large-scale data assimilation problems for carbon dioxide sequestration
- Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
- A Higher-Order Generalized Singular Value Decomposition for Rank-Deficient Matrices
- A block-randomized stochastic method with importance sampling for CP tensor decomposition
- A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes
- Accelerated doubly stochastic gradient descent for tensor CP decomposition
- Provable stochastic algorithm for large-scale fully-connected tensor network decomposition
- Parallel Randomized Tucker Decomposition Algorithms
- Randomized tensor wheel decomposition
- A random sampling algorithm for fully-connected tensor network decomposition with applications
- 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
- Fast algorithms for least squares problems with Kronecker lower subsets
- Efficient randomized algorithms for computing an approximation of the tensor train decomposition
- Accelerated alternating least squares for tensor wheel decomposition with applications
- Tensor decomposition with unaligned observations
- An alternating algorithm for structure preserving CP-decompositions of partially symmetric tensors
- Tensor robust principal component analysis with total generalized variation for high-dimensional data recovery
- Inertial accelerated stochastic mirror descent for large-scale generalized tensor CP decomposition
- Randomized algorithms for symmetric nonnegative matrix factorization
- A modified spectral projected gradient method for tensor approximations over closed convex sets
- Subspace embedding with random Khatri-Rao products and its application to eigensolvers
- Intrinsic Low-Tucker-Rank Theory and Unified Tensor CUR Decomposition for High-Dimensional Hyperinterpolation
- Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition
- Group sparse-based tensor CP decomposition: model, algorithm, and applications in chemometrics
- A quasi-subspace iteration method for canonical polyadic decomposition to third order tensors
- Compressed randomized t-CSVD and its applications
- A chiseling algorithm for low-rank Grassmann decomposition of skew-symmetric tensors
- Block-randomized stochastic methods for tensor ring decomposition
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)
