A proximal alternating direction method for semi-definite rank minimization

Ganzhao Yuan, Bernard Ghanem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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 languageEnglish (US)
Title of host publication30th AAAI Conference on Artificial Intelligence, AAAI 2016
PublisherAAAI press
Number of pages9
ISBN (Print)9781577357605
StatePublished - Jan 1 2016

Bibliographical note

KAUST Repository Item: Exported on 2020-12-23
Acknowledgements: 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.


Dive into the research topics of 'A proximal alternating direction method for semi-definite rank minimization'. Together they form a unique fingerprint.

Cite this