# Basis pursuit denoising (BPDN) and LASSO with a given measurement error?

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.

• 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 – user795305 Jul 19 '17 at 6: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

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:

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

• 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