Abstract
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 stateof- The-art low-rank semi-definite minimization algorithms in terms of solution quality.
| Original language | English (US) |
|---|---|
| Title of host publication | 30th AAAI Conference on Artificial Intelligence, AAAI 2016 |
| Publisher | AAAI press |
| Pages | 2300-2308 |
| Number of pages | 9 |
| ISBN (Print) | 9781577357605 |
| State | Published - Jan 1 2016 |
Bibliographical note
KAUST Repository Item: Exported on 2020-12-23Acknowledgements: Research reported in this publication was supported by competitive research funding from King Abdullah University of Science and Technology (KAUST). Yuan is also supported by Natural Science Foundation of China (61402182), Postdoctoral Science Foundation of China (2015M572317), and Fundamental Research Funds for Central Universities. A special thanks is also extended to Prof. Shaohua Pan for her helpful discussion on the MPEC techniques.