Approximate tensor decompositions: disappearance of many separations

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 $\epsilon$ and norm, we define the approximate rank as the minimum rank of an element in the $\epsilon$-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 ${\ell }_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éodory'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.

arXiv comment35 pages (single column), very close to published version

References in corpus (10)

• Robustness of entanglement
• Tensor networks for complex quantum systems
• Lifts of convex sets and cone factorizations
• Purifications of multipartite states: limitations and constructive methods
• Positive semidefinite rank
• Efficient description of many-body systems with Matrix Product Density Operators
• Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning
• Compressibility of positive semidefinite factorizations and quantum models
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Tensor decompositions on simplicial complexes with invariance

Cited by in corpus (1)

• Quantum Information Theory and Free Semialgebraic Geometry: One Wonderland Through Two Looking Glasses