Recovery of third order tensors via convex optimization

We study recovery of low-rank third order tensors from underdetermined linear measurements. This natural extension of low-rank matrix recovery via nuclear norm minimization is challenging since the tensor nuclear norm is in general intractable to compute. To overcome this obstacle we introduce hierarchical closed convex relaxations of the tensor unit nuclear norm ball based on so-called theta bodies - a recent concept from computational algebraic geometry. Our tensor recovery procedure consists in minimization of the resulting new norms subject to the linear constraints. Numerical results on recovery of third order low-rank tensors show the effectiveness of this new approach.