Reference : Low-rank optimization with trace norm penalty
E-prints/Working papers : Already available on another site
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/112300
Low-rank optimization with trace norm penalty
English
Mishra, Bamdev mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Meyer, Gilles mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Bach, Francis [INRIA - SIERRA project-team - Ecole Normale Supérieure de Paris > Laboratoire d'Informatique > > >]
Sepulchre, Rodolphe mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
2012
No
[en] low-rank ; trace norm ; geometric optimization algorithms
[en] 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 still maintaining complexity that is linear in the number of rows of the matrix. To compute a set of solutions efficiently for a grid of regularization parameters we propose a predictor-corrector approach on the quotient manifold that outperforms the naive warm-restart approach. The performance of the proposed algorithm is illustrated on problems of low-rank matrix completion and multivariate linear regression.
http://hdl.handle.net/2268/112300
Submitted to SIAM Journal on Optimization (SIOPT)
http://arxiv.org/abs/1112.2318

There is no file associated with this reference.

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.