Approximate tensor decompositions: disappearance of many separations

DOI10.1063/5.0033876zbMATH Open1497.15027arXiv2004.10219OpenAlexW3197152554MaRDI QIDQ5154281FDOQ5154281

Authors: Gemma De las Cuevas, Andreas Klingler, Tim Netzer 

Publication date: 4 October 2021

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

Abstract: It is well-known that tensor decompositions show separations, that is, that constraints on local terms (such as positivity) may entail an arbitrarily high cost in their representation. Here we show that many of these separations disappear in the approximate case. Specifically, for every approximation error $varepsilon$ and norm, we define the approximate rank as the minimum rank of an element in the $varepsilon$-ball with respect to that norm. For positive semidefinite matrices, we show that the separations between rank, purification rank, and separable rank disappear for a large class of Schatten $p$-norms. For nonnegative tensors, we show that the separations between rank, positive semidefinite rank, and nonnegative rank disappear for all $el{l}_p$-norms with $p>1$. For the trace norm ($p=1$), we obtain upper bounds that depend on the ambient dimension. We also provide a deterministic algorithm to obtain the approximate decomposition attaining our bounds. Our main tool is an approximate version of Carath'eodory's Theorem. Our results imply that many separations are not robust under small perturbations of the tensor, with implications in quantum many-body systems and communication complexity.

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

Recommendations

• Hermitian tensor product approximation of complex matrices and separability
• On the order of approximation in approximative triadic decompositions of tensors
• Separability of Hermitian tensors and PSD decompositions
• On the rank and the approximation of symmetric tensors
• Relative error tensor low rank approximation

zbMATH Keywords

tensor decompositionsquantum many-body systemsCarathéodory theorem

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Miscellaneous inequalities involving matrices (15A45) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Many-body theory; quantum Hall effect (81V70)

Cites Work

• Functions of Matrices
• Characterization of the subdifferential of some matrix norms
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• An Introduction to Banach Space Theory
• Title not available (Why is that?)
• Linear vs. semidefinite extended formulations
• Sharp uniform convexity and smoothness inequalities for trace norms
• Title not available (Why is that?)
• Lifts of Convex Sets and Cone Factorizations
• Symmetric tensor decomposition
• Positive semidefinite rank
• Compressibility of Positive Semidefinite Factorizations and Quantum Models
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Title not available (Why is that?)
• Approximate Carathéodory's theorem in uniformly smooth Banach spaces
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices

Cited In (7)

• Polynomial decompositions with invariance and positivity inspired by tensors
• Tensor decompositions on simplicial complexes with invariance
• Boolean operators and neural networks
• Blind Separation of Exponential Polynomials and the Decomposition of a Tensor in Rank-$(L_r,L_r,1)$ Terms
• On the computational benefit of tensor separation for high-dimensional discrete convolutions
• Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
• Approximate real symmetric tensor rank

This page was built for publication: Approximate tensor decompositions: disappearance of many separations

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