Fixed point and Bregman iterative methods for matrix rank minimization

Shiqian Ma (sm2756columbia.edu)
Donald Goldfarb (goldfarbcolumbia.edu)
Lifeng Chen (lc2161columbia.edu)

Abstract: The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The linearly constrained nuclear norm minimization is a convex relaxation of this problem. Although it can be cast as a semidefinite programming problem, the nuclear norm minimization problem is expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm that can solve very large matrix rank minimization problems. Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3.

Keywords: Matrix Rank Minimization, Matrix Completion Problem, Nuclear Norm Minimization, Fixed Point Iterative Method, Bregman Distances, Singular Value Decomposition

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report, Department of IEOR, Columbia University, October, 2008.

Download: [PDF]

Entry Submitted: 11/21/2008
Entry Accepted: 11/21/2008
Entry Last Modified: 05/07/2009

Modify/Update this entry