Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
This work addresses tensor completion for data analysis, offering an incremental improvement by incorporating incoherence to potentially enhance recovery over standard methods.
The paper tackles the problem of higher-order tensor completion by introducing incoherent tensor norms, showing that a kth-order tensor of rank r and dimension d can be perfectly recovered from O((r^{(k-1)/2}d^{3/2}+r^{k-1}d)(log(d))^2) uniformly sampled entries.
In this paper, we investigate the sample size requirement for a general class of nuclear norm minimization methods for higher order tensor completion. We introduce a class of tensor norms by allowing for different levels of coherence, which allows us to leverage the incoherence of a tensor. In particular, we show that a $k$th order tensor of rank $r$ and dimension $d\times\cdots\times d$ can be recovered perfectly from as few as $O((r^{(k-1)/2}d^{3/2}+r^{k-1}d)(\log(d))^2)$ uniformly sampled entries through an appropriate incoherent nuclear norm minimization. Our results demonstrate some key differences between completing a matrix and a higher order tensor: They not only point to potential room for improvement over the usual nuclear norm minimization but also highlight the importance of explicitly accounting for incoherence, when dealing with higher order tensors.