Compressed sensing: $\ell_0$ “norm” vs $\ell_1$ norm

Suppose we have a very efficient way to perform $\ell_0$ "norm" compressed vs $\ell_1$ norm compressed sensing. Specifically, $\ell_0$ "norm" compressed sensing is

\eqalign{ & \min \quad {x^T}Qx + {b^T}x + \mu {\left\| x \right\|_0} \cr & \text{s.t}:\quad Ax \le b \cr}

while $\ell_1$ norm compressed sensing is

\eqalign{ & \min \quad {x^T}Qx + {b^T}x + \mu {\left\| x \right\|_1} \cr & \text{s.t}:\quad Ax \le b \cr}

Should we almost always use the $\ell_0$ norm formulation? Is there any paper discussing the benefits of $\ell_0$ (disregard the computational perspectives) over $\ell_1$ norm compressed sensing?

Edit: The actual application we are interested in is about avoiding overfitting formulated below. For example $x$ is a very long feature vector (say length $1000$); however we only $100$ data, i.e., ${E_\text{feature}}$ is $100 \times 1000$, and ${E_\text{input}}$ is $100 \times 1$. The question we are interested in is whether the $\ell_0$ norm formulation (if can be computed practically) can offer a significant advantage over the $\ell_1$ norm formulation.

\eqalign{ & \min \quad \left\| {{E_\text{feature}}x - {E_\text{input}}} \right\|_2^2 + \mu {\left\| x \right\|_{0,1}} \cr & \text{s.t}:\quad Ax \le b \cr}

• – Christian Clason Apr 1 '17 at 8:43
• I think it depends on your goal. It also depends on how you're computing your L0 and L1 norm (are you dividing by the length of $x$ in your L1 norm?). If you do divide by the length of $x$, the L1 norm will allow for the case where one entry is really large but all the other entries are really small to compensate for it. Do you consider this to be overfitting? If yes, then the L0 norm is better. If not, the L1 norm should be okay and, in fact, the fit from the L1 norm might illuminate the more important features of the problem. – nukeguy Apr 4 '17 at 19:36
• Clearly, if what you want is to minimize the 0-norm, and you can effectively perform the minimization, then you should use the first formulation. Of course, the 0-norm problem is intractable, so that premise is false. The 1-norm is used as a surrogate in many cases precisely because it is tractable and has good approximation properties. Thus there isn't much of a question to answer here. – Brian Borchers May 6 '18 at 16:24

In Compressed Sensing the real problem is the ${\left\| \cdot \right\|}_{0}$ norm (Well, Pseudo Norm).
One of the great discoveries are conditions under which using ${\left\| \cdot \right\|}_{1}$ will yield the same results as using ${\left\| \cdot \right\|}_{0}$.
So we can find geometrical intuition why ${L}_{1}$ promotes sparsity yet real sparse cost function is the ${\left\| \cdot \right\|}_{0}$ norm.