  We propose new Riemannian preconditioned algorithms for low-rank tensor
completion via the polyadic decomposition of a tensor. These algorithms exploit
a non-Euclidean metric on the product space of the factor matrices of the
low-rank tensor in the polyadic decomposition form. This new metric is designed
using an approximation of the diagonal blocks of the Hessian of the tensor
completion cost function, thus has a preconditioning effect on these
algorithms. We prove that the proposed Riemannian gradient descent algorithm
globally converges to a stationary point of the tensor completion problem, with
convergence rate estimates using the $\L{}$ojasiewicz property. Numerical
results on synthetic and real-world data suggest that the proposed algorithms
are more efficient in memory and time compared to state-of-the-art algorithms.
Moreover, the proposed algorithms display a greater tolerance for overestimated
rank parameters in terms of the tensor recovery performance, thus enable a
flexible choice of the rank parameter.
