A cross-based alternating least squares method for CP tensor decomposition

Canonical Polyadic (CP) tensor decomposition is a fundamental tool for analyzing high-dimensional data. The standard Alternating Least Squares (ALS) algorithm becomes computationally prohibitive for large-scale tensors as it requires accessing all tensor entries to solve the linear least squares subproblems at each iteration. To mitigate this cost, randomized sampling methods have been introduced to solve smaller, sampled least squares problems. However, these approaches often depend heavily on the sampling distribution and typically require a sample size significantly larger than the target rank ($s \gg k$) to ensure accuracy.In this talk, we present a novel deterministic cross-based ALS method (CP-ACLS) that utilizes maximum volume-based pivot selection to identify the most $R$ informative rows for each subproblem. We propose a hierarchical sampling strategy that exploits the Khatri-Rao structure to efficiently select these pivots. Compared to standard and randomized ALS approaches, our method can potentially reduce the computational cost significantly without sacrificing accuracy