# 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.

• It is my impression that $\ell_1$ norm is only better than $\ell_0$ in terms of practical feasibility; $\ell_0$ optimisation becomes combinatorial and thus quickly infeasible as the problem size grows. Oct 5 '15 at 15:07
• Oct 5 '15 at 16:00
• Could you refer to the exact point where it says ${L}_{1}$ is better than ${L}_{0}$?
– Royi
Jun 3 '19 at 4:39
• @Royi: The OP was last seen on Aug 25 '16 at 19:29, according to his/her profile. I'm afraid you won't get a reply anymore. Feb 28 '20 at 11:49
– Royi
May 22 at 6:51

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.