Pencil-based algorithms for tensor rank decomposition are not stable

DOI10.1137/18M1200531MaRDI QIDQ5232115zbMATHFDO

Authors Paul Breiding, Nick Vannieuwenhoven, Carlos Beltran

Publication date 29 August 2019

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

numerical instabilitycanonical polyadic decomposition

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical computation of matrix norms, conditioning, scaling (65F35) Sensitivity analysis for optimization problems on manifolds (49Q12) Geometric aspects of numerical algebraic geometry (14Q65)

Abstract: We prove the existence of an open set of $n_{1}imes{n}_{2}imes{n}_3$ tensors of rank $r$ on which a popular and efficient class of algorithms for computing tensor rank decompositions based on a reduction to a linear matrix pencil, typically followed by a generalized eigendecomposition, is arbitrarily numerically forward unstable. Our analysis shows that this problem is caused by the fact that the condition number of the tensor rank decomposition can be much larger for $n_{1}imes{n}_{2}imes2$ tensors than for the $n_{1}imes{n}_{2}imes{n}_3$ input tensor. Moreover, we present a lower bound for the limiting distribution of the condition number of random tensor rank decompositions of third-order tensors. The numerical experiments illustrate that for random tensor rank decompositions one should anticipate a loss of precision of a few digits.

Recommendations

• Condition numbers for the tensor rank decomposition
• The average condition number of most tensor rank decomposition problems is infinite
• On the average condition number of tensor rank decompositions
• The condition number of many tensor decompositions is invariant under Tucker compression
• Three decompositions of symmetric tensors have similar condition numbers

Cites work

• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• scientific article; zbMATH DE number 3279238 (Why is no real title available?)
• A Decomposition for Three-Way Arrays
• A Multilinear Singular Value Decomposition
• A Theory of Condition
• A new truncation strategy for the higher-order singular value decomposition
• An algorithm for generic and low-rank specific identifiability of complex tensors
• Applied Multiway Data Analysis
• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• Canonical polyadic decomposition of third-order tensors: relaxed uniqueness conditions and algebraic algorithm
• Component models for three-way data: An alternating least squares algorithm with optimal scaling features
• Condition numbers for the tensor rank decomposition
• Condition. The geometry of numerical algorithms
• Distributions of angles in random packing on spheres
• Effective criteria for specific identifiability of tensors and forms
• Homotopy techniques for tensor decomposition and perfect identifiability
• Independent component analysis, a new concept?
• Introduction to Smooth Manifolds
• Multilinear algebra. 2nd ed
• ON THE CONCEPT OF k-SECANT ORDER OF A VARIETY
• On Generic Identifiability of 3-Tensors of Small Rank
• On the Precision Attainable with Various Floating-Point Number Systems
• Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-\((L_r,L_r,1)\) terms, and a new generalization
• Real identifiability vs. complex identifiability
• Riemannian Geometry
• Semialgebraic geometry of nonnegative tensor rank
• 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 rank is NP-complete
• Tensor spaces and numerical tensor calculus
• The condition number of join decompositions
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

Cited in

(13)

• Numerical stability and tensor nuclear norm
• On Best Low Rank Approximation of Positive Definite Tensors
• A normal form algorithm for tensor rank decomposition
• Derandomization and absolute reconstruction for sums of powers of linear forms
• Nonlinear algebra and applications
• Smoothed analysis for tensor methods in unsupervised learning
• Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
• Systems of polynomial equations, higher-order tensor decompositions, and multidimensional harmonic retrieval: a unifying framework. Part I: the canonical polyadic decomposition
• On Uniqueness and Computation of the Decomposition of a Tensor into Multilinear Rank-$(1,L_r,L_r)$ Terms
• scientific article; zbMATH DE number 7668289 (Why is no real title available?)
• From computation to comparison of tensor decompositions
• A recursive eigenspace computation for the canonical polyadic decomposition
• The average condition number of most tensor rank decomposition problems is infinite

Describes a project that uses

Uses Software

• mctoolbox
• Tensorlab

This page was built for publication: Pencil-based algorithms for tensor rank decomposition are not stable

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