The condition number of many tensor decompositions is invariant under Tucker compression

DOI10.1007/S11075-023-01526-9MaRDI QIDQ6047573zbMATH OpenOpenAlexFDO

Authors Nick Dewaele, Paul Breiding, Nick Vannieuwenhoven

Publication date 12 September 2023

Published in Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

condition numberinvariancestructured block term decompositionsum of tensor trainsTucker compression

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: We characterise the sensitivity of several additive tensor decompositions with respect to perturbations of the original tensor. These decompositions include canonical polyadic decompositions, block term decompositions, and sums of tree tensor networks. Our main result shows that the condition number of all these decompositions is invariant under Tucker compression. This result can dramatically speed up the computation of the condition number in practical applications. We give the example of an $265imes371imes7$ tensor of rank $3$ from a food science application whose condition number was computed in $6.9$ milliseconds by exploiting our new theorem, representing a speedup of four orders of magnitude over the previous state of the art.

Recommendations

• Three decompositions of symmetric tensors have similar condition numbers
• Condition numbers for the tensor rank decomposition
• Linear algebra for tensor problems
• The average condition number of most tensor rank decomposition problems is infinite
• On the average condition number of tensor rank decompositions

Cites work

• A Multilinear Singular Value Decomposition
• A new scheme for the tensor representation
• A new truncation strategy for the higher-order singular value decomposition
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• A Theory of Condition
• Condition numbers for the tensor rank decomposition
• Condition. The geometry of numerical algorithms
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• Decompositions of a Higher-Order Tensor in Block Terms—Part II: Definitions and Uniqueness
• Decompositions of a Higher-Order Tensor in Block Terms—Part III: Alternating Least Squares Algorithms
• Hierarchical Singular Value Decomposition of Tensors
• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Introduction to Smooth Manifolds
• Julia: a fresh approach to numerical computing
• Multilinear algebra. 2nd ed
• On the identifiability of ternary forms
• Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-(L_r,L_r,1) terms, and a new generalization
• Orthogonal tensor decompositions
• SOTT: greedy approximation of a tensor as a sum of tensor trains
• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions and Applications
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Tensor-train decomposition
• The condition number of join decompositions
• The Condition Number of Riemannian Approximation Problems
• The geometry of algorithms using hierarchical tensors
• The structured condition number of a differentiable map between matrix manifolds, with applications

Cited in

(7)

• Condition numbers for the tensor rank decomposition
• Three decompositions of symmetric tensors have similar condition numbers
• The average condition number of most tensor rank decomposition problems is infinite
• Pencil-based algorithms for tensor rank decomposition are not stable
• Tensor and its Tucker core: the invariance relationships.
• Recompression of Hadamard Products of Tensors in Tucker Format
• Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition

This page was built for publication: The condition number of many tensor decompositions is invariant under Tucker compression

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