2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – mmmm
    May 13 at 7:20
  • $\begingroup$ 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. $\endgroup$
    – David
    May 13 at 15:36
  • $\begingroup$ no, it is L1 for Ax-y as well.. that's why I ask... $\endgroup$
    – dpdp
    May 13 at 20:31
  • $\begingroup$ Related - dsp.stackexchange.com/questions/65986. $\endgroup$
    – Royi
    May 14 at 10:05
  • $\begingroup$ @dpdp, Could you give us the reference? $\endgroup$
    – Royi
    May 14 at 10:05
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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?) $\endgroup$
    – dpdp
    May 13 at 20:36
  • $\begingroup$ 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. $\endgroup$
    – David
    May 14 at 13:00
  • $\begingroup$ FWIW it's Eq 1.5 in page 3 arxiv.org/pdf/1211.0290.pdf $\endgroup$
    – dpdp
    May 14 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.