  


Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations
YunBin Zhao (y.zhao.2bham.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 acrossdiscipline applications, is known to be NPhard 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 Fnorm (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 (Semidefinite Programming ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Download: [PDF] Entry Submitted: 01/30/2011 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  