Wikipedia defines basis pursuit denoising to be the solution to the minimization problem $$\min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1$$

I am not sure I see the difference between this and LASSO, I just assume they are the same.

Then Wikipedia says that, when $\lambda\to\infty$, this problem becomes basis pursuit, which is defined as the solution to $$\min_x \|x\|_1 \quad \mbox{subject to} \quad y = Ax$$

This I definitely don't understand. To me, when $\lambda\to\infty$ the condition $\|x\|_1$ should trump the other one and the solution shoud just be $x=0$.

I even found a paper by Tibshirani, the inventor of LASSO, where he claims exactly this.

Why I am wrong?


1 Answer 1


Basis pursuit is typically applied to the underdetermined case where you can have $y-Ax = 0$ for an infinite number of values of $x$. In that case, you often want the sparsest solution, which can be found by increasing $\lambda$ until you can no longer satisfy the constraint $y-Ax = 0$. If you keep increasing $\lambda$ past that point, you're right, eventually you'll get $x=0$, but that's not the optimum basis pursuit solution, which is constrained by the requirement that $y-Ax=0$.

LASSO, on the other hand, typically deals with the overdetermined case, where you can't actually find an $x$ for which $y-Ax=0$, and therefore any shrinkage of $x$ increases the "violation" of the constraint $y-Ax=0$. Typically we don't think about it that way, though, and just treat it as trading off sparsity with accuracy as measured by the in-sample fitting criterion of choice (L2-norm in the case of least squares.) It is basically the same thing as basis pursuit denoising in the statistical realm, which is basis pursuit when you are willing to accept an $x$ for which $y-Ax$ is "small" in some formal sense of the word.

The Wikipedia statement in the basis pursuit denoising article ("As $\lambda \rightarrow \infty$ (or when $\delta = 0$), this problem becomes basis pursuit.") is half correct - the half referring to $\delta = 0$ (which is equivalent to enforcing $y-Ax = 0$). Contra Wikipedia, as $\lambda \to 0$ the problem becomes a basis pursuit problem, assuming there actually is a range of values for $\lambda$ such that $y-Ax = 0$ can be satisfied. Even writing it that way is sloppy and confusing, since it makes it appear to the unwary reader that the basis pursuit solution is at $\lambda = 0$, which it isn't except in the case of exactly determined $y-Ax=0$, for which you don't need basis pursuit anyway.

  • $\begingroup$ Sorry, but you state it both ways, that the thing becomes basis pursuit both when $\lambda\to 0$ and when $\lambda\to\infty$. So which is it? I am very confused, sorry $\endgroup$
    – thedude
    Nov 29, 2019 at 17:08
  • $\begingroup$ (I have in mind the overdetermined case, I don't want to enforce $Ax=b$) $\endgroup$
    – thedude
    Nov 29, 2019 at 17:14
  • $\begingroup$ I don't state it both ways. I quote the Wikipedia article, and state that it is half-correct, the incorrect part being the $\lambda \to \infty$ part. However, I don't think that thinking about basis pursuit denoising in terms of $\lambda \to$ anything is particularly helpful in terms of determining its relationship to basis pursuit itself. $\endgroup$
    – jbowman
    Nov 29, 2019 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.