Provable Tensor Ring Completion
This addresses tensor completion for multi-dimensional data analysis, with incremental improvements in recovery guarantees and performance.
The paper tackles the problem of tensor completion using tensor ring decomposition, proving that a d-order tensor can be exactly recovered with high probability from n^{d/2} r^2 ln^7(n^{d/2}) samples via convex optimization, and experiments show improved performance over state-of-the-art methods.
Tensor completion recovers a multi-dimensional array from a limited number of measurements. Using the recently proposed tensor ring (TR) decomposition, in this paper we show that a d-order tensor of dimensional size n and TR rank r can be exactly recovered with high probability by solving a convex optimization program, given n^{d/2} r^2 ln^7(n^{d/2})samples. The proposed TR incoherence condition under which the result holds is similar to the matrix incoherence condition. The experiments on synthetic data verify the recovery guarantee for TR completion. Moreover, the experiments on real-world data show that our method improves the recovery performance compared with the state-of-the-art methods.