Trace norm regularization

Low-rank optimization with trace norm penalty

Authors

B. Mishra, G. Meyer, F. Bach, and R. Sepulchre

Abstract

Problems of the form f(X) + λ||X||_* are tackled, where f is a smooth convex function, ||X||_* is the trace (or nuclear) norm of X, and λ >= 0 is a regularization parameter.

The paper addresses the problem of low-rank trace norm (also known as nuclear 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.

Downloads

• Status: SIAM Journal on Optimization 23 (4), pp. 2124 – 2149, 2013.
• Paper:  [Publisher’s pdf] [arXiv:1112.2318]
• Codes:
  • TraceNorm for multivariate linear regression (added 27/06/15, not fully polished) .
  • TraceNorm for large-scale matrix completion (added on 12/12/12).
  • Past version for smaller dimensional problems: Matlab developmental code for matrix completion, modified on 25/08/12.
• Entry: December 23, 2011.

An example with an animated logo of ULg

This is an illustration of the code on a low-rank image of zeros and ones. 60% of the entries (pixels) are randomly removed with uniform probability of an approximately low-rank image of the University of Liege logo. The low-rank matrix completion code outputs a sequence of (globally optimal) solutions as the regularization parameter λ is varied. Below we show the recovery of the original image.

Recovered image with different ranks	Traversing different ranks.
Original image	Better prediction accuracy of regularization path