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

Improve this question
$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 at 21:21

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\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, 2014 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.