Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations
This work offers a theoretical foundation for developing efficient computational methods for rank minimization, which is relevant to researchers in optimization and engineering dealing with NP-hard problems.
The paper provides an approximation theory for NP-hard matrix rank minimization problems, proving they can be approximated to any accuracy via continuous optimization. It shows that under certain conditions, the approximation converges to the minimum rank solution, and applies this to characterize when a system of quadratic equations has only the zero solution.
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.