Penalty decomposition methods for rank minimization

Zhaosong Lu, Yong Zhang, Xiaorui Li

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


In this paper we consider general rank minimization problems with rank appearing either in the objective function or as a constraint. We first establish that a class of special rank minimization problems has closed-form solutions. Using this result, we then propose penalty decomposition (PD) methods for general rank minimization problems in which each subproblem is solved by a block coordinate descent method. Under some suitable assumptions, we show that any accumulation point of the sequence generated by the PD methods satisfies the first-order optimality conditions of a nonlinear reformulation of the problems. Finally, we test the performance of our methods by applying them to the matrix completion and nearest low-rank correlation matrix problems. The computational results demonstrate that our methods are generally comparable or superior to the existing methods in terms of solution quality.

Original languageEnglish (US)
Pages (from-to)531-558
Number of pages28
JournalOptimization Methods and Software
Issue number3
StatePublished - May 4 2015
Externally publishedYes

Bibliographical note

Funding Information:
This work was supported in part by NSERC Discovery Grant.


  • matrix completion
  • nearest low-rank correlation matrix
  • penalty decomposition methods
  • rank minimization

Fingerprint Dive into the research topics of 'Penalty decomposition methods for rank minimization'. Together they form a unique fingerprint.

Cite this