Id: arxiv/2607.22194 Url: https://arxiv.org/abs/2607.22194 Tags: math.NA Score: 0 Title: Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition Domain: math.NA Source: arxiv Authors: Israa Fakih, Laura Grigori, Karl Pierce Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-24 Page: https://delphi.science/r/arxiv/2607.22194 We present a novel leverage score-based sampling strategy for the randomized alternating least squares optimization (ALS) of the canonical polyadic decomposition (CPD-ALS). Unlike previous strategies, we determine row-wise samples for the CPD-ALS problem from the leverage scores of the target tensor which is being decomposed. We demonstrate that, when rows are sampled according to the leverage score distribution of the matricized target tensor, each least squares subproblem of the CPD-ALS problem achieves $(1+ε)-$relative accuracy in the residual norm with probability at least $1-δ$ using a…