A dual framework for low-rank tensor completion
One of the popular approaches for low-rank tensor completion is to use the latent trace norm regularization. However, most existing works in this direction learn a sparse combination of tensors. In this work, we fill this gap by proposing a variant of the latent trace norm that helps in learning a non-sparse combination of tensors. We develop a dual framework for solving the low-rank tensor completion problem. We first show a novel characterization of the dual solution space with an interesting factorization of the optimal solution. Overall, the optimal solution is shown to lie on a Cartesian product of Riemannian manifolds. Furthermore, we exploit the versatile Riemannian optimization framework for proposing computationally efficient trust region algorithm. The experiments illustrate the efficacy of the proposed algorithm on several real-world datasets across applications.
The article focus on tensor completion by trace-norm regularization. In this approach, tensor with missing data are completed with a decomposition as a sum of K low-rank tensors. The rank of each of these tensor components is not fixed but constrained by a trace-norm regularization on the specific matricized form of each tensor (so tensor component K will be constrained to have a low-rank k-mode matricization). The main contribution is to propose another regularization than latent-trace norm which tends to eliminate components, thus enabling a non-sparse decomposition.  The proposed trace norm regularizer can be rewritten through variational characterization as the solution of a minimization problem on the space of positive semi-definite matrices with unit trace (defined as the spectrahedron manifold in Journée at al./2008)  and two novel formulations whose main interests are to depends on only one dual tensor (compared to K components) and K matrices are presented. As the matrices belongs to the spectrahedron manifold, they can be parametrized through a product of a fixed-rank matrices (whose frobenius norm is 1) with any element of the orthogonal group. As a consequence,  the fixed-parameters problems should  be solved through optimization on a quotient manifold. Here a Trust-Region (second order) algorithm is chosen which necessitates the computation of the Riemannian gradient, the Riemannian hessian and a retraction operator. All elements are provided and detailed in the supplementary material.  Last, several experiments (color image completion, link prediction, movie recommendation) are presented that shows the general efficiency of the method. There are some missing details like the chosen ranks of the parametrization of the spectrahedron matrices which could influence the effectiveness of the method. However as codes are provided, the reproductivity of some of the  experiments is possible.  My main complaint with this work is: as this works focus in tensor completion, it eschews to bring into the light its relationship with matrix completion methods. In particular, there are a lot of elements in common with the recent (ICML’18) work  [P. Jawanpuria and B. Mishra. A Unified framework for structured low-rank matrix learning. International Conference on Machine Learning, 2018.] (cited in the text as [17]). In particular, the dual trick, the main Riemannian components necessary for the Trust Region implementation (projections, retraction) are the same.  Another remark is that the use of trace-norm regularization enables to not specify the ranks of each components of the decomposition, whereas the chosen parametrization of the elements of the spectrahedron manifold makes the choice of ranks of the matrix again necessary.   A summary is that the addressed problem is interesting, the algorithms proposed make a good use of the Riemannian framework and the experiments are good. The main negative point is that the contributions of this work may rely a lot to similar work on matricial decomposition