# Tuning parameter in the LASSO/group LASSO

I have a problem regarding the tuning parameter $\lambda$ in the LASSO or group LASSO.

Suppose I want to find a matrix $\mathbf{A} = [\mathbf{a}_1,...,\mathbf{a}_n]\in\cal{C}^{m\times n}$ that minimizes the distance to some known matrix $\mathbf{A}_0\in\cal{C}^{m\times n}$, with sparsity constraint on the columns: $$\underset{\mathbf A}{\mathrm{min}}||\mathbf{A}-\mathbf{A}_0||_F^2 + \lambda\sum_{i=1}^{n}||\mathbf{a}_i||_2,$$ then my question is:

Is there some approach that can find the smallest $\lambda$ that achieves a certain level of sparsity? For example, if I want 50% of the columns in $\mathbf{A}$ to be zeros, how should I determine $\lambda$ (error is of no concern at this point)?

One simple way would be to initialise $\lambda$ with some proper interval, and then check sparsity after solving the LASSO problem. We can do this repeatedly to narrow down the interval until certain sparsity is achieved. Is there any smarter or more rigorous way to solve this?

• I had to do something similar a few years ago. My approach was to concatenate the columns of $A$ into a big vector and then do group lasso on $X\beta$, where $X$ was a blog diagonal matrix. I can attempt to provide a full answer if you like. Commented Jul 20, 2019 at 15:06
• If you know that you want $k$ columns of $A$ to be nonzero, why not just choose $A$ to agree perfectly with the $k$ largest columns of $A_0$ (as measured by the $2$-norm) and have the other columns of $A$ be all zeros? Commented Nov 24, 2019 at 11:51
• Is the computational effort, computing for several $\lambda$, really so costly? Could you explain some details about your case why you would like to compute it faster? (I imagine that possibly some details of the case could help design and optimise the algorithm) What sort of level of simplifications do we need to make or can we make? (e.g. compute an exact answer or approximate it?) Commented Jan 10, 2022 at 9:59

How the lasso solution is generated, is that the variables are included in to the model one by one, untill you will get solution for all possible lambdas. So you don't have to do the narrowing down the intervals, you can just fit the whole lasso and then find the lambda that goes with the desired sparsity level. Or even better, you might stop fitting the lasso, once the desired sparsity is reached. For example glmnet package in R can do it with the parameter dfmax.

• "How the lasso solution is generated" There are many ways to solve a LASSO problem, and not all of them are as you described. Commented Nov 24, 2019 at 11:54
• you are right. glmnet/lars do it this way, but there are other approaches Commented Nov 24, 2019 at 15:56
• Changing the answer into "How the lasso solution can be generated" solves the problem indicated by the previous comments. A problem that remains is that group LASSO is not solved with LARS. Commented Jan 8, 2022 at 9:47

I'll assume $$A$$ and $$A_0$$ have real entries. I need to think about whether the argument below still makes sense in the complex case. I'll also change the data fidelity term to $$(1/2) \| A - A_0\|_F^2$$. The factor of $$(1/2)$$ I inserted makes calculations a little nicer.

Your problem separates into $$n$$ separate optimization problems. The $$i$$th problem is to minimize $$\|a_i\|_2 + \frac{1}{2\lambda} \| a_i - v_i \|^2$$, where $$v_i$$ is the $$i$$th column of $$A_0$$. In other words, the $$i$$th problem is to evaluate the prox-operator of the $$2$$-norm at the point $$v_i$$. But we know the prox-operator of the 2-norm. It just shrinks $$v_i$$ towards the origin by a distance $$\lambda$$. (If we hit the origin, we stop.) So for a given $$\lambda$$ you can easily tell how many columns of $$A$$ will be zero. Just look at $$A_0$$, and see how many of its columns are within a distance $$\lambda$$ of the origin.

So, you can see how to choose $$\lambda$$ to make $$A$$ have the desired number of zero columns.

To make 50% of the columns of $$A$$ be zero, just set $$\lambda$$ equal to the median of the $$2$$-norms of the columns of $$A_0$$.