  In this paper we consider general rank minimization problems with rank
appearing in either objective function or constraint. We first establish that a
class of special rank minimization problems has closed-form solutions. Using
this result, we then propose penalty decomposition methods for general rank
minimization problems in which each subproblem is solved by a block coordinate
descend method. Under some suitable assumptions, we show that any accumulation
point of the sequence generated by the penalty decomposition 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.
