1
$\begingroup$

Does anyone know the term or algorithm for an NNLS, wherein the solution has a constraint such that it contains only $p$ non-zero values?

For example, if the standard linear least squares problem is:

$\bf{X}\bf{\beta} = \bf{y}$

$\bf{\hat{\beta}} = (\bf{X^TX})^{-1}\bf{X}^T\bf{y}$

And we place the constraint that $\hat{\beta}\ge0$ (to create a non-negative linear least squares problem). The wonderful thing is that there are several methods out there that solve this problem quite easily, in python or MATLAB etc.

However, if we place the additional constraint that $\beta$ must have only $p$ values that are non-zero ($\beta$ is sparse), what is this type of problem named?

I am interested in this as it would be useful to select the $p$ most useful predictors in the set rather than all of them.

I thought of something similar to PCA, but this appears to be quite different.

I would assume that there is a simple way to implement this in various programming languages such as python, but I am uncertain of what to search.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

For the general case: Tikhonov regularization. For variable selection and shrinkage: LASSO.

$\endgroup$
4
  • $\begingroup$ Thank you! this helps a lot to orient myself into the correct terminology. However, I see that you can change $\lambda$ for these regularizations, but is there a way to set a parameter such that I get exactly only $p=2$ coeffecients returned in the solution vector? $\endgroup$
    – chase
    Mar 4, 2018 at 19:40
  • 1
    $\begingroup$ Yes, it is called the $l_0$ "norm" (penalty): Here a good introduction $\endgroup$
    – V. Vancak
    Mar 4, 2018 at 20:21
  • $\begingroup$ Thank you for the help. I was mainly interested if there is an algorithm which already has this ability to select an exact number of parameters as an input, but it appears the $l_0$ norm only attempts to guess the number of parameters, as they state in the paper "In particular, the number of variables selected by 𝐿0 are close to 3, the true number of nonzero variables, while lasso selected more than 11 features on average with different correlation structures (𝑟 = 0, 0.3, 0.6, 0.8)." $\endgroup$
    – chase
    Mar 5, 2018 at 1:19
  • 1
    $\begingroup$ By setting strict equality in $\sum_{j=1}^p I(w_j \neq 0 ) = r$ you will choose exactly $r$ parameters. Don't know about packages, but the classic one is the glmnet in R. Not sure If it can be specified to meet your constrains. Anyway, consider to ask on CV as well. stats.stackexchange.com is slightly more suitable for these type of questions. $\endgroup$
    – V. Vancak
    Mar 5, 2018 at 1:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .