5
$\begingroup$

I am having some difficulties to understand the difference between:

  1. Basis Pursuit DeNoising (BPDN) which is often stated as:

$min \left \| x \right \|_1 s.t \left \|Ax-b \right \|_2 \leq \varepsilon$ (1)

but solutions are generally found by solving:

$min \left \| Ax-b \right \|_{2}^{2}+\lambda \left \| x \right \|_1$ (2)

  1. And LASSO, which is often stated as:

$min \left \| Ax-b \right \|_2 s.t \left \|x \right \|_1 \leq \varepsilon$ (3)

for which in Lagrangian form is also (2)

It seems to me that the natural langrangian form for BPDN would be: $min \left \| x \right \|_1 +\lambda\left \| Ax-b \right \|_{2}^{2}$ But i never saw this in any literature. Can i conclude from this that (2) for small $\lambda$ is BPDN, and for large $\lambda$ its LASSO? or where is the difference between the two?

The main point which i do not understand about finding a BPDN solution is how to use an estimate for the measurement error or noise if this is available? If one knows for example that the noise in measurements b is for example 10%, how can i use this information about in the solution procedure? Expression 1 would allow me include this error estimate by means of epsilon.
The naive approach of putting expression 1 in a general purpose non-linear optimiser with inequality constraints and some fixed value for epsilon works however very poorly. I understand that with the value of lambda i can control the sparsity, but how can i set epsilon in the standard solution procedures, which all seem to be using the Lagrangian form (2), where the noise threshold epsilon seems absent?

Any helpful insights are really appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ The minimizer isn't affected by scaling by constants. For an explanation of a very similar question, see, for instance, stats.stackexchange.com/questions/117369 $\endgroup$ Commented Jul 19, 2017 at 6:11
  • $\begingroup$ @Ben, Thanks for the link. Sorry maybe i was not very clear, the question was not about the scaling constants, so i removed them to avoid confusion. 1 subquestion is about the difference between BPDN and LASSO? The main question is about how to use knowledge of the measurement error in the solution process. $\endgroup$ Commented Jul 19, 2017 at 14:13

2 Answers 2

Reset to default
3
$\begingroup$

Real world model is:

$$ A x = y $$

Where $ x $ is a sparse vector.
Yet, in reality we don't have measurements of $ y $ but $ b = y + v $ where $ v $ is a vector with the properties of our measurement method.

Hence we allow the model not to have strict equality which implies:

$$ {\left\| A x - b \right\|}_{2}^{2} \leq \epsilon = {\left\| v \right\|}_{2}^{2} $$

Now, the different models are equivalent as for any $ \epsilon $ there is a $ \lambda $ (Which depends on $ A $ and $ b $ unfortunately) which the models ( (1) and (2) ) are equivalent.

For instance I created simple simulation on for that simulation:

enter image description here

The full code is available on my StackExchange Cross Validated Q291962 GitHub Repository.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your effort. To bring my question to the point: If i know $v$ or $\varepsilon $ how do i choose $\lambda$? $\endgroup$ Commented Apr 27, 2018 at 13:49
  • $\begingroup$ There is no simple function connecting between the two (The function itself is model and data dependent). $\endgroup$ Commented Apr 27, 2018 at 17:04
0
$\begingroup$

I cannot find anyone that addresses this problem for LASSO / $\ell(1)$ regression, and since the regularization term is not differentiable, it's a bit harder than the ridge /$\ell(2)$ case. I posted an answer here: https://math.stackexchange.com/a/4682686/192065 It shows equivalence for:

  1. $\ell(1)$ constrained optimization (for fixed $r>0$, find $\text{arg}\min_x f(x)$ subject to $\|x\|_1 \leq r$ )
  2. the usual LASSO regularization problem, (for fixed $\lambda \geq 0$, find $\text{arg}\min_x f(x) + \lambda\|x\|_1$ )
  3. the Lagrangian with $g(x) = \|x\|_1 - r$, (for fixed $r>0$, find $\text{arg}\min_{x, \lambda \geq 0} f(x)+ \lambda( \|x\|_1 -r)$)
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.