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?
 A: 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.
