Compressed sensing: $\ell_0$ "norm" vs $\ell_1$ norm

Question

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} $$

Answer 1

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.