  


Convergence of fixedpoint continuation algorithms for matrix rank minimization
Donald Goldfarb (goldfarbcolumbia.edu) Abstract: The matrix rank minimization problem has applications in many fields such as system identification, optimal control, lowdimensional embedding, etc. As this problem is NPhard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixedpoint continuation algorithm for solving the nuclear norm minimization problem. By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixedpoint continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported. Keywords: Matrix Rank Minimization, Matrix Completion, Greedy Algorithm, FixedPoint Method, Singular Value Decomposition, Restricted Isometry Property Category 1: Convex and Nonsmooth Optimization Citation: Technical Report, Department of IEOR, Columbia University, 2009 Download: [PDF] Entry Submitted: 06/18/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  