I am solving an L1 regularized least squares of the form like:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$

I saw that for the L2 norm case there are several methods to obtain the magnitude of $\lambda$ as seen in the study Comparing parameter choice methods for regularization of ill-posed problems. For the L1 case I was told to look at AIC\BIC but I have a feeling I am not using them correctly.

For example, y is a 1x1000 vector and A is a 1000x1000 dictionary, and I plan it so that x will be a sparse vector of a length 1000 with only 5-15 non zeros values. By trial and error the range of $\lambda$s that retrieve accurate solutions is broad in the range 1e-4-1e-2 (using CVX). I want to find the optimal value, similar to generalized cross validation that is done in L2 norm case.

I am calculating AIC\BIC (using aicbic function in matlab) as follows: I scan values of $\lambda$ in the range 1e-7 to 1. For each $\lambda$ value I use for the log-likelihood, the log of the output of the optimal value of CVX (cvx_optval), for the number of estimated model parameters I use the number of non-zero (or |x|>1e-6) entries in the solution of x, and for the sample size I simply use the length of y.

I get the minimum of the AIC\BIC estimate for a $\lambda$ value around 1, which is incorrect. This is because the number of non-zero entries that is used for the estimated model parameters is dropping to 1, so the total function gets a minima there.

What am I doing wrong, and should I use AIC\BIC or something else and how?

  • $\begingroup$ I don't know enough to tell you but if you don't get a good answer here, you might have better luck on stats.stackexchange.com. $\endgroup$ Dec 22, 2022 at 5:19
  • $\begingroup$ What's wrong about cross validation? You can quite simply also apply it to L1 regression. $\endgroup$
    – davidhigh
    Dec 22, 2022 at 15:43
  • $\begingroup$ AIC\BIC are all connected with cross validation (which is a broader concept), so it should work for AIC\BIC just as much as it should work for CV... I was also asking about the way I implemented AIC\BIC here. $\endgroup$
    – yourds
    Dec 22, 2022 at 17:37
  • 1
    $\begingroup$ This result is telling you that the solution with only one nonzero entry in $x$ is fitting the data well in comparison with solutions with more nonzero entries. What is it about the solutions with $\lambda$ in the range from 1e-4 to 1e-2 that you prefer? $\endgroup$ Dec 23, 2022 at 16:55
  • $\begingroup$ unfortunately that's not the case. the minimum in the AIC vs $\lambda$ happens if the # of non-zero elements in x (which I use as the estimated model parameters input for AICBIC) drops to 1. that's always how $\lambda$ behaves , the larger it is the more sparse the solution will be and so the smaller integer # that is input as estimated model parameters.I have a feeling I misunderstood how to use AIC inputs, and that is the core of my question. $\endgroup$
    – yourds
    Dec 23, 2022 at 23:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.