Statistical Performance of Convex Tensor Decomposition

Abstract

We analyze the statistical performance of a recently proposed convex tensor de-composition algorithm. Conventionally tensor decomposition has been formu-lated as non-convex optimization problems, which hindered the analysis of their performance. We show under some conditions that the mean squared error of the convex method scales linearly with the quantity we call the normalized rank of the true tensor. The current analysis naturally extends the analysis of convex low-rank matrix estimation to tensors. Furthermore, we show through numerical experiments that our theory can precisely predict the scaling behaviour in practice. 1