Compressive Sensing Results for Unconstrained Form

Question

Suppose $z\in \mathbb R^n$ is $K$ sparse, and for some measurement matrix $A\in \mathbb R^{m\times n}$ satisfying lots of awesome incoherence properties, we have $b = Az + n$ where $n_i \sim \mathcal N(0,\sigma)$.

The basis pursuit problem solves $$ \min_x \|x\|_1 \text{ subject to } \|Ax - b\|_2\leq \rho $$ and we know that for special cases of $\rho$, $m$, $K$, etc, we can either recover exactly $x = z$ or the sparsity pattern $\textbf{supp } x = \textbf{supp } z$. Specifically, there are results that directly relate the admissible noise level and therefore $\rho$, with the guarantees.

But let's face it, in general, we usually solve the unconstrained version $$ \min_x \frac{1}{2}\|Ax - b\|_2 + \lambda \|x\|_1 $$

Under similar assumptions for $K$ and $m$, and some assumptions on $\lambda$, what is currently known about the recoverability of either $z$ or the support of $z$?

Edit: I know there are homotopy methods that can interchange between $\rho$ and $\lambda$, and I am not looking for an implementation hint. I am simply curious (and pessimistic) as to whether there exists a theoretical gaurantee on an explicit choice of $\lambda$ relating to these admissible noise levels. Put it another way, are there cases where the homotopy method has a known solution?

Edit: A cool observation from Royi: Taking the Lagrangian of the basis pursuit problem, we get $$ \max_{\nu\geq 0}\min_{x}L(x,\nu,\rho) = \|x\|_1 + \nu \|Ax-b\|_2-\rho\nu. $$ Divide everything by $2\nu$ and doing a change of variables $\lambda = 2/\nu$ gives $$ \max_{\lambda\geq 0}\min_{x} \frac{1}{2} \|Ax-b\|_2 + \lambda \|x\|_1 $$ where the last term ($\rho/2$) is constant and drops out.

From this analysis we have an exact description of $\lambda$ corresponding to the BP problem:

If $\rho > \|Ax-b\|_2$ (constraint is not tight at optimality) then $\nu = 0 \iff \lambda = +\infty$.

If $\rho = \|Ax-b\|_2$ then $\lambda$ is the $\arg\max_\lambda$ of the penalized version, which in general is hard to solve but is mathematically well defined!

Answer 1

Since both forms are equivalent any property of the one usually holds for the other.

When I say equivalence I mean:

$$ \forall \epsilon, \, \exists \lambda : x \left( \epsilon \right) = x \left( \lambda \right) $$

Namely by tweaking the value of $ \lambda $ you can always have the solution of one form match the other.

You may have a look in my StackExchange Cross Validated Q291962 answer.

Remark
If one writes the Lagrangian of the problem $ \epsilon $ form of the problem one will have to find the $ \lambda $ that satisfies the KKT Conditions. This is the same $ \lambda $ the iterative solver finds. Since the KKT doesn't have a closed form solution I don't think a direct connection exists. Actually $ \lambda $ is a function of $ k $, $ A $ and $ b $ so it is really not simple.