Differences Between Two $ {L}_{1} $ Norm Minimization Schemes

Question

I was reading and working with L1 regularized least squares, where:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$

is used to solve for sparse solutions in $\boldsymbol{x}$. However, I also stumbled on a different minimization for a similar case:

$$ \arg \min_{\boldsymbol{x}} {\left\| \boldsymbol{x} \right\|}_{1} \mbox{ subject to } {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{1}< \delta $$

so in the second case the expression is not unconstrained, but they switched both parts to L1 norm... What are the reasons to do so if both look for sparse solutions in $\boldsymbol{x}$ ?

Answer 1

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}< \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}< \delta $$

They are trying to find:

1. An $\boldsymbol{x}$ that is sparse under the constraint that
2. $\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}< \delta $$ but because that is a very difficult problem, they are using the convex formulation they have given.