  We consider the tensor completion problem of predicting the missing entries
of a tensor. The commonly used CP model has a triple product form, but an
alternate family of quadratic models, which are the sum of pairwise products
instead of a triple product, have emerged from applications such as
recommendation systems. Non-convex methods are the method of choice for
learning quadratic models, and this work examines their sample complexity and
error guarantee. Our main result is that with the number of samples being only
linear in the dimension, all local minima of the mean squared error objective
are global minima and recover the original tensor. We substantiate our
theoretical results with experiments on synthetic and real-world data, showing
that quadratic models have better performance than CP models where there are a
limited amount of observations available.
