The paper addresses the problem of low-rank trace norm minimization. We
propose an algorithm that alternates between fixed-rank optimization and
rank-one updates. The fixed-rank optimization is characterized by an efficient
factorization that makes the trace norm differentiable in the search space and
the computation of duality gap numerically tractable. The search space is
nonlinear but is equipped with a particular Riemannian structure that leads to
efficient computations. We present a second-order trust-region algorithm with a
guaranteed quadratic rate of convergence. Overall, the proposed optimization
scheme converges super-linearly to the global solution while maintaining
complexity that is linear in the number of rows and columns of the matrix. To
compute a set of solutions efficiently for a grid of regularization parameters
we propose a predictor-corrector approach that outperforms the naive
warm-restart approach on the fixed-rank quotient manifold. The performance of
the proposed algorithm is illustrated on problems of low-rank matrix completion
and multivariate linear regression.

本文提出一种通过交替固定秩优化与秩一更新来解决低秩矩阵迹范数最小化问题的算法，针对具有理曼结构的非线性搜索空间，利用有效的因子分解实现了迹范数在搜索空间的可微以及对偶间隙的数值计算可行，提出了一个拥有保证二次收敛速度的二阶信任域算法，并以低秩矩阵完成和多元线性回归问题为例说明了该算法的性能。