Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: interpolating/smoothing w/ monotonically increasing
Date: Thu, 13 Aug 2009 11:52:02 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 62
Message-ID: <h60up2$dpn$1@fred.mathworks.com>
References: <ged003$oi7$1@fred.mathworks.com> <ged11r$f59$1@fred.mathworks.com> <ged2vl$ep1$1@fred.mathworks.com> <ged7g2$ki3$1@fred.mathworks.com> <gedajd$mp$1@fred.mathworks.com> <gedfqa$am6$1@fred.mathworks.com> <h60o8v$e66$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1250164322 14135 172.30.248.37 (13 Aug 2009 11:52:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 13 Aug 2009 11:52:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:562966


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h60o8v$e66$1@fred.mathworks.com>...
> An anonymous reader has solicited me to post the code of monotonic interpolation. As I do not own optimization toolbox I cannot check whereas LINPROG is correctly called and provides good result. But here we go. If you see any issue with linprog call please let me know.
> 
> Bruno

There is an IMPORTANT caveat there.

Bruno has written a piecewise linear approximant. This
is NOT interpolation, because interpolation reproduces
the data exactly. When your data is not monotone, then
a monotone function cannot interpolate the data.

You will see different results from a monotone cubic
approximant too. See my SLM tools for both a linear
and cubic approximant. (It looks like Bruno has used
a solution that I posted some time ago, before I had
chosen to post SLM.

http://www.mathworks.com/matlabcentral/fileexchange/24443

Note that the constraints for a monotone cubic are
a bit nastier than just those one would employ for a
monotone linear approximant. In fact, there are several
ways one can implement a class of constraints for a
monotone cubic. (Outside the scope of this discussion.)

While in the past, I have offered an L1 or Linfinity solver
when I've written a tool like SLM, I've rarely found it to
be in demand. It is not difficult to add to SLM though
if users wanted it.

Now, why did Bruno see different results from the
various choices of approximant used? 

An infinity norm solver will minimize the MAXIMUM
residual. This is a terrible choice for problems where
you have an outlier or outliers in the data, since all
that matters is a reduction of the MAXIMUM residual.
Worse, if you use an infinity norm solver to solve this
problem, then it need not reproduce the data points
even when the data is truly monotone! See that the
L1 and L2 solvers will at least reproduce the data
points in those parts of the curve where the data was
monotone.

At the other extreme is an L1 solver. Here the sum of
absolute residuals is minimized. So a single outlier may
often be ignored when it is inconsistent with the
remainder of the data. There is no assurance that this
will always yield a better result however. In fact, I can
give an example where the L1 solver need not generate
as good a solution as the L2 (lsqlin) solver.

I'll argue that the best solution would use my SLM tools
to yield a result that is both smooth and has all the
properties that you know must exist in the underlying
relationship.

Again, I'll consider adding an L1 solver to SLM if
there are requests. This is easy enough to do.

John