Parametrized complexity of sparse optimization Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so if anyone has one handy, please say so in the comments!] The $\ell_0$ &quot;norm&quot; is the number of non-zero elements in the vector $x$. A common way to solve such problems is via a convex relaxation: relax $||x||_0\le k$ to $||x||_1\le k$ and solve the resulting linear program. With luck, one can quantify how close the relaxed solution is to the optimal.
My question is: What if we try a more gradual relaxation, via the $\ell_p$ norm for $0&lt;p&lt;1$? These result in non-convex programs, but the non-convexity degree can be tweaked. Surely the $p=0.999$ case, for reasonably set other parameters, cannot be much harder than the $p=1$ case?.. Has anybody tried this approach? The idea is to seek a better efficiency/optimality tradeoff via values of $p$ other than $1$.
This may be related to what you have in mind: arxiv.org/abs/0804.4666