Please use this identifier to cite or link to this item:
Title: An implementable proximal point algorithmic framework for nuclear norm minimization
Authors: Liu, Y.-J.
Sun, D. 
Toh, K.-C. 
Keywords: Accelerated proximal gradient method
Gradient projection method
Nuclear norm minimization
Proximal point method
Rank minimization
Issue Date: Jun-2012
Citation: Liu, Y.-J., Sun, D., Toh, K.-C. (2012-06). An implementable proximal point algorithmic framework for nuclear norm minimization. Mathematical Programming 133 (1-2) : 399-436. ScholarBank@NUS Repository.
Abstract: The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature. © 2011 Springer and Mathematical Optimization Society.
Source Title: Mathematical Programming
ISSN: 00255610
DOI: 10.1007/s10107-010-0437-8
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.