In this paper, we focus on the fixed-precision problem for the approximate Tucker decomposition of any tensor. First, we modify several structured matrices for the adaptive randomized range finder algorithm in [W. Yu,...
详细信息
In this paper, we focus on the fixed-precision problem for the approximate Tucker decomposition of any tensor. First, we modify several structured matrices for the adaptive randomized range finder algorithm in [W. Yu, Y. Gu, and Y. Li, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1339--1359], when the standard Gaussian matrices are replaced by uniform random matrices, the Khatri--Rao product of the standard Gaussian matrices (or the uniform random matrices). Second, by using this modified algorithm for each mode unfolding of the input/intermediate tensor, we obtain the adaptive randomized variants for T-HOSVD and ST-HOSVD. Third, we propose theoretical properties for these adaptive randomized variants. Finally, numerical examples illustrate that for a given tolerance, the proposed algorithms are superior to other algorithms in terms of relative error, desired Tucker rank, and running time.
Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-c...
详细信息
Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. First, a mechanism for calculating the approximation error in the Frobenius norm is proposed, which enables efficient adaptive rank determination for a large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by Martinsson and Voronin, this results in an algorithm called randQB_EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB_FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB_FP can serve as a single-pass algorithm for calculating leading singular values, under a certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB_FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.
暂无评论