Efficient algorithms for Tucker decomposition via approximate matrix multiplication

DOI10.1007/S10444-025-10232-0MaRDI QIDQ6982632zbMATH OpenFDO

Authors Mao-Lin Che, Yimin Wei, Hong Yan

Publication date 16 May 2025

Published in Advances in Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10444-025-10232-0

zbMATH Keywords

approximate matrix multiplicationlow rank approximations of tensorsnearly optimal probabilitiespower schemerandom projectionrandomized ST-HOSVDrandomized T-HOSVDstandard Gaussian matricestensor contractionTucker decompositionuniform probabilities

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Basic linear algebra (15A99) Random matrices (algebraic aspects) (15B52) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Numerical optimization and variational techniques (65K10) Randomized algorithms (68W20)

Cites work

• A fast randomized algorithm for orthogonal projection
• A fast randomized algorithm for the approximation of matrices
• A literature survey of low-rank tensor approximation techniques
• A multilevel Monte Carlo estimator for matrix multiplication
• A Multilinear Singular Value Decomposition
• A new truncation strategy for the higher-order singular value decomposition
• A Newton-Grassmann method for computing the best multilinear rank-(r₁,r₂,r₃) approximation of a tensor
• A randomized algorithm for a tensor-based generalization of the singular value decomposition
• A randomized algorithm for principal component analysis
• A randomized algorithm for the decomposition of matrices
• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• A randomized tensor singular value decomposition based on the t-product.
• Algorithm 862
• Algorithm 941: \texttt{htucker} -- a Matlab toolbox for tensors in hierarchical Tucker format
• An efficient randomized algorithm for computing the approximate Tucker decomposition
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme
• Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Factorization strategies for third-order tensors
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Nonnegative Matrix/Tensor Factorization Based on Low-Rank Approximation
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Generalizing the column-row matrix decomposition to multi-way arrays
• Hierarchical Singular Value Decomposition of Tensors
• HOID: higher order interpolatory decomposition for tensors based on Tucker representation
• Importance sampling for a Monte Carlo matrix multiplication algorithm, with application to information retrieval
• Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
• Krylov-type methods for tensor computations.I
• Low-rank Tucker approximation of a tensor from streaming data
• Matrix approximation and projective clustering via volume sampling
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Optimal sampling algorithms for block matrix multiplication
• Practical sketching algorithms for low-rank matrix approximation
• Quasi-Newton methods on Grassmannians and multilinear approximations of tensors
• RA-HOOI: rank-adaptive higher-order orthogonal iteration for the fixed-accuracy low multilinear-rank approximation of tensors
• Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
• Randomized algorithms for the approximations of Tucker and the tensor train decompositions
• Randomized algorithms for the low multilinear rank approximations of tensors
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Randomized LU decomposition
• Randomized LU decomposition using sparse projections
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Subspace Iteration Randomization and Singular Value Problems
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
• Tensor Decompositions and Applications
• Tensor networks for dimensionality reduction and large-scale optimization. I: Low-rank tensor decompositions
• Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives
• Tensor-train decomposition
• The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
• The restricted isometry property for random block diagonal matrices
• Theory and Computation of Complex Tensors and its Applications
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. I: Tucker case

Cited in

(2)

• Efficient randomized algorithms for computing an approximation of the tensor train decomposition
• Intrinsic Low-Tucker-Rank Theory and Unified Tensor CUR Decomposition for High-Dimensional Hyperinterpolation

This page was built for publication: Efficient algorithms for Tucker decomposition via approximate matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6982632)