  There has been continued interest in seeking a theorem describing optimal
low-rank approximations to tensors of order 3 or higher, that parallels the
Eckart-Young theorem for matrices. In this paper, we argue that the naive
approach to this problem is doomed to failure because, unlike matrices, tensors
of order 3 or higher can fail to have best rank-r approximations. The
phenomenon is much more widespread than one might suspect: examples of this
failure can be constructed over a wide range of dimensions, orders and ranks,
regardless of the choice of norm (or even Bregman divergence). Moreover, we
show that in many instances these counterexamples have positive volume: they
cannot be regarded as isolated phenomena. In one extreme case, we exhibit a
tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The
notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors.
In a more positive spirit, we propose a natural way of overcoming the
ill-posedness of the low-rank approximation problem, by using weak solutions
when true solutions do not exist. In our work we emphasize the importance of
closely studying concrete low-dimensional examples as a first step towards more
general results. To this end, we present a detailed analysis of equivalence
classes of 2-by-2-by-2 tensors, and we develop methods for extending results
upwards to higher orders and dimensions. Finally, we link our work to existing
studies of tensors from an algebraic geometric point of view. The rank of a
tensor can in theory be given a semialgebraic description; i.e., can be
determined by a system of polynomial inequalities. In particular we make
extensive use of the 2-by-2-by-2 hyperdeterminant.
