Optimization Online


Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations

Yun-Bin Zhao (y.zhao.2***at***bham.ac.uk)

Abstract: Matrix rank minimization problems are gaining a plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least F-norm (i.e., Frobenius norm), then the solution of the approximation problem converges to the minimum rank solution of the original problem as the approximation parameter tends to zero. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. The methodology and results in this paper provide a new theoretical basis for the development of some efficient computational methods for solving rank minimization problems. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.

Keywords: Matrix rank minimization, singular values, matrix norms, semidefinite programming, duality theory, quadratic equations

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 01/30/2011
Entry Accepted: 01/30/2011
Entry Last Modified: 06/26/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