3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Arildsen Oct 5 '15 at 15:07
  • $\begingroup$ See also dsp.stackexchange.com/questions/23735/… $\endgroup$ – Thomas Arildsen Oct 5 '15 at 16:00
  • $\begingroup$ Could you refer to the exact point where it says $ {L}_{1} $ is better than $ {L}_{0} $? $\endgroup$ – Royi Jun 3 at 4:39
  • $\begingroup$ Anything missing on my answer? Please let me know. $\endgroup$ – Royi Oct 31 at 6:37
0
$\begingroup$

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} \text{ s.t. } {\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} \text{ s.t. } {\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.