More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees

2021/10/14 by Osman Asif Malik, Malik, Osman Asif · 1 citation
Mathematics · Computer Science · Physics and Astronomy · #Tensor decomposition and applications #Computational Physics and Python Applications #Model Reduction and Neural Networks

paper · pdf · doi:10.48550/arxiv.2110.07631

Abstract

Recent papers have developed alternating least squares (ALS) methods for CP and tensor ring decomposition with a per-iteration cost which is sublinear in the number of input tensor entries for low-rank decomposition. However, the per-iteration cost of these methods still has an exponential dependence on the number of tensor modes when parameters are chosen to achieve certain worst-case guarantees. In this paper, we propose sampling-based ALS methods for the CP and tensor ring decompositions whose cost does not have this exponential dependence, thereby significantly improving on the previous state-of-the-art. We provide a detailed theoretical analysis and also apply the methods in a feature extraction experiment.

Cited by

• Domain-Aware Tensor Network Structure Search

Related

• Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks
• Practical Alternating Least Squares for Tensor Ring Decomposition
• Efficient construction of tensor ring representations from sampling
• Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
• CP Decomposition for Tensors via Alternating Least Squares with QR Decomposition