  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.
