Fast truncation of mode ranks for bilinear tensor operations

DOI10.1002/NLA.765MaRDI QIDQ4909731zbMATH OpenOpenAlexFDO

Authors N. L. Zamarashkin, D. V. Savostyanov, E. E. Tyrtyshnikov

Publication date 21 March 2013

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

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

zbMATH Keywords

interpolative decompositionlow-rank matrix approximationmatrix pseudo-skeleton approximationmultidimensional arraysstructured tensorsTucker approximation

Mathematics Subject Classification ID

Factorization of matrices (15A23) Multilinear algebra, tensor calculus (15A69)

Abstract: We propose a fast algorithm for mode rank truncation of the result of a bilinear operation on 3-tensors given in the Tucker or canonical form. If the arguments and the result have mode sizes n and mode ranks r, the computation costs $O(n{r}^3+r^4)$. The algorithm is based on the cross approximation of Gram matrices, and the accuracy of the resulted Tucker approximation is limited by square root of machine precision.

Recommendations

• Linear algebra for tensor problems
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. I: Tucker case
• Fast revealing of mode ranks of tensor in canonical form
• Tensor-train decomposition
• Multiresolution low-rank tensor formats

Cites work

• A Multilinear Singular Value Decomposition
• A theory of pseudoskeleton approximations
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Black box low tensor-rank approximation using fiber-crosses
• Computation of the Canonical Decomposition by Means of a Simultaneous Generalized Schur Decomposition
• Cross approximation in tensor electron density computations
• Fast revealing of mode ranks of tensor in canonical form
• Fast simultaneous orthogonal reduction to triangular matrices
• Incomplete cross approximation in the mosaic-skeleton method
• Linear algebra for tensor problems
• Multigrid accelerated tensor approximation of function related multidimensional arrays
• On cross approximation of multi-index arrays
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Principal component analysis of three-mode data by means of alternating least squares algorithms
• Tensor decomposition in electronic structure calculations on 3D Cartesian grids
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• The maximal-volume concept in approximation by low-rank matrices
• Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time
• Verification of the cross 3D algorithm on quantum chemistry data

Cited in

(8)

• Superfast Fourier transform using QTT approximation
• Black box approximation of tensors in hierarchical Tucker format
• A literature survey of low-rank tensor approximation techniques
• Exploiting Efficient Representations in Large-Scale Tensor Decompositions
• Numerical tensor calculus
• Fast multidimensional convolution in low-rank tensor formats via cross approximation
• Q-less QR decomposition in inner product spaces
• Linear algebra for tensor problems

Describes a project that uses

Uses Software

• cross2D

This page was built for publication: Fast truncation of mode ranks for bilinear tensor operations

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