Parametrized complexity of sparse optimization

Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0le 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||_0le k$ to $||x||_1le 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<p<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$.