  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.
