  We study extensions of compressive sensing and low rank matrix recovery to
the recovery of low rank tensors from incomplete linear information. While the
reconstruction of low rank matrices via nuclear norm minimization is rather
well-understand by now, almost no theory is available for the extension to
higher order tensors due to various theoretical and computational difficulties
arising for tensor decompositions. In fact, nuclear norm minimization for
matrix recovery is a tractable convex relaxation approach, but the extension of
the nuclear norm to tensors is in general NP-hard to compute. In this article,
we introduce convex relaxations of the tensor nuclear norm which are computable
in polynomial time via semidefinite programming. Our approach is based on theta
bodies, a concept from computational algebraic geometry similar to the Lasserre
relaxations. We introduce polynomial ideals which are generated by the second
order minors corresponding to different matricizations of the tensor (where the
tensor entries are treated as variables) such that the nuclear norm ball is the
convex hull of the algebraic variety of the ideal. The $k$-th theta body for
such an ideal generates a new norm which we call the $\theta_k$-norm. We show
that in the matrix case, these norms reduce to the nuclear norm. For tensors of
order $d \geq 3$ however, we obtain new norms. The sequence of the
corresponding unit-$\theta_k$-norm balls converges asymptotically to the unit
tensor nuclear norm ball. By providing the Gr\"obner basis for the ideals, we
explicitly give semidefinite programs for the computation of the
$\theta_k$-norm and for the minimization of the $\theta_k$-norm under an affine
constraint. Numerical experiments for order-3 tensor recovery via
$\theta_1$-norm minimization suggest that our approach successfully
reconstructs tensors of low rank from incomplete linear (random) measurements.
