In this paper we consider general l0-norm minimization problems, that is, the
problems with l0-norm appearing in either objective function or constraint. In
particular, we first reformulate the l0-norm constrained problem as an
equivalent rank minimization problem and then apply the penalty decomposition
(PD) method proposed in [33] to solve the latter problem. By utilizing the
special structures, we then transform all matrix operations of this method to
vector operations and obtain a PD method that only involves vector operations.
Under some suitable assumptions, we establish that any accumulation point of
the sequence generated by the PD method satisfies a first-order optimality
condition that is generally stronger than one natural optimality condition. We
further extend the PD method to solve the problem with the l0-norm appearing in
objective function. Finally, we test the performance of our PD methods by
applying them to compressed sensing, sparse logistic regression and sparse
inverse covariance selection. The computational results demonstrate that our
methods generally outperform the existing methods in terms of solution quality
and/or speed.