  Sparsity constrained minimization captures a wide spectrum of applications in
both machine learning and signal processing. This class of problems is
difficult to solve since it is NP-hard and existing solutions are primarily
based on Iterative Hard Thresholding (IHT). In this paper, we consider a class
of continuous optimization techniques based on Mathematical Programs with
Equilibrium Constraints (MPECs) to solve general sparsity constrained problems.
Specifically, we reformulate the problem as an equivalent biconvex MPEC, which
we can solve using an exact penalty method or an alternating direction method.
We elaborate on the merits of both proposed methods and analyze their
convergence properties. Finally, we demonstrate the effectiveness and
versatility of our methods on several important problems, including feature
selection, segmented regression, MRF optimization, trend filtering and impulse
noise removal. Extensive experiments show that our MPEC-based methods
outperform state-of-the-art techniques, especially those based on IHT.
