PRACTICAL LEVERAGE-BASED SAMPLING FOR LOW-RANK TENSOR DECOMPOSITION

作     者：Larsen, Brett W. Kolda, Tamara G. 

作者机构：Stanford Univ Stanford CA 94305 USA MathSci Ai Dublin CA 94568 USA 

出 版 物：《SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS》 (SIAM J. Matrix Anal. Appl.)

年 卷 期：2022年第43卷第3期

页      面：1488-1517页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Department of Energy Office of Science Advanced Scientific Computing Research Applied Mathematics Program Department of Energy Computational Sciences Graduate Fellowship program [DE-FG02-97ER25308] 

主　　题：tensor decomposition CANDECOMP/PARAFAC canonical polyadic CP matrix sketching leverage score sampling randomized numerical linear algebra RandNLA 

摘      要：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(r(d)/epsilon) for a decomposition of rank r and epsilon-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.