Optimization Online


On the Global Optimality for Linear Constrained Rank Minimization Problem

Xin Liu (liuxin***at***lsec.cc.ac.cn)
Hong Wang (hong.wang***at***connect.polyu.hk)
Xiaojun Chen (xiaojun.chen***at***polyu.edu.hk)
Yaxiang Yuan (yyx***at***lsec.cc.ac.cn)

Abstract: The rank minimization with linear equality constraints has two closely related models, the low rank approximation model, that is to find the best rank-k approximation of a matrix satisfying the linear constraints, and its corresponding factorization model. The latter one is an unconstrained nonlinear least squares problem and hence enjoys a few fast first-order methods such as the nonlinear successive over-relaxation algorithm LMaFit or alternating least squares. However, the solutions obtained by the above mentioned approaches lack of global optimality guarantee. In this paper, we focus on exploring the theoretical properties of the factorization model of the low rank approximation with linear constraints. Under some particular situations, we show that the corresponding factorization models are of the property that all second-order stationary points are global minimizers. By assuming such property holds, we propose an algorithm framework which outputs the global solution of the linear constrained rank minimization problem after solving a series of its factorization models with different ranks to the second-order necessary optimality. The adaptive regularization with cubics can be used as the inner local solvers to obtain the second-order stationary point. Finally, we put forward a conjecture that the reduction between the global minima of the low rank approximation with consecutive ranks is monotonically decreasing with the increase of the rank. If this conjecture holds, we can accelerate the estimation of the optimal rank by an adaptive technique, and hence significantly increase the efficiency of the overall performance of our framework in solving the linear constrained rank minimization problem.

Keywords: linear constrained rank minimization, low rank approximation, nonconvex optimization, second-order optimality condition, global minimizer

Category 1: Nonlinear Optimization

Category 2: Global Optimization

Citation: 1/2015

Download: [PDF]

Entry Submitted: 11/10/2014
Entry Accepted: 11/10/2014
Entry Last Modified: 12/19/2015

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