# Compressed Sensing relationship to L1 Regularization

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?

• related: quora.com/… – Charlie Parker Mar 27 '18 at 17:57
• 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. – 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.

• 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? – Charlie Parker Mar 26 '18 at 22:04
• 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”). – mweylandt Mar 26 '18 at 22:42
• 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? – Charlie Parker Mar 27 '18 at 17:54
• 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. – mweylandt Mar 27 '18 at 18:01
• Here is the other question: stats.stackexchange.com/questions/337113/… – Charlie Parker Mar 27 '18 at 18:57