Compressive Sensing Results for Unconstrained Form

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!

• For every $\rho$ there is a $\lambda$ such that optimal solutions to the two optimization problems are the same. Commented Mar 25, 2018 at 21:20
• Yes but is there an explicit way of finding $\lambda$ given $\rho$? I basically want an explicit bound on $\lambda$. Commented Mar 25, 2018 at 21:25
• You can find $\lambda$ in a straightforward way by binary search. Commented Mar 25, 2018 at 21:30
• yes but I'm trying to write a closed form probabilistic recovery guarantee as a function of $\lambda$ Commented Mar 25, 2018 at 21:36
• Also I don't think it makes much sense to do LASSO in a binary search, since a single LASSO is 1) not THAT computationally cheap and 2) in practice sufficient. So the theory should be tighter than that... Commented Mar 25, 2018 at 21:38

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.

• I mean I see what you mean in that the recovery guarantees for K, m, and incoherence of A are the same. I think I phrased my question wrong though; I'm really wondering if there are any results with explicit conditions on $\lambda$. Commented Apr 4, 2018 at 15:00
• If you write the Lagrangian of the problem you'll have to find the $\lambda$ that satisfies the KKT Conditions. This is the same $\lambda$. Since it doesn't have a closed form solution from the KKT I don't think a straight connection exist. Actually $\lambda$ is a function of $k$, $A$ and $b$ so it is really not simple.
– Royi
Commented Apr 4, 2018 at 16:00
• That's a nice way of looking at it! Thank you, a negative result is also very useful for me. Commented Apr 5, 2018 at 0:46
• I added some detail to what you are saying, and it seems to give me exactly the answer I want! Thank you! Commented Apr 5, 2018 at 1:07
• Could you mark my answe so the question will be marked as solved? You are welcome.
– Royi
Commented Apr 5, 2018 at 4:35