I understand that compressed sensing finds the sparsest solution to $$y = Ax$$ where $x \in \mathbb{R}^D$, $A \in \mathbb{R}^{k \times D}$, and $y \in \mathbb{R}^{k}$, $k << D$.

In this way we can reconstruct $x$ (the original) using $y$ (the compression), reasonably fast. We say that $x$ is the sparsest solution. Sparsity can be understood as the $l_0$-norm for vectors.

We also know that the $l_1$-norm (solvable using linear programming) is a good approximation to the $l_0$-norm (which is NP-hard for large vectors). Therefore $x$ is also the smallest $l_1$ solution to $Ax=y$

I've read that compressed sensing is similar to regression with a lasso penalty ($l_1$). I've seen geometric interpretations of this too, but I haven't made the connection mathematically.

Other than minimizing the $l_1$ norm, what is the relationship (mathematically) between compression and Lasso?

  • $\begingroup$ related: quora.com/… $\endgroup$ – Charlie Parker Mar 27 '18 at 17:57
  • $\begingroup$ to my understanding Compressed Sensing is the field that studies recovery of Sparse Signals and L1 Regularization is just one specific formulation for approximately solving it. $\endgroup$ – Charlie Parker Mar 27 '18 at 18:56

There is essentially no difference. It's just statistician's terminology vs electrical engineer's terminology.

Compressed sensing (more precisely, basis pursuit denoising [1]) is this problem:

$\text{arg min}_x \frac{1}{2}\|Ax - b\| + \lambda \|x\|_1$

while the Lasso[2] is this problem

$\text{arg min}_{\beta} \frac{1}{2}\|y - X\beta\| + \lambda \|\beta\|_1$

Inasmuch as there is a difference, it's that in Compressed Sensing applications, you (the engineer) get to choose $A$ to be "nicely behaved" while, for the Lasso, you (the statistician) don't get to choose $X$ and have to deal with whatever the data are (and they are rarely "nice"...). Consequently, much of the subsequent Compressed Sensing literature has focused on choosing $A$ to be as "efficient" as possible, while much of the subsequent statistical literature has focused on improvements to the lasso that still work with $X$ that "break" the lasso.

[1] S.S. Chen, D.L. Donoho, M.A. Saunders. "Atomic Decomposition by Basis Pursuit." SIAM Journal on Scientific Computing 20(1), p.33-61, 1998. https://doi.org/10.1137/S1064827596304010

[2] R. Tibshirani "Regression Shrinkage and Selection via the lasso." Journal of the Royal Statistical Society: Series B 58(1), p.267–88, 1996. JSTOR 2346178.

  • $\begingroup$ but usually compressed sensing is phrased as $ min \| x \|_1$ such that $Ax=b$. Is that really equivalent to min of $\|Ax - b \| + \lambda \| x \|_1$ if so why and how does lambda fall in the original picture? $\endgroup$ – Charlie Parker Mar 26 '18 at 22:04
  • $\begingroup$ The formulation you give (with the equality constraint) is the “limit” in a sense as $\lambda \to 0$. It arises when you assume there is no noise in the system (so it’s often called “basis pursuit” as opposed to “basis pursuit denoising”). $\endgroup$ – mweylandt Mar 26 '18 at 22:42
  • $\begingroup$ something I am confused is I though matching pursuit methods where greedy algorithms to (approximately) solve $ \| Xw - y \|^2 + \lambda \| w \|_0$. However, I thought soft thresholding algorithms where exact solvers to the convex relaxation formulation $ \| Xw - y \|^2 + \lambda \| w \|_1$. Thus, if this is true would they lead to the same solution? i.e. it seems Lasso and OM solve the same problem but with a very different formulation. Any algorithm for LASSO yields the same solution cuz its convex put if OM is a greedy algorithm for L0 then I'd assume they are very different. Is this right? $\endgroup$ – Charlie Parker Mar 27 '18 at 17:54
  • $\begingroup$ I think this is worth asking in a separate question. In general, no -- the L1 (lasso) and L0 (best subsets) solutions are different. But there are special well-studied circumstances where the L0 and L1 versions of the basis pursuit problem (not basis pursuit noising) give the same solution. $\endgroup$ – mweylandt Mar 27 '18 at 18:01
  • 1
    $\begingroup$ Here is the other question: stats.stackexchange.com/questions/337113/… $\endgroup$ – Charlie Parker Mar 27 '18 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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