Approximate tensor decompositions: disappearance of many separations

DOI10.1063/5.0033876MaRDI QIDQ5154281zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(7)

• Polynomial decompositions with invariance and positivity inspired by tensors
• Tensor decompositions on simplicial complexes with invariance
• Boolean operators and neural networks
• On the computational benefit of tensor separation for high-dimensional discrete convolutions
• Blind Separation of Exponential Polynomials and the Decomposition of a Tensor in Rank-$(L_r,L_r,1)$ Terms
• 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)