Optimization Online


Approximation of Matrix Rank Function and Its Application to Matrix Rank Minimization

Chengjin Li (chengjin98298***at***163.com)

Abstract: Matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. However, the problem is in general NP-hard, and it is computationally hard to solve directly in practice. In this paper, we provide a new kind of approximation functions for the rank of matrix, and the corresponding approximation problems can be used to approximate the matrix rank minimization problem within any level of accuracy. Furthermore, the monotonicity and the Frechet derivative of the approximation functions are discussed. On this basis, we design a new method, which is called as successive projected gradient method, for solving the matrix rank minimization problem by using the projected gradient method to find the stationary point of a series of approximation problems. Finally, the convergence analysis and the preliminary numerical results of the successive projected gradient method for the rank minimization problem are given.

Keywords: Matrix rank minimization, approximation function, projected gradient method, successive projected gradient method

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China, 08/2012

Download: [PDF]

Entry Submitted: 08/18/2012
Entry Accepted: 08/19/2012
Entry Last Modified: 08/19/2012

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