Constrained LASSO Problem - ${L}_{1}$ Regularized Least Squares with Linear Equality Constraints

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?

• @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. Jan 16, 2019 at 23:54
• Could you explain what "orthogonal invariance property of Φ" means?
– Royi
Jan 17, 2019 at 0:18
• @Royi $\|\Phi x\|_2 = \|x\|_2$ Jan 17, 2019 at 0:21
• This is called Unitary Matrix. I don't think it is usable for the Lasso case in the ${L}_{1}$ term.
– Royi
Jan 17, 2019 at 8:04
• @Royi, I don't think subgradient is a good strategy. Jan 29, 2019 at 5:36

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?