4

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.

Hjan
  • 141
  • 5
  • The minimizer isn't affected by scaling by constants. For an explanation of a very similar question, see, for instance, https://stats.stackexchange.com/questions/117369 – user795305 Jul 19 '17 at 06:11
  • @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. – Hjan Jul 19 '17 at 14:13

1 Answers1

2

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.

Royi
  • 966
  • 8
  • 20
  • Thanks for your effort. To bring my question to the point: If i know $v$ or $\varepsilon $ how do i choose $\lambda$? – Hjan Apr 27 '18 at 13:49
  • There is no simple function connecting between the two (The function itself is model and data dependent). – Royi Apr 27 '18 at 17:04