Approximate Real Symmetric Tensor Rank

Abstract

We investigate the effect of an -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 >0 are given. What is the smallest symmetric tensor rank in the -neighborhood of f? In other words, what is the symmetric tensor rank of f after a clever -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.

Tasks

Reproductions