It is known that the complexity of computing the rank of d-tensor and
its best rank one approximation is NP-hard over the complex numbers for
d 3. But what are the known upper bounds for the bit complexity of these
quantities for general and symmetric tensors? We claim that these problems
are hard to compute because they are intimately related to solubility of system
of polynomial equations.
We rst will discuss the recent results in [2] which shows that if we x the
dimension n of a symmetric d-tensor then the bit complexity of computation
of best rank one symmetric approximation of a symmetric tensor is of at most
of order O(d8n). For qubits (n=2) the bit complexity is O(d8).
We second discuss how to convert the problem of finding whether a rank of
a given d-tensor is at most r equivalent to a nonsolubility of a system of linear
equations with many variables. The upper bound on complexity is O(d3d2r4
).
References
[1] M. Aliabadi and S. Friedland, On the complexity of finding tensor ranks,
to appear in Communications on Applied Mathematics and Computation,
arXiv:2002.07151.
[2] S. Friedland and L. Wang, Spectral norm of a symmetric tensor and its
computation, Mathematics of Computation, 89 (2020)., 2175-2215.
Copyright. All Rights Reserved.