A06 Tensor theta norms and low rank recovery

This project investigates an algorithmic approach for the recovery of low rank tensors from incomplete random linear measurements. It is well-known that nuclear norm minimization can provably recover low rank matrices from an optimal number of measurements. Unfortunately, the tensor nuclear norm is NP-hard to compute for tensors of order three or higher. We will therefore consider computable relaxations of the tensor nuclear norm based on theta bodies, a concept from convex algebraic geometry. We aim at proving optimal bounds on the number of required random measurements for successful recovery.