Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/102811
Title: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
Authors: Toh, K.-C. 
Yun, S.
Keywords: Iteration complexity
Matrix completion
Nuclear norm minimization
Proximal gradient
Singular value decomposition
Issue Date: 2010
Citation: Toh, K.-C.,Yun, S. (2010). An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific Journal of Optimization 6 (3) : 615-640. ScholarBank@NUS Repository.
Abstract: The affine rank minimization problem, which consists of finding a matrix of minimum rank subject to linear equality constraints, has been proposed in many areas of engineering and science. A specific rank minimization problem is the matrix completion problem, in which we wish to recover a (low-rank) data matrix from incomplete samples of its entries. A recent convex relaxation of the rank minimization problem minimizes the nuclear norm instead of the rank of the matrix. Another possible model for the rank minimization problem is the nuclear norm regularized linear least squares problem. This regularized problem is a special case of an unconstrained nonsmooth convex optimization problem, in which the objective function is the sum of a convex smooth function with Lipschitz continuous gradient and a convex function on a set of matrices. In this paper, we propose an accelerated proximal gradient algorithm, which terminates in O(1/??) iterations with an ε-optimal solution, to solve this unconstrained nonsmooth convex optimization problem, and in particular, the nuclear norm regularized linear least squares problem. We report numerical results for solving large-scale randomly generated matrix completion problems. The numerical results suggest that our algorithm is efficient and robust in solving large-scale random matrix completion problems. In particular, we are able to solve random matrix completion problems with matrix dimensions up to 105 each in less than 10 minutes on a modest PC. © 2010 Yokohama Publishers.
Source Title: Pacific Journal of Optimization
URI: http://scholarbank.nus.edu.sg/handle/10635/102811
ISSN: 13489151
Appears in Collections:Staff Publications

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

Page view(s)

107
checked on Oct 19, 2018

Google ScholarTM

Check


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