  Nonsmooth sparsity constrained optimization captures a broad spectrum of
applications in machine learning and computer vision. However, this problem is
NP-hard in general. Existing solutions to this problem are limited since they
fail to solve general nonsmooth problems, lack convergence analysis, or lead to
weaker optimality conditions. This paper revisits the Penalty Alternating
Direction Method (PADM) for nonsmooth sparsity constrained optimization
problems. We consider two variants of the PADM, i.e., PADM based on Iterative
Hard Thresholding (PADM-IHT) and PADM based on Block Coordinate Decomposition
(PADM-BCD). We show that the PADM-BCD algorithm finds stronger stationary
points of the optimization problem than previous methods. We also develop novel
theories to analyze the convergence rate for both of the PADM-IHT and the
PADM-BCD algorithms. Finally, numerical results demonstrate the superiority of
PADM-BCD to existing sparse optimization algorithms.
