  We consider the Principal Component Analysis problem for large tensors of
arbitrary order $k$ under a single-spike (or rank-one plus noise) model. On the
one hand, we use information theory, and recent results in probability theory,
to establish necessary and sufficient conditions under which the principal
component can be estimated using unbounded computational resources. It turns
out that this is possible as soon as the signal-to-noise ratio $\beta$ becomes
larger than $C\sqrt{k\log k}$ (and in particular $\beta$ can remain bounded as
the problem dimensions increase).
  On the other hand, we analyze several polynomial-time estimation algorithms,
based on tensor unfolding, power iteration and message passing ideas from
graphical models. We show that, unless the signal-to-noise ratio diverges in
the system dimensions, none of these approaches succeeds. This is possibly
related to a fundamental limitation of computationally tractable estimators for
this problem.
  We discuss various initializations for tensor power iteration, and show that
a tractable initialization based on the spectrum of the matricized tensor
outperforms significantly baseline methods, statistically and computationally.
Finally, we consider the case in which additional side information is available
about the unknown signal. We characterize the amount of side information that
allows the iterative algorithms to converge to a good estimate.
