Volume: 43 • Number: 2 • Pages: 840-866

We propose new Riemannian preconditioned algorithms for low-rank tensor comple-tion via the polyadic decomposition of a tensor. These algorithms exploit a non-Euclidean metric onthe 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 thetensor completion cost function and thus has a preconditioning effect on these algorithms. We provethat the proposed Riemannian gradient descent algorithm globally converges to a stationary pointof the tensor completion problem, with convergence rate estimates using the \Lojasiewicz property.Numerical results on synthetic and real-world data suggest that the proposed algorithms are moreefficient in memory and time compared to state-of-the-art algorithms. Moreover, the proposed algo-rithms display a greater tolerance for overestimated rank parameters in terms of the tensor recoveryperformance and thus enable a flexible choice of the rank parameter.