6
$\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.

Improve this question
$\endgroup$
5
  • $\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, 2015 at 15:07
  • $\begingroup$ See also dsp.stackexchange.com/questions/23735/… $\endgroup$
    – Thomas Arildsen
    Oct 5, 2015 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, 2019 at 4:39
  • $\begingroup$ @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. $\endgroup$
    – Florian
    Feb 28, 2020 at 11:49
  • $\begingroup$ Could you please review my question? Please mark it if it answers your question. Thank You. $\endgroup$
    – Royi
    Jan 30 at 19:01

1 Answer 1

Reset to default
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} \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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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