An approximation theory of matrix rank minimization and its applications to quadratic equations

Yun-Bin Zhao

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)
173 Downloads (Pure)


Matrix rank minimization problems are gaining plenty of recent attention in
both mathematical and engineering fields. This class of problems, arising in various and acrossdiscipline 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 Frobenius norm, then any accumulation point of solutions to the approximation problem, as the approximation parameter tends to zero, is a minimum rank solution of the original problem. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. 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.
Original languageEnglish
Pages (from-to)77-93
Number of pages15
JournalLinear Algebra and its Applications
Issue number1
Publication statusPublished - 2012


  • Matrix rank minimization, singular values, matrix norms, semidefinite programming, duality theory, quadratic equations.


Dive into the research topics of 'An approximation theory of matrix rank minimization and its applications to quadratic equations'. Together they form a unique fingerprint.

Cite this