Signal Reconstruction in Compressed Sensing with a Simple Vector Signal as an Example While going through the different types of reconstruction algorithm as mentioned in Richard G. Baraniuk - Compressive Sensing - Lecture Notes (Also on DocDroid), I came to know that minimum $ {L}_{1} $ norm reconstruction is better than minimum $ {L}_{0} $ and $ {L}_{2} $ norm reconstruction.  

Can anyone show me why $ {L}_{1} $ norm is better by taking a simple signal vector of small length as an example?
I would like to know what will be the final optimization results in each reconstruction method.
Better is hard to measure unless there is a well defined measure.

Yet in the classic Compressed Sensing model (Sparse Representation) the Holly Grail is actually the $ {L}_{0} $ Pseudo Norm.

The problem is $ {L}_{0} $ isn't really a norm and hence the optimization problem isn't convex.
Moreover, it is not smooth (It has discrete properties) and the problem:

$$ \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \quad \text{s.t.} \quad {\left\| x \right\|}_{0} \leq k $$

Is actually NP hard. Namely we don't know how to solve it efficiently.

We can prove that under some cases solving the following problem:

$$ \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \quad \text{s.t.} \quad {\left\| x \right\|}_{1} \leq k $$

Yields the same solution. Yet this form is Convex and we have many effective tools to solve it.

Hence it is preferable to use this model in the cases it is good enough.