Optimization Online


Low-Rank Matrix Completion using Nuclear Norm with Facial Reduction

Shimeng Huang(s87huang***at***uwaterloo.ca)
Henry Wolkowicz(hwolkowicz***at***uwaterloo.ca)

Abstract: Minimization of the nuclear norm is often used as a surrogate, convex relaxation, for finding the minimum rank completion (recovery) of a partial matrix. The minimum nuclear norm problem can be solved as a trace minimization semidefinite programming problem (\SDP). The \SDP and its dual are regular in the sense that they both satisfy strict feasibility. Interior point algorithms are the current methods of choice for these problems. This means that it is difficult to solve large scale problems and difficult to get high accuracy solutions. In this paper we take advantage of the structure at optimality for the minimum nuclear norm problem. We show that even though strict feasibility holds, the facial reduction framework can be successfully applied to obtain a proper face that contains the optimal set, and thus can dramatically reduce the size of the final nuclear norm problem while guaranteeing a low-rank solution. We include numerical tests for both exact and noisy cases. In all cases we assume that knowledge of a \emph{target rank} is available.

Keywords: Low-rank matrix completion, matrix recovery, semidefinite programming (\SDPp), facial reduction, cliques, Slater condition, nuclear norm, compressed sensing.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: University of Waterloo, Canada, July/2016

Download: [PDF]

Entry Submitted: 08/14/2016
Entry Accepted: 08/15/2016
Entry Last Modified: 08/14/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society