2
$\begingroup$

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: \begin{equation} \underset{\mathbf A}{\mathrm{min}}||\mathbf{A}-\mathbf{A}_0||_F^2 + \lambda\sum_{i=1}^{n}||\mathbf{a}_i||_2, \end{equation} 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?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Demetri Pananos Jul 20 '19 at 15:06
  • $\begingroup$ 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? $\endgroup$ – littleO Nov 24 '19 at 11:51
0
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ "How the lasso solution is generated" There are many ways to solve a LASSO problem, and not all of them are as you described. $\endgroup$ – littleO Nov 24 '19 at 11:54
  • $\begingroup$ you are right. glmnet/lars do it this way, but there are other approaches $\endgroup$ – rep_ho Nov 24 '19 at 15:56
0
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

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.