Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable

DOI10.1137/18M1200531zbMATH Open1451.14170arXiv1807.04159MaRDI QIDQ5232115FDOQ5232115

Carlos Beltran, Nick Vannieuwenhoven, Paul Breiding

Publication date: 29 August 2019

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

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.

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)

Cites Work

• Independent component analysis, a new concept?
• Applied Multiway Data Analysis
• Tensor Decompositions and Applications
• Component models for three-way data: An alternating least squares algorithm with optimal scaling features
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• A Multilinear Singular Value Decomposition
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Condition
• Introduction to Smooth Manifolds
• Title not available (Why is that?)
• Riemannian Geometry
• Title not available (Why is that?)
• Tensor Spaces and Numerical Tensor Calculus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• Distributions of Angles in Random Packing on Spheres
• Title not available (Why is that?)
• An Algorithm For Generic and Low-Rank Specific Identifiability of Complex Tensors
• A Theory of Condition
• Tensor rank is NP-complete
• Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-\((L_r,L_r,1)\) terms, and a new generalization
• A Decomposition for Three-Way Arrays
• Canonical polyadic decomposition of third-order tensors: relaxed uniqueness conditions and algebraic algorithm
• On Generic Identifiability of 3-Tensors of Small Rank
• Multilinear algebra. 2nd ed
• ON THE CONCEPT OF k-SECANT ORDER OF A VARIETY
• Tensor Decomposition for Signal Processing and Machine Learning
• Effective Criteria for Specific Identifiability of Tensors and Forms
• On the Precision Attainable with Various Floating-Point Number Systems
• A new truncation strategy for the higher-order singular value decomposition
• Homotopy techniques for tensor decomposition and perfect identifiability
• Real identifiability vs. complex identifiability
• Semialgebraic geometry of nonnegative tensor rank
• The Condition Number of Join Decompositions
• Condition numbers for the tensor rank decomposition

Cited In (12)

• Derandomization and absolute reconstruction for sums of powers of linear forms
• Systems of Polynomial Equations, Higher-order Tensor Decompositions, and Multidimensional Harmonic Retrieval: A Unifying Framework. Part I: The Canonical Polyadic Decomposition
• A Recursive Eigenspace Computation for the Canonical Polyadic Decomposition
• From Computation to Comparison of Tensor Decompositions
• On Uniqueness and Computation of the Decomposition of a Tensor into Multilinear Rank-$(1,L_r,L_r)$ Terms
• Smoothed analysis for tensor methods in unsupervised learning
• Title not available (Why is that?)
• On Best Low Rank Approximation of Positive Definite Tensors
• A normal form algorithm for tensor rank decomposition
• Nonlinear algebra and applications
• Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
• The average condition number of most tensor rank decomposition problems is infinite

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)