Wedderburn rank reduction and Krylov subspace method for tensor approximation. Part 1: Tucker case

Abstract

New algorithms are proposed for the Tucker approximation of a 3-tensor, that access it using only the tensor-by-vector-by-vector multiplication subroutine. In the matrix case, Krylov methods are methods of choice to approximate the dominant column and row subspaces of a sparse or structured matrix given through the matrix-by-vector multiplication subroutine. Using the Wedderburn rank reduction formula, we propose an algorithm of matrix approximation that computes Krylov subspaces and allows generalization to the tensor case. Several variants of proposed tensor algorithms differ by pivoting strategies, overall cost and quality of approximation. By convincing numerical experiments we show that the proposed methods are faster and more accurate than the minimal Krylov recursion, proposed recently by Elden and Savas.

34 pages, 3 tables, 5 figures. Submitted to SIAM J. Scientific Computing

References in corpus (2)

• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. Part 1: Tucker case

Cited by in corpus (7)

• Alternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems
• Alternating minimal energy methods for linear systems in higher dimensions. Part I: SPD systems
• A literature survey of low-rank tensor approximation techniques
• Exact NMR simulation of protein-size spin systems using tensor train formalism
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. Part 1: Tucker case
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Towards a better understanding of the matrix product function approximation algorithm in application to quantum physics