  In this paper we consider sparse approximation problems, that is, general
$l_0$ minimization problems with the $l_0$-"norm" of a vector being a part of
constraints or objective function. In particular, we first study the
first-order optimality conditions for these problems. We then propose penalty
decomposition (PD) methods for solving them in which a sequence of penalty
subproblems are solved by a block coordinate descent (BCD) method. Under some
suitable assumptions, we establish that any accumulation point of the sequence
generated by the PD methods satisfies the first-order optimality conditions of
the problems. Furthermore, for the problems in which the $l_0$ part is the only
nonconvex part, we show that such an accumulation point is a local minimizer of
the problems. In addition, we show that any accumulation point of the sequence
generated by the BCD method is a saddle point of the penalty subproblem.
Moreover, for the problems in which the $l_0$ part is the only nonconvex part,
we establish that such an accumulation point is a local minimizer of the
penalty subproblem. Finally, we test the performance of our PD methods by
applying them to sparse logistic regression, sparse inverse covariance
selection, and compressed sensing problems. The computational results
demonstrate that our methods generally outperform the existing methods in terms
of solution quality and/or speed.
