# Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond

arXiv: https://arxiv.org/abs/2212.03851 · HTML: https://mlsanity.com/paper/2212.03851/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 80 references that are in the map.
- First posted on arXiv 7 Dec 2022.

## Builds on (most cited first, 11 of 11)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Spectral Learning on Matrices and Tensors](https://mlsanity.com/paper/2004.07984/) (2020)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [Fourier PCA and Robust Tensor Decomposition](https://mlsanity.com/paper/1306.5825/) (2013)
- [Quantum entanglement, sum of squares, and the log rank conjecture](https://mlsanity.com/paper/1701.06321/) (2017)
- [On cap sets and the group-theoretic approach to matrix multiplication](https://mlsanity.com/paper/1605.06702/) (2016)
- [Overcomplete order-3 tensor decomposition, blind deconvolution and Gaussian mixture models](https://mlsanity.com/paper/2007.08133/) (2020)
- [Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time](https://mlsanity.com/paper/1912.08805/) (2019)

## Built on by (most cited first, 2 of 2)

- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)
- [Tensor-based second-order causal discovery](https://mlsanity.com/paper/2606.18074/) (2026)

## Abstract (arXiv)

We study the problem of finding elements in the intersection of an arbitrary conic variety in mathbbFn with a given linear subspace (where mathbbF can be the real or complex field). This problem captures a rich family of algorithmic problems under different choices of the variety. The special case of the variety consisting of rank-1 matrices already has strong connections to central problems in different areas like quantum information theory and tensor decompositions. This problem is known to be NP-hard in the worst case, even for the variety of rank-1 matrices. Surprisingly, despite these hardness results we develop an algorithm that solves this problem efficiently for "typical" subspaces. Here, the subspace U subseteq mathbbFn is chosen generically of a certain dimension, potentially with some generic elements of the variety contained in it. Our main result is a guarantee that our algorithm recovers all the elements of U that lie in the variety, under some mild non-degeneracy assumptions on the variety. As corollaries, we obtain the following new results: bullet Polynomial time algorithms for several entangled subspaces problems in quantum entanglement, including determining r-entanglement, complete entanglement, and genuine entanglement of a subspace. While all of these problems are NP-hard in the worst case, our algorithm solves them in polynomial time for generic subspaces of dimension up to a constant multiple of the maximum possible. bullet Uniqueness results and polynomial time algorithmic guarantees for generic instances of a broad class of low-rank decomposition problems that go beyond tensor decompositions. Here, we recover a decomposition of the form sumi=1R vi otimes wi, where the vi are elements of the variety X. This implies new uniqueness results and genericity guarantees even in the special case of tensor decompositions.