# 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$$ "norm" 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? 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$$.