I have an optimization question.

I want to solve the following problem:

$$ \arg\min_S\frac{1}{2}\|s-c\|_2^2 +\lambda\|\Phi s\|_1 \mbox{ s.t. } As = 0 $$

in which $\Phi$ is the wavelet transform operator.

My strategy is to find the close form solution of the lasso problem by using the orthogonal invariance property of $\Phi$, and then we project the solution onto the affine space.

I think this method will not converge to the optimal solution, but the numerical results shows good.

Is there any efficient method to solve this kind of problem?

  • $\begingroup$ What's the Orthogonal Invariance property of LASSO? Can you link to it? $\endgroup$
    – Royi
    Jan 16 '19 at 13:18
  • $\begingroup$ I will post an answer to this soon (Indeed you can not project the solution of the LASSO, at least it is not guaranteed to yield the correct answer unless the solution set contains the set of constraints). $\endgroup$
    – Royi
    Jan 16 '19 at 20:15
  • $\begingroup$ @Royi, Since we have a wavelet transform in the problem, I want to call $\Phi$ as less as possible, I want to seek a solution like that. $\endgroup$
    – Z-Harlpet
    Jan 16 '19 at 23:54
  • $\begingroup$ Could you explain what "orthogonal invariance property of Φ" means? $\endgroup$
    – Royi
    Jan 17 '19 at 0:18
  • $\begingroup$ @Royi $\|\Phi x\|_2 = \|x\|_2$ $\endgroup$
    – Z-Harlpet
    Jan 17 '19 at 0:21

Indeed you can not solve the problem ignoring the equality constraints and then project the solution onto the set of solution for the constraint. It is easy to build real world example which shows that.

Yet, it might be that in most cases it will work reasonably well.

You didn't mention how you solve the LASSO Problem but one of the easiest ways to solve it is using Sub Gradient Descent (Though it is not the fastest, but the idea is simple).

The Sub Gradient is a generalization of the Gradient Descent for cases which are not differentiable like the $ {L}_{1} $ Norm.

The Sub Graident of your function above is given by:

$$ s - c + \lambda {\Phi}^{T} \operatorname{sign} \left( \Phi s \right) $$

The nice thing about the Sub Gradient method that it has the Projected Sub Gradient variant which fits exactly what you need.

What you need to do is each iteration of the Sub Gradient Descent to project the result of the step onto the set of the constraint.

It will be something like:

  1. $ {s}^{ \left( k + \frac{1}{2} \right) } = {s}^{ \left( k \right) } - \alpha \left( {s}^{ \left( k \right) } - c + \lambda {\Phi}^{T} \operatorname{sign} \left( \Phi {s}^{ \left( k \right) } \right) \right) $.
  2. $ {s}^{ \left( k + 1 \right) } = {s}^{ \left( k + \frac{1}{2} \right) } - {A}^{T} {\left( A {A}^{T} \right)}^{-1} A {s}^{ \left( k + \frac{1}{2} \right) } $.

When you need to iterate between those steps until the solution is converged.
It is easy to see that step (2) is projection onto the convex set defined by $ A s = 0 $.

Of course you can replace the Sub Gradient by something more modern and efficient as FISTA and this will still work like a charm (Iterating by Graidnet Step and Projection Step).


Why not add an $\alpha\|As\|$ term to the optimization instead of having it as a constraint?


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.