Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition

DOI10.48550/arXiv.2607.22194MaRDI QIDQ7284464zbMATH OpenarXivFDO

Authors Laura Grigori, Israa Fakih, Karl Pierce

Publication date 24 July 2026

Published in arXiv

Tldr We introduce a randomized interpolative decomposition method to speed up canonical polyadic alternating least squares optimization by leveraging the leverage score distribution of the tensor being decomposed. Our strategy leads to a $(1+ε)-$accurate approximation with high probability in each ALS iteration, significantly reducing computational and storage requirements compared to prior methods.

Full work available at URL https://doi.org/10.48550/arXiv.2607.22194

arXiv classification

math.NA

Cites work

• A Practical Randomized CP Tensor Decomposition
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Decomposition of Big Tensors With Low Multilinear Rank
• Determinantal point processes in randomized numerical linear algebra
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings
• Fast approximation of matrix coherence and statistical leverage
• Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Parallel Randomized QR with Column Pivoting Algorithms for Reliable Low-rank Matrix Approximations
• Faster least squares approximation
• Householder QR factorization with randomization for column pivoting (HQRRP)
• Local convergence of the alternating least squares algorithm for canonical tensor approximation
• Numerical operator calculus in higher dimensions
• OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings
• Practical leverage-based sampling for low-rank tensor decomposition
• Principal component analysis of three-mode data by means of alternating least squares algorithms
• Randomized algorithms for symmetric nonnegative matrix factorization
• Randomized QR with column pivoting
• Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation
• Sketching as a tool for numerical linear algebra
• Tensor Decompositions and Applications
• The expression of a tensor or a polyadic as a sum of products.

This page was built for publication: Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition

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