A Krylov-Schur-like method for computing the best rank-(r₁,r₂,r₃) approximation of large and sparse tensors

DOI10.1007/S11075-022-01303-0zbMATH Open1500.65016arXiv2012.07595OpenAlexW3112172152WikidataQ114224274 ScholiaQ114224274MaRDI QIDQ2084262FDOQ2084262

Authors: Lars Eldén, Maryam Dehghan 

Publication date: 18 October 2022

Published in: Numerical Algorithms (Search for Journal in Brave)

Abstract: The paper is concerned with methods for computing the best low multilinear rank approximation of large and sparse tensors. Krylov-type methods have been used for this problem; here block versions are introduced. For the computation of partial eigenvalue and singular value decompositions of matrices the Krylov-Schur (restarted Arnoldi) method is used. We describe a generalization of this method to tensors, for computing the best low multilinear rank approximation of large and sparse tensors. In analogy to the matrix case, the large tensor is only accessed in multiplications between the tensor and blocks of vectors, thus avoiding excessive memory usage. It is proved that, if the starting approximation is good enough, then the tensor Krylov-Schur method is convergent. Numerical examples are given for synthetic tensors and sparse tensors from applications, which demonstrate that for most large problems the Krylov-Schur method converges faster and more robustly than higher order orthogonal iteration.

Full work available at URL: https://arxiv.org/abs/2012.07595

Recommendations

• Krylov-type methods for tensor computations.I
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. I: Tucker case
• A Newton-Grassmann method for computing the best multilinear rank-\((r_1,r_2,r_3)\) approximation of a tensor
• The Best rank-\((R_1,R_2,R_3)\) approximation of tensors by means of a geometric Newton method

zbMATH Keywords

Grassmann manifoldsymmetric tensorsparse tensorbest rank approximationblock Krylov-type methodKrylov-Schur algorithmmultilinear rank tensors

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Efficient MATLAB Computations with Sparse and Factored Tensors
• Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
• ARPACK Users' Guide
• Title not available (Why is that?)
• The Geometry of Algorithms with Orthogonality Constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Calculating the Singular Values and Pseudo-Inverse of a Matrix
• Algorithm 862
• A Multilinear Singular Value Decomposition
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Euclidean embedding of co-occurrence data
• Matrix algorithms. Vol. 2: Eigensystems
• Most tensor problems are NP-hard
• Tensors in computations
• Title not available (Why is that?)
• On search directions for minimization algorithms
• Decomposition of quantics in sums of powers of linear forms
• A Krylov--Schur algorithm for large eigenproblems
• Low rank Tucker-type tensor approximation to classical potentials
• Rank-one approximation to high order tensors
• Perturbation theory and optimality conditions for the best multilinear rank approximation of a tensor
• A Newton-Grassmann method for computing the best multilinear rank-\((r_1,r_2,r_3)\) approximation of a tensor
• Multigrid accelerated tensor approximation of function related multidimensional arrays
• Block Krylov-Schur method for large symmetric eigenvalue problems
• Handwritten digit classification using higher order singular value decomposition
• Algorithms for Separable Nonlinear Least Squares Problems
• Quasi-Newton methods on Grassmannians and multilinear approximations of tensors
• Differential-geometric Newton method for the best rank-\((R _{1}, R _{2}, R _{3})\) approximation of tensors
• Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme
• Krylov-type methods for tensor computations.I
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. I: Tucker case
• Spectral partitioning of large and sparse 3‐tensors using low‐rank tensor approximation

Cited In (5)

• Efficient alternating least squares algorithms for low multilinear rank approximation of tensors
• Tensor Golub-Kahan method based on Einstein product
• Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. I: Tucker case
• Krylov-type methods for tensor computations.I

Uses Software

• eigs
• TensorToolbox
• ARPACK
• Algorithm 862

This page was built for publication: A Krylov-Schur-like method for computing the best rank-\((r_1,r_2,r_3)\) approximation of large and sparse tensors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084262)