1

There are two functions associated by the model

$a(x) = \int_{k_1}^{k_2} b(k)\exp(-kx)dk$

where $a(x)$ is the experimental data I have, and $b(k)$ is the information I want to get. Or I can write in a matrix form if k space is discretized:

$a = Mb$

Now I would like to solve this inverse problem with L1 regularization with b>=0 constrain:

min: $|Mb-a|^2 + \lambda|b|$

subject to: $b\geq 0$

with $\lambda$ as the regularization parameter.

(Actually this problem is similar to a previous one, but this time it is L1 norm regularization.)

My questions are:

  1. While general solvers for the unconstrained least square with L1 regularization problems exist, I have some difficulties finding a solver for the constrained case like here. Is there an existing solver/routine I can make use of? If not, is there an easy way to get on this problem?
  2. I don't know the noise level. Someone suggested cross-validation method to get the regularization parameter. I have some difficulties understanding this method. Could anyone give an easy explanation and point me to the appropriate resources for further understanding?

Update: regarding the first question above, I have found this Matlab solver is really great.

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467
shva
  • 31
  • 3
  • Sorry, I should have clarified my previous comment. I'm reposting it with explanation. The link to Rob Hyndman's post on [Cross-validation](http://robjhyndman.com/hyndsight/crossvalidation/) was in answer to Q2 – Glen_b Feb 25 '14 at 05:04
  • To clarify, that post's discussion of cross validation gives what is alternatively known as the "PRESS" statistic or the "deleted residual," which uses the hat matrix as a shortcut to doing leave-one-out cross validation. If you're not satisfied with the explanation in Glen's link, try googling those terms for more information. – David Marx Feb 25 '14 at 05:14
  • Thanks. I just read the post link. However, for the non-negativity constrained L1 problem I have, can I still use the form of H matrix (described in the "Cross-​​validation for lin­ear models" section of Glen's link) for the purpose of generalized cross-validation? It seems that there should be some way to include the regularization parameter $\lambda$, and I cannot see there is a closed form of it for a given $\lambda$. – shva Feb 25 '14 at 21:21

1 Answers1

1

Least square regression with an L1 regularization term is better known as "LASSO regression." Some light googling turned up this paper that describes a "Constrained LASSO" algorithm (which I'm not otherwise familiar with besides having stumbled across this paper) for tackling your problem.

http://www-bcf.usc.edu/~rusmevic/psfiles/CLasso.pdf

David Marx
  • 6,647
  • 1
  • 25
  • 43
  • Yes. I later find the non-negativity constrained L1-regularized problem can be solved as a constrained quadratic program. I also find there is a solver written for such program as I update in the question description. – shva Feb 25 '14 at 21:17