Faster search for tensor decomposition over finite fields

Abstract

We present an $O^{\ast }(|\mathbb{F}{|}^{\min \left\{R,{\sum }_{d\ge 2}{n}_d\right\}+(R-n_0)({\sum }_{d\ne 0}{n}_d)})$-time algorithm for determining whether the rank of a concise tensor $T\in {\mathbb{F}}^{n_0\times \cdots \times n_{D-1}}$ is $\le R$, assuming $n_0\ge \cdots \ge n_{D-1}$ and $R\ge n_0$. For 3-dimensional tensors, we have a second algorithm running in $O^{\ast }(|\mathbb{F}{|}^{n_0+n_2+(R-n_0+1-r_{\ast })(n_1+n_2)+r_{\ast }^2})$ time, where $r_{\ast }:=\lfloor \frac{R}{n_0}\rfloor +1$. Both algorithms use polynomial space and improve on our previous work, which achieved running time $O^{\ast }(|\mathbb{F}{|}^{n_0+(R-n_0)({\sum }_d{n}_d)})$.

14 pages