Tensor Completion with Nearly Linear Samples Given Weak Side Information
This addresses the computational-statistical gap in tensor completion for machine learning and data analysis, offering a significant reduction in sample requirements with minimal side information, though it is incremental in leveraging existing tensor methods.
The paper tackles the high sample complexity required for tensor completion by showing that weak side information, such as non-orthogonal weight vectors for each mode, reduces the sample complexity from O(n^{t/2}) to O(n^{1+κ}) for consistent estimation, with experiments validating this on synthetic and real-world datasets.
Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only $Θ(tn)$ degrees of freedom in a $t$-order tensor with $n^t$ entries, the best known polynomial time algorithm requires $O(n^{t/2})$ samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to $O(n)$. The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with $O(n^{1+κ})$ samples for any small constant $κ> 0$. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights.