This drawback leads to other sparsity improving terms that result in nonconvex approximation schemes.
A natural choice is to use the \( \ell _p \) -quasi-norm for some \( p \in (0,1) \) , which is no longer convex,
but still continuous, see [1]}.
Despite its nonconvexity, if there are no constraints (i.e., \( X = \mathbb {R}^n \) ), the resulting problem can still be
solved relatively efficiently by a proximal-type method.
For additional constraints, one can apply an augmented Lagrangian-type method and use the proximal-type approach to solve the resulting (unconstrained) subproblems, see [2]}, [3]}.
In principle, these techniques can also be used for the \( \ell _0 \) -norm, but the discontinuity still causes some trouble and typically leads to slowly convergent (proximal-type) gradient methods, see [3]}.
Another method belonging to the class of nonconvex approximations is the penalty decomposition method [5]}, which introduces an additional variable and solves the resulting problem
by an alternating minimization technique.
Also the DC-type methods (DC = difference of convex) described in [6]} result in a nonconvex
approximation which is shown to be exact under some additional assumptions, see also the DC-reformulation of the
\( \ell _0 \) -norm from [7]} (this reformulation, however, is applied to cardinality-constrained problems where the \( \ell _0 \) -term is not in the objective function but in
the constraints, see below for a more detailed discussion).
