# 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. – Demetri Pananos Jul 20 '19 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? – littleO Nov 24 '19 at 11:51

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$$.