Recovery Guarantees for Quadratic Tensors with Sparse Observations
This provides a theoretical guarantee for non-convex methods in tensor completion, which is useful for applications like recommendation systems, though it is incremental as it builds on existing quadratic models.
The paper tackles the tensor completion problem using quadratic models, showing that with a linear number of samples, all local minima are global minima and recover the original tensor, with experiments demonstrating better performance than CP models on limited data.
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.