differences between two L1 norm minization schemes
The first equation you have is often called the Quadratic Problem, which through the use of Duality can be shown to be equivalent to the Basis Pursuit De-Noising (BPDN) given as:
$$ \arg \min_{\boldsymbol{x}} {\left\| \boldsymbol{x} \right\|}_{1}     \mbox{ subject to }   {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}&lt; \delta .$$
In your 2nd problem, the L2 norm is replaced with the L1 norm in the constraint. When you constrain the L2 error, you tend to end up with an error vector that is quite dense, i.e. a lot of non-zero elements, and each error is small with respect to $\delta$.
By switching the error to the L1 norm, then they are trying to make the error vector sparse (as opposed to dense). So in this formulation:
$$ \arg \min_{\boldsymbol{x}} {\left\| \boldsymbol{x} \right\|}_{1}     \mbox{ subject to }   {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{1}&lt; \delta $$
They are trying to find:

An $\boldsymbol{x}$ that is sparse under the constraint that
$\boldsymbol{e}=A \boldsymbol{x} - \boldsymbol{y}$ is also sparse.

In this sense you might think that the problem they really want to solve is:
$$ \arg \min_{\boldsymbol{x}} {\left\| \boldsymbol{x} \right\|}_{0}     \mbox{ subject to }   {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{0}&lt; \delta $$
but because that is a very difficult problem, they are using the convex formulation they have given.