0
$\begingroup$

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.

$\endgroup$

migrated from mathoverflow.net Feb 23 '14 at 7:15

This question came from our site for professional mathematicians.

  • $\begingroup$ Sorry, I should have clarified my previous comment. I'm reposting it with explanation. The link to Rob Hyndman's post on Cross-validation was in answer to Q2 $\endgroup$ – Glen_b Feb 25 '14 at 5:04
  • $\begingroup$ 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. $\endgroup$ – David Marx Feb 25 '14 at 5:14
  • $\begingroup$ 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$. $\endgroup$ – shva Feb 25 '14 at 21:21
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – shva Feb 25 '14 at 21:17

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.