期刊
SIAM JOURNAL ON OPTIMIZATION
卷 23, 期 4, 页码 2124-2149出版社
SIAM PUBLICATIONS
DOI: 10.1137/110859646
关键词
trace norm; Riemannian optimization; trust region; regularization path; predictor-corrector on quotient manifold; matrix completion; multivariate linear regression
资金
- Interuniversity Attraction Poles Programme
- Belgian State, Science Policy Office
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 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 superlinearly 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据