The average condition number of most tensor rank decomposition problems is infinite

DOI10.1007/S10208-022-09551-1OpenAlexW2921197080MaRDI QIDQ2697393

Nick Vannieuwenhoven, Paul Breiding, Carlos Beltran

Publication date: 12 April 2023

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

condition numbertensor decompositionaverage analysis

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Multilinear algebra, tensor calculus (15A69)

Uses Software

• alphaCertified
• HomotopyContinuation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Energy and discrepancy of rotationally invariant determinantal point processes in high dimensional spheres
• Rank probabilities for real random \(N\times N \times 2\) tensors
• Refined methods for the identifiability of tensors
• Fast linear homotopy to find approximate zeros of polynomial systems
• On a problem posed by Steve Smale
• Elementary structure of real algebraic varieties
• Conditioning of random conic systems under a general family of input distributions
• Identifiability of parameters in latent structure models with many observed variables
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Multilinear algebra. 2nd ed
• Independent component analysis, a new concept?
• Complexity of Bezout's theorem. V: Polynomial time
• Smoothed analysis of termination of linear programming algorithms
• The distribution of condition numbers of rational data of bounded bit length
• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• Ranks of tensors and a generalization of secant varieties
• The real polynomial eigenvalue problem is well conditioned on the average
• Probabilistic analysis of the Grassmann condition number
• A randomized homotopy for the Hermitian eigenpair problem
• Average-case complexity without the black swans
• On maximum, typical and generic ranks
• Semialgebraic Geometry of Nonnegative Tensor Rank
• Condition
• Introduction to Smooth Manifolds
• Tensor decompositions for learning latent variable models
• Algorithm 921
• Smoothed Analysis of Moore–Penrose Inversion
• Tensor Spaces and Numerical Tensor Calculus
• The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs
• Tensor rank is NP-complete
• Generic Uniqueness Conditions for the Canonical Polyadic Decomposition and INDSCAL
• The Probability That a Numerical Analysis Problem is Difficult
• The fundamental theorem of algebra and complexity theory
• The kinematic formula in Riemannian homogeneous spaces
• The Condition Number of Join Decompositions
• Tensor Decomposition for Signal Processing and Machine Learning
• Real identifiability vs. complex identifiability
• Numerical Methods for Computing Angles Between Linear Subspaces
• On Generic Identifiability of 3-Tensors of Small Rank
• Random Points on an Algebraic Manifold
• Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable
• An Algorithm For Generic and Low-Rank Specific Identifiability of Complex Tensors
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Effective Criteria for Specific Identifiability of Tensors and Forms
• A Riemannian Trust Region Method for the Canonical Tensor Rank Approximation Problem
• Applied Multiway Data Analysis
• Tails of Condition Number Distributions
• Condition Numbers of Gaussian Random Matrices
• A Theory of Condition
• The Condition Number of Riemannian Approximation Problems
• On the average condition number of tensor rank decompositions
• On the complexity of computing error bounds

This page was built for publication: The average condition number of most tensor rank decomposition problems is infinite