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!
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.