Author

Alperen A. Ergür, Jesus Rebollo Bueno, Petros Valettas

Category

math.NA

Date Published

2022/07/25

Date Retrieved

2022/08/02

Date Updated

2022/08/02

Description

We investigate the effect of an $\varepsilon$-room of perturbation tolerance
on symmetric tensor decomposition from an algorithmic perspective. More
precisely, we prove theorems and design algorithms for the following problem:
Suppose a real symmetric $d$-tensor $f$, a norm $||.||$ on the space of
symmetric $d$-tensors, and $\varepsilon >0$ error tolerance with respect to
$||.||$ 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 provide two different
theoretical bounds and three algorithms for approximate symmetric tensor rank
estimation. Our first result is a randomized energy increment algorithm for the
case of $L_p$-norms. Our second result is a simple sampling-based algorithm,
inspired by some techniques in geometric functional analysis, that works for
any norm. We also provide a supplementary algorithm in the case of the
Hilbert-Schmidt norm. All our algorithms come with rigorous complexity
estimates, which in turn yield our two main theorems on symmetric tensor rank
with $\varepsilon$-room of tolerance. We also report on our experiments with a
preliminary implementation of the energy increment algorithm.

Posts

12

Readers

0

Score

1.75

Tweeters

6

URL

https://arxiv.org/pdf/2207.12529.pdf

TOP