A Proximal Alternating Direction Method for Semi-Definite Rank Minimization

A Proximal Alternating Direction Method for Semi-Definite Rank Minimization

​Ganzhao Yuan and Bernard Ghanem
"A Proximal Alternating Direction Method for Semi-Definite Rank Minimization"
AAAI Conference on Artificial Intelligence (AAAI 2016)​
​Ganzhao Yuan, Bernard Ghanem
Semidefinite Rank Minimization, MPEC, Sensor Network Localization, Kurdyka-Łojasiewicz Inequality, Proximal ADM, Convergence Analysis
2016
​Semi-definite rank minimization problems model a wide range of applications in both signal processing and machine learning fields. This class of problem is NP-hard in general. In this paper, we propose a proximal Alternating Direction Method (ADM) for the well-known semi-definite rank regularized minimization problem. Specifically, we first reformulate this NP-hard problem as an equivalent biconvex MPEC (Mathematical Program with Equilibrium Constraints), and then solve it using proximal ADM, which involves solving a sequence of structured convex semi-definite subproblems to find a desirable solution to the original rank regularized optimization problem. Moreover, based on the KurdykaŁojasiewicz inequality, we prove that the proposed method always converges to a KKT stationary point under mild conditions. We apply the proposed method to the widely studied and popular sensor network localization problem. Our extensive experiments demonstrate that the proposed algorithm outperforms state-of-the-art low-rank semi-definite minimization algorithms in terms of solution quality.