2020/06/30 by Brett W. Larsen, Tamara G. Kolda, Larsen, Brett W. +1
Computer Science · Engineering · Mathematics · #Advanced Neural Network Applications #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2006.16438
openalex publication_date 2020/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The low-rank canonical polyadic tensor decomposition is useful in data analysis and can be computed by solving a sequence of overdetermined least squares subproblems. Motivated by consideration of sparse tensors, we propose sketching each subproblem using leverage scores to select a subset of the rows, with probabilistic guarantees on the solution accuracy. We randomly sample rows proportional to leverage score upper bounds that can be efficiently computed using the special Khatri-Rao subproblem structure inherent in tensor decomposition. Crucially, for a (d+1)-way tensor, the number of rows in the sketched system is O(rd/ε) for a decomposition of rank r and ε-accuracy in the least squares solve, independent of both the size and the number of nonzeros in the tensor. Along the way, we provide a practical solution to the generic matrix sketching problem of sampling overabundance for high-leverage-score rows, proposing to include such rows deterministically and combine repeated samples in the sketched system; we conjecture that this can lead to improved theoretical bounds. Numerical results on real-world large-scale tensors show the method is significantly faster than deterministic methods at nearly the same level of accuracy.