The condition number of join decompositions

DOI10.1137/17M1142880zbMATH Open1384.49035arXiv1611.08117WikidataQ130209071 ScholiaQ130209071MaRDI QIDQ4604567FDOQ4604567

Authors: Paul Breiding, Nick Vannieuwenhoven 

Publication date: 2 March 2018

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

Abstract: The join set of a finite collection of smooth embedded submanifolds of a mutual vector space is defined as their Minkowski sum. Join decompositions generalize some ubiquitous decompositions in multilinear algebra, namely tensor rank, Waring, partially symmetric rank and block term decompositions. This paper examines the numerical sensitivity of join decompositions to perturbations; specifically, we consider the condition number for general join decompositions. It is characterized as a distance to a set of ill-posed points in a supplementary product of Grassmannians. We prove that this condition number can be computed efficiently as the smallest singular value of an auxiliary matrix. For some special join sets, we characterized the behavior of sequences in the join set converging to the latter's boundary points. Finally, we specialize our discussion to the tensor rank and Waring decompositions and provide several numerical experiments confirming the key results.

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

Recommendations

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

zbMATH Keywords

condition numberCP decompositionWaring decompositionblock term decompositiontensor rank decompositionjoin decomposition problemjoin set

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Multilinear algebra, tensor calculus (15A69) Methods of local Riemannian geometry (53B21) Numerical computation of matrix norms, conditioning, scaling (65F35) Sensitivity analysis for optimization problems on manifolds (49Q12) Local Riemannian geometry (53B20) Semialgebraic sets and related spaces (14P10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Orthogonal tensor decompositions
• Applied Multiway Data Analysis
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Identifiability of parameters in latent structure models with many observed variables
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Title not available (Why is that?)
• Condition. The geometry of numerical algorithms
• Introduction to Smooth Manifolds
• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Title not available (Why is that?)
• Title not available (Why is that?)
• On maximum, typical and generic ranks
• Title not available (Why is that?)
• Induction for secant varieties of Segre varieties
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the uniqueness of the canonical polyadic decomposition of third-order tensors. II: Uniqueness of the overall decomposition
• Tensor decompositions for learning latent variable models
• On generic identifiability of symmetric tensors of subgeneric rank
• Title not available (Why is that?)
• A coordinate-free condition number for convex programming
• An algorithm for generic and low-rank specific identifiability of complex tensors
• Kruskal's Permutation Lemma and the Identification of CANDECOMP/PARAFAC and Bilinear Models with Constant Modulus Constraints
• Rank-one approximation to high order tensors
• Congruences and concurrent lines in multi-view geometry
• Decompositions of a Higher-Order Tensor in Block Terms—Part II: Definitions and Uniqueness
• On Generic Identifiability of 3-Tensors of Small Rank
• Projection-like retractions on matrix manifolds
• On the ideals and singularities of secant varieties of Segre varieties
• The geometry of ill-conditioning
• Tensor Decomposition for Signal Processing and Machine Learning
• Effective criteria for specific identifiability of tensors and forms
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• Real rank two geometry
• Condition numbers for the tensor rank decomposition

Cited In (18)

• Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
• Learning diagonal Gaussian mixture models and incomplete tensor decompositions
• Perturbation analysis for matrix joint block diagonalization
• Pencil-based algorithms for tensor rank decomposition are not stable
• Which constraints of a numerical problem cause ill-conditioning?
• On the minimal ranks of matrix pencils and the existence of a best approximate block-term tensor decomposition
• The condition number of many tensor decompositions is invariant under Tucker compression
• A recursive eigenspace computation for the canonical polyadic decomposition
• An approximation method of CP rank for third-order tensor completion
• Riemannian Newton optimization methods for the symmetric tensor approximation problem
• Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
• Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
• The Condition Number of Riemannian Approximation Problems
• A Riemannian trust region method for the canonical tensor rank approximation problem
• Three decompositions of symmetric tensors have similar condition numbers
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• The average condition number of most tensor rank decomposition problems is infinite
• The dynamics of swamps in the canonical tensor approximation problem

Uses Software

• mctoolbox
• Tensorlab

This page was built for publication: The condition number of join decompositions

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