# Approximate Real Symmetric Tensor Rank

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 25 Jul 2022.

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

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Tensor Methods in Computer Vision and Deep Learning](https://mlsanity.com/paper/2107.03436/) (2021)
- [Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithm](https://mlsanity.com/paper/1911.04415/) (2019)
- [Robust and Resource Efficient Identification of Two Hidden Layer Neural Networks](https://mlsanity.com/paper/1907.00485/) (2019)
- [Landscape analysis of an improved power method for tensor decomposition](https://mlsanity.com/paper/2110.15821/) (2021)
- [The sum-of-squares hierarchy on the sphere, and applications in quantum information theory](https://mlsanity.com/paper/1908.05155/) (2019)
- [On the Nuclear Norm and the Singular Value Decomposition of Tensors](https://mlsanity.com/paper/1308.3860/) (2013)
- [Symmetric Tensor Nuclear Norms](https://mlsanity.com/paper/1605.08823/) (2016)
- [Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carath'eodory's Theorem](https://mlsanity.com/paper/1406.2296/) (2014)
- [Approximating Nonnegative Polynomials via Spectral Sparsification](https://mlsanity.com/paper/1612.06245/) (2016)
- [Waring Rank, Parameterized and Exact Algorithms](https://mlsanity.com/paper/1807.06194/) (2018)
- [Approximate tensor decompositions: disappearance of many separations](https://mlsanity.com/paper/2004.10219/) (2020)
- [Functional norms, condition numbers and numerical algorithms in algebraic geometry](https://mlsanity.com/paper/2102.11727/) (2021)
- [Harmonic Hierarchies for Polynomial Optimization](https://mlsanity.com/paper/2202.12865/) (2022)

## Abstract (arXiv)

We investigate the effect of an varepsilon-room of perturbation tolerance on symmetric tensor decomposition. To be more precise, suppose a real symmetric d-tensor f, a norm ||.|| on the space of symmetric d-tensors, and varepsilon >0 are given. What is the smallest symmetric tensor rank in the varepsilon-neighborhood of f? In other words, what is the symmetric tensor rank of f after a clever varepsilon-perturbation? We prove two theorems and develop three corresponding algorithms that give constructive upper bounds for this question. With expository goals in mind; we present probabilistic and convex geometric ideas behind our results, reproduce some known results, and point out open problems.