1
$\begingroup$

I have a function called f(x) which is convex and I can have access to its first order derivative , my objective function is

$$\ J(\bf{x}) = f(\bf{x}) + \lambda |\bf{x}|_0 $$

$$\ \bigtriangledown f(\bf{x}) \space is \space available$$

Could you please provide a list of state of the art methods in the literature that can solve this sparse regularization problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to SciComp.SE! Such "shopping list" questions are not a good fit for this site (see scicomp.stackexchange.com/help/dont-ask). You will get better answers if you add some detail (context, size of the problem, desired accuracy, performance constraints, whether it has to be $l^0$, etc.) and ask for specific recommendations for your specific problem. $\endgroup$
    – Christian Clason
    Commented Mar 16, 2014 at 11:12

1 Answer 1

Reset to default
3
$\begingroup$

The short answer is that in general this problem is intractable (NP-Hard) with the $\| x \|_{0}$ regularization.

Are you willing to consider minimizing

$ f(x) + \lambda \| x \|_{1}$

instead? There are many methods for the 1-norm regularized problem. There are also lots of theoretical results that give conditions under which 1-norm minimization produces solutions that are very close to the 0-norm regularized solution.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Agreed. Last I checked, this general approach was favored in the literature. $\endgroup$
    – Geoff Oxberry
    Commented Mar 14, 2014 at 7:55
  • $\begingroup$ Thanks Brian, I am also looking for the name some state of the art methods on how to solve the l1 norm regularized problem in a general form of f(x) for which first order oracle properties are available. $\endgroup$
    – c.Parsi
    Commented Mar 18, 2014 at 18:41
  • $\begingroup$ See stanford.edu/~boyd/papers/prox_algs.html $\endgroup$
    – Brian Borchers
    Commented Mar 21, 2014 at 14:19
  • $\begingroup$ See also stanford.edu/~boyd/papers/admm_distr_stats.html $\endgroup$
    – Brian Borchers
    Commented Mar 21, 2014 at 14:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.