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

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}$$ ?

• That can only be answered when knowing what you do this for! You're solving an optimization problem for some purpose, so that purpose is important to the optimal method.
– mmmm
May 13 '21 at 7:20
• In the 2nd case did you mean to write the L1 norm of Ax-y? If not, you should fix it. I suspect you meant the L2 norm for this component. May 13 '21 at 15:36
• no, it is L1 for Ax-y as well.. that's why I ask...
– dpdp
May 13 '21 at 20:31
• Related - dsp.stackexchange.com/questions/65986.
– Royi
May 14 '21 at 10:05
• @dpdp, Could you give us the reference?
– Royi
May 14 '21 at 10:05

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.

• thanks for the answer. I just dont understand the reason Ax-y needs to be sparse, will it improve accuracy if x is sparse (and it is)? or be less sensitive to noise? (or perhaps more?)
– dpdp
May 13 '21 at 20:36
• It really depends on the nature of the problem that is being solved, and represents a apriori information you have about the problem. It will not necessarily be appropriate for all problems. May 14 '21 at 13:00
• FWIW it's Eq 1.5 in page 3 arxiv.org/pdf/1211.0290.pdf
– dpdp
May 14 '21 at 23:55