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?

$\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$ Mar 16, 2014 at 11:12

1 Answer 1

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.

$\endgroup$
4

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