Mathematics – Optimization and Control
Scientific paper
2010-10-05
Mathematics
Optimization and Control
20 pages
Scientific paper
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.
No associations
LandOfFree
Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-86609