  We consider the problem of finding the smallest or largest entry of a tensor
of order N that is specified via its rank decomposition. Stated in a different
way, we are given N sets of R-dimensional vectors and we wish to select one
vector from each set such that the sum of the Hadamard product of the selected
vectors is minimized or maximized. We show that this fundamental tensor problem
is NP-hard for any tensor rank higher than one, and polynomial-time solvable in
the rank-one case. We also propose a continuous relaxation and prove that it is
tight for any rank. For low-enough ranks, the proposed continuous reformulation
is amenable to low-complexity gradient-based optimization, and we propose a
suite of gradient-based optimization algorithms drawing from projected gradient
descent, Frank-Wolfe, or explicit parametrization of the relaxed constraints.
We also show that our core results remain valid no matter what kind of polyadic
tensor model is used to represent the tensor of interest, including Tucker,
HOSVD/MLSVD, tensor train, or tensor ring. Next, we consider the class of
problems that can be posed as special instances of the problem of interest. We
show that this class includes the partition problem (and thus all NP-complete
problems via polynomial-time transformation), integer least squares, integer
linear programming, integer quadratic programming, sign retrieval (a special
kind of mixed integer programming / restricted version of phase retrieval), and
maximum likelihood decoding of parity check codes. We demonstrate promising
experimental results on a number of hard problems, including state-of-art
performance in decoding low density parity check codes and general parity check
codes.
