A proximal alternating direction method for semi-definite rank minimization

Ganzhao Yuan, Bernard Ghanem

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

5 Scopus citations

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

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

Cite this