Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations

Andreas Klingler; Tim Netzer; Gemma De les Coves

doi:10.22331/q-2025-02-26-1649

Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations

Andreas Klingler^1,2, Tim Netzer³, and Gemma De les Coves¹

¹Institute for Theoretical Physics, Technikerstr. 21a, A-6020 Innsbruck, Austria
²Faculty of Mathematics, Oskar-Morgenstern-Platz 1, A-1090 Wien, Austria
³Department of Mathematics, Technikerstr. 13, A-6020 Innsbruck, Austria

Published:	2025-02-26, volume 9, page 1649
Editor:	Ion Nechita
Eprint:	arXiv:2304.13478v3
Doi:	https://doi.org/10.22331/q-2025-02-26-1649
Citation:	Quantum 9, 1649 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.

Featured image: Let \( T \) be a tensor in an \( n \)-fold tensor product space, and consider a specific notion of rank, denoted as t-rank. If there exists a family of tensors \( (T_\varepsilon)_{\varepsilon > 0} \) such that \( T_\varepsilon \to T \) as \( \varepsilon \to 0 \) and \( \text{t-rank}(T_\varepsilon) < \text{t-rank}(T) \) for all \( \varepsilon > 0 \), we say that the t-rank exhibits a gap between rank and border rank. This indicates that while the rank of approximating tensors may be strictly lower, the rank of the limiting tensor \( T \) remains higher, revealing a structural discontinuity in the behavior of the t-rank.

In this work, we analyze different positive tensor network decompositions and investigate their ranks in relation to this phenomenon, examining how the t-rank behaves under such approximations.

Popular summary

Many complex systems, from quantum mechanics to machine learning, rely on tensors to describe interactions between components. A key measure of complexity is the tensor rank, which represents the minimum number of simpler building blocks (elementary tensors) needed to reconstruct a tensor. Unlike matrix rank, tensor rank is not stable under approximations—it can suddenly drop under arbitrarily small perturbations, leading to the concept of border rank, which reflects this limit under approximation.

In this work, we prove that this collapse phenomenon also occurs in positive tensor decompositions, which play a key role in probability theory and quantum information. We show that for several well-known tensors, the border rank is strictly smaller than the actual rank, revealing a fundamental gap. This effect extends beyond standard decompositions to positive tensor network representations, such as Matrix Product Density Operators and the Local Purification form, which are widely used in quantum many-body physics and statistical mechanics.

This collapse has significant consequences: for instance, certain sets of probability distributions used to model correlations in physics and statistics are not closed. This means that even if a distribution can be approximated arbitrarily well by simpler ones, it may not belong to the set itself.

We further analyze different types of tensor decompositions and show that this rank gap persists even when additional constraints, such as symmetry or positivity, are imposed. Our findings suggest that rank-based optimization techniques may be inherently unstable in some settings, as small perturbations can drastically alter the complexity of a decomposition.

► BibTeX data

@article{Klingler2025borderranksof,
  doi = {10.22331/q-2025-02-26-1649},
  url = {https://doi.org/10.22331/q-2025-02-26-1649},
  title = {Border {R}anks of {P}ositive and {I}nvariant {T}ensor {D}ecompositions: {A}pplications to {C}orrelations},
  author = {Klingler, Andreas and Netzer, Tim and De les Coves, Gemma},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1649},
  month = feb,
  year = {2025}
}

► References

[1] D. Bini, G. Lotti, and F. Romani. ``Approximate solutions for the bilinear form computational problem''. SIAM J. Comput. 9, 692–697 (1980).
https://doi.org/10.1137/0209053

[2] J. M. Landsberg. ``Tensors: Geometry and applications''. Volume 128. American Mathematical Soc. (2011).
https://doi.org/10.1090/gsm/128

[3] T. Barthel, J. Lu, and G. Friesecke. ``On the closedness and geometry of tensor network state sets''. Lett. Math. Phys. 112, 72 (2022).
https://doi.org/10.1007/s11005-022-01552-z

[4] M. Christandl, A. Lucia, P. Vrana, and A. H. Werner. ``Tensor network representations from the geometry of entangled states''. SciPost Phys. 9, 1–35 (2020).
https://doi.org/10.21468/SCIPOSTPHYS.9.3.042

[5] J. M. Landsberg, Y. Qi, and K. Ye. ``On the geometry of tensor network states''. Quantum Inf. Comput. 12, 346–354 (2012).
https://doi.org/10.26421/qic12.3-4-12

[6] V. De Silva and L. H. Lim. ``Tensor rank and the ill-posedness of the best low-rank approximation problem''. SIAM J. Matrix Anal. Appl. 30, 1084–1127 (2008).
https://doi.org/10.1137/06066518X

[7] J. M. Landsberg and Mateusz Michałek. ``Abelian tensors''. Journal de Mathématiques Pures et Appliquées 108, 333–371 (2017).
https://doi.org/10.1016/j.matpur.2016.11.004

[8] J. Zuiddam. ``A note on the gap between rank and border rank''. Linear Algebra Appl. 525, 33–44 (2017).
https://doi.org/10.1016/j.laa.2017.03.015

[9] M. Christandl, F. Gesmundo, D. Stilck França, and A. H. Werner. ``Optimization at the boundary of the tensor network variety''. Phys. Rev. B 103, 1–9 (2021).
https://doi.org/10.1103/PhysRevB.103.195139

[10] P. Comon, L.-H. Lim, Y. Qi, and K. Ye. ``Topology of tensor ranks''. Adv. Math. 367, 107128 (2020).
https://doi.org/10.1016/j.aim.2020.107128

[11] C. Beltrán, P. Breiding, and N. Vannieuwenhoven. ``The average condition number of most tensor rank decomposition problems is infinite''. Found. Comp. Math. 23, 433–491 (2023).
https://doi.org/10.1007/s10208-022-09551-1

[12] G. De las Cuevas, T. S. Cubitt, J. I. Cirac, M. M. Wolf, and D. Pérez-García. ``Fundamental limitations in the purifications of tensor networks''. J. Math. Phys. 57, 071902 (2016).
https://doi.org/10.1063/1.4954983

[13] M. Kliesch, D. Gross, and J. Eisert. ``Matrix-product operators and states: NP-hardness and undecidability''. Phys. Rev. Lett. 113, 160503 (2014).
https://doi.org/10.1103/PhysRevLett.113.160503

[14] G. De las Cuevas, N. Schuch, D. Pérez-García, and J.I. Cirac. ``Purifications of multipartite states: Limitations and constructive methods''. New J. Phys. 15, 123021 (2013).
https://doi.org/10.1088/1367-2630/15/12/123021

[15] G. De las Cuevas and T. Netzer. ``Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices''. J. Math. Phys. 61, 41901 (2020).
https://doi.org/10.1063/1.5127668

[16] G. De las Cuevas, M. Hoogsteder Riera, and T. Netzer. ``Tensor decompositions on simplicial complexes with invariance''. J. Symb. Comput. 124, 102299 (2024).
https://doi.org/10.1016/j.jsc.2024.102299

[17] H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, and R. R. Thomas. ``Positive semidefinite rank''. Math. Program. 153, 133–177 (2015).
https://doi.org/10.1007/s10107-015-0922-1

[18] R. Jain, Y. Shi, Z. Wei, and S. Zhang. ``Efficient protocols for generating bipartite classical distributions and quantum states''. IEEE Trans. Inf. Theory 59, 5171–5178 (2013).
https://doi.org/10.1109/TIT.2013.2258372

[19] I. Glasser, R. Sweke, N. Pancotti, J. Eisert, and J. I. Cirac. ``Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden markov models to quantum machine learning''. Adv. NeurIPS 32, 1498–1510 (2019).
https://doi.org/10.48550/arXiv.1907.03741

[20] M. Yannakakis. ``Expressing combinatorial optimization problems by linear programs''. J. Comput. System Sci. 43, 441–466 (1991).
https://doi.org/10.1016/0022-0000(91)90024-Y

[21] J. Gouveia, P. A. Parrilo, and R. R. Thomas. ``Lifts of convex sets and cone factorizations''. Math. Oper. Res. 38, 248–264 (2013).
https://doi.org/10.1287/moor.1120.0575

[22] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. De Wolf. ``Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds''. Proc. ACM Symp. Theory of Computing (2012).
https://doi.org/10.1145/2213977.2213988

[23] R. Jain, Z. Wei, P. Yao, and S. Zhang. ``Multipartite quantum correlation and communication complexities''. Comput. Complexity 26, 199–228 (2017).
https://doi.org/10.1007/s00037-016-0126-y

[24] J. E. Cohen and U. G. Rothblum. ``Nonnegative ranks, decompositions, and factorizations of nonnegative matrices''. Linear Algebra Appl. 190, 149–168 (1993).
https://doi.org/10.1016/0024-3795(93)90224-C

[25] D. Pérez-García, F. Verstraete, M. M. Wolf, and J. I. Cirac. ``Matrix product state representations''. Quantum Inf. Comput. 7, 401–430 (2007).
https://doi.org/10.26421/qic7.5-6-1

[26] K. Temme and F. Verstraete. ``Stochastic matrix product states''. Phys. Rev. Lett. 104, 210502 (2010).
https://doi.org/10.1103/PhysRevLett.104.210502

[27] A. Fawzi et al. ``Discovering faster matrix multiplication algorithms with reinforcement learning''. Nature 610, 47–53 (2022).
https://doi.org/10.1038/s41586-022-05172-4

[28] G. De las Cuevas, A. Klingler, and T. Netzer. ``Approximate tensor decompositions: disappearance of many separations''. J. Math. Phys. 62, 093502 (2021).
https://doi.org/10.1063/5.0033876

[29] C. Eckart and G. Young. ``The approximation of one matrix by another of lower rank''. Psychometrika 1, 211–218 (1936).
https://doi.org/10.1007/BF02288367

[30] Y. Qi, P. Comon, and L. H. Lim. ``Semialgebraic geometry of nonnegative tensor rank''. SIAM J. Matrix Anal. 37, 1556–1580 (2016).
https://doi.org/10.1137/16M1063708

[31] J. J. Sylvester. ``On the principles of the calculus of forms''. Cambridge and Dublin Math. J. 7, 52–97 (1852).
https://doi.org/10.1017/CBO9781139151078.009

[32] G. Comas and M. Seiguer. ``On the rank of a binary form''. Found. Comput. Math. 11, 65–78 (2011).
https://doi.org/10.1007/s10208-010-9077-x

[33] E. Ballico and A. Bernardi. ``Tensor ranks on tangent developable of segre varieties''. Linear Multilinear Algebra 61, 881–894 (2013).
https://doi.org/10.1080/03081087.2012.716430

[34] L. H. Lim and P. Comon. ``Nonnegative approximations of nonnegative tensors''. J. Chemom. 23, 432–441 (2009).
https://doi.org/10.1002/cem.1244

[35] M. Sanz, D. Pérez-García, M. M. Wolf, and J. I. Cirac. ``A quantum version of Wielandt's inequality''. IEEE Trans. Inf. Theory 56, 4668–4673 (2010).
https://doi.org/10.1109/TIT.2010.2054552

[36] G. De las Cuevas, J. I. Cirac, N. Schuch, and D. Pérez-García. ``Irreducible forms of matrix product states: Theory and applications''. J. Math. Phys. 58, 121901 (2017).
https://doi.org/10.1063/1.5000784

[37] A. Schönhage. ``Partial and total matrix multiplication''. SIAM J.Comput. 10, 434–455 (1981).
https://doi.org/10.1137/0210032

[38] Y. Shitov. ``Counterexamples to Strassen’s direct sum conjecture''. Acta Math. 222, 363–379 (2019).
https://doi.org/10.4310/ACTA.2019.v222.n2.a3

[39] M. Christandl, F. Gesmundo, M. Michałek, and J. Zuiddam. ``Border rank nonadditivity for higher order tensors''. SIAM J. Matrix Anal. Appl. 42, 503–527 (2021).
https://doi.org/10.1137/20M1357366

[40] M. Christandl, A. K. Jensen, and J. Zuiddam. ``Tensor rank is not multiplicative under the tensor product''. Linear Algebra Appl. 543, 125–139 (2018).
https://doi.org/10.1016/j.laa.2017.12.020

[41] M. Christandl, F. Gesmundo, and A. K. Jensen. ``Border rank is not multiplicative under the tensor product''. SIAM J. Appl. Algebra Geom. 3, 231–255 (2019).
https://doi.org/10.1137/18M1174829

[42] G. De las Cuevas, A. Klingler, and T. Netzer. ``Polynomial decompositions with invariance and positivity inspired by tensors''. Linear Algebra Appl. 698, 537–588 (2024).
https://doi.org/10.1016/j.laa.2024.05.025

[43] J. I. Cirac, D. Pérez-García, N. Schuch, and F. Verstraete. ``Matrix product states and projected entangled pair states: Concepts, symmetries, and theorems''. Rev. Mod. Phys. 93, 045003 (2021).
https://doi.org/10.1103/RevModPhys.93.045003

[44] M. Christandl, P. Vrana, and J. Zuiddam. ``Asymptotic tensor rank of graph tensors: beyond matrix multiplication''. Computational Complexity 28, 57–111 (2019).
https://doi.org/10.1007/s00037-018-0172-8

[45] R. A. Horn and C. R. Johnson. ``Matrix analysis''. Cambridge University Press. (1985). 2nd edition.
https://doi.org/10.1017/cbo9780511810817

[46] C. Bocci, E. Carlini, and F. Rapallo. ``Perturbation of matrices and nonnegative rank with a view toward statistical models''. SIAM J. Matrix Anal. Appl. 32, 1500–1512 (2011).
https://doi.org/10.1137/110825455

[47] G. H. Golub and C. F. Van Loan. ``Matrix computations''. Johns Hopkins University Press. (1996). 3rd edition.
https://doi.org/10.56021/9781421407944

[48] R. Orús. ``A practical introduction to tensor networks: Matrix product states and projected entangled pair states''. Ann. Physics 349, 117–158 (2014).
https://doi.org/10.1016/j.aop.2014.06.013

Cited by

[1] Lisa T. Weinbrenner and Otfried Gühne, "Quantifying entanglement from the geometric perspective", Europhysics Letters 151 6, 68001 (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-11 23:03:01). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2026-08-11 23:03:01).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.