Long story short, I would like to efficiently:

Minimize ||bX-y||2 subject to X ≥ 0 and bX ≥ y

I have an observation that is a single curve (y) in the form of signal intensity vs. frequency. I would like to model this signal as a linear combination of a series of predictor curves in a design matrix, X. My current implementation is using an ordinary least squares analysis where the coefficients of the predictor curves, X, are given by,

b = (XTX)-1XTy

and the fitted values are given by,

ŷ = bX

However, this simple approach minimizes the sum of squared residuals and the fitted curves will always cross the data at some point, which is not physically realistic in the system that I am trying to model. From this, my desired restrictions would be:

bX ≥ y,

b ≥ 0

If anyone could point me in the right direction it would be greatly appreciated.

  • $\begingroup$ Did you think about optimization with one inequality constraint per data point ? $\endgroup$ – Claude Leibovici Dec 25 '18 at 15:41
  • $\begingroup$ @ClaudeLeibovici I had not initially. Now that I have spent some time researching (Lawson and Hanson, 1974), I think this is the correct method to use. However, I now wish to impose a non-negativity constraint in addition to my original bX> Y constraint. Is it possible to minimize || bX - Y|| subject to X>=0; bX > 0? $\endgroup$ – burlyhab Dec 28 '18 at 4:08
  • $\begingroup$ If you consider optimization, provided some reasonable guesses for the parameters, you could handle any number of inequality constraints as you wish. I faced this kind of problems long time ago. It was related to the curve fit of some physical properties (small errors) to be fitted to a nonlinear model; for safety and economic reasons we did not want to overestimate the predicted value at any point. It worked very nicely. $\endgroup$ – Claude Leibovici Dec 28 '18 at 4:15
  • $\begingroup$ @ClaudeLeibovici Forgive me, this may be a question for a different forum. Do you have a recommendation for a computationally efficient method to solve a minimization of this type? $\endgroup$ – burlyhab Dec 28 '18 at 4:50
  • $\begingroup$ If I properly remember, we used a modified version of subroutine NLPQL which was developed by Schittkowski in the mid 80's. Having a look at klaus-schittkowski.de//NLPQLP.pdf there is an improved version of it and it seems that the code is available at klaus-schittkowski.de $\endgroup$ – Claude Leibovici Dec 28 '18 at 5:11

If you want the fit line to always be above the data points except where it touches them, then it would have to go through two of the data points while being above or going through all the other data points.

A simple way of doing this, although computationally annoying, is to get the line through each pair of data points. For each of these lines, check if the line is above or on all the other points. This is the one you want.

If there are n points, this takes $O(n^3)$ time since there are $n(n-1)/2$ pairs of points and you have to check $n-2$ other points for each.

A more computationally effective method, could be to get the convex hull of the data points (which takes $n\log n$ time). One of its lines will be above or on all the other points, so this will take $O(n^2\log n)$ time.

It would be interesting if a $O(n^2)$ or $O(n)$ method could be found.


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.