Trouble finding an algorithm

[Glen]

I've been playing with the Diliberto-Straus algorithm, using the Chebyshev metric to fit a model of the form

z = f(x) + g(y)

It's a very simple algorithm (it took a few minutes to implement) and I've been looking at ways to improve it.

Anyway von Golitschek (1984) extended the algorithm to the case z = H[ u(y).f(x) + v(x).g(y) ] for specified u and v.

e.g. see http://books.google.com/books?id=jceNPtrJN8kC&pg=PA76&lpg=PA76&dq=golitschek+nomographic|nomographical&source=bl&ots=H1hlK9CVCJ&sig=NMb1HU4792EsntxUjcIK6Eh_FLc#v=onepage&q=golitschek%20nomographic|nomographical

(every google books reference that I can find that discusses it, cuts out the page that the discussion occurs on )

Unfortunately, I don't seem to be able to get hold of the original book here,
(M. von Golitschek, "Shortest path algorithms for the approximation by nomographic functions,"
in Anniversary Volume on Approximation Theory and Functional Analysis, P. L. Butzer, R. L. Stens, and B. Sz. -Nagy, eds.,
Birkhauser Verlag, Basel, Switzerland, ISNM 65, 1984, pp. 281-301. )

nor can I find any papers which discuss it properly (I found an online pdf book by Cheney which actually started to discuss it, but when it came to
details, he basically simplified the situation back to the Diliberto-Straus case ... and essentially got the DS algorithm. Gee, thanks, I can find that
anywhere)

(Most of the approximation-theory books in the university library here seem to predate 1984, but I've just managed to identify a couple of more recent ones in the catalog, so there's some hope one of them will have something.)

So anyway, if any of you guys are able to take a look and tell me what the algorithm consists of, that would be useful. I assume there's a back-projection
step to estimate H-inverse (i.e. the transform of z), which is the obvious thing to do, but I'm not exactly sure of how Golitschek deals with the u and v functions - I assume its NOT something as basic as just dividing through (because there are problems with that).

Any pointers or ideas?

[RonDoerfler]

Hi Glen,

The 1984 book, "Anniversary Volume on Approximation Theory and Functional Analysis" is available in a few university libraries around here (i.e., Chicago). If no one else has provided the article to you by this weekend, I can stop by one of those libraries on Saturday, copy the von Golitschek lecture, and send you a scan of it. If you discover any papers or other books that discuss this topic, just let me know and I'll look those up too.

Ron

[Glen]

I wouldn't wish you to make a special trip on my account, though next time you happen to be around the right area(s), it would be great if you could take a look.

Besides the de Boor book that I linked to above
Approximation theory
By Carl De Boor, American Mathematical Society (near p77)

(where the material I'd want to see was on the next page after the link), there was another:

Multivariate approximation theory: selected topics
By Elliott Ward Cheney (near p48)

So besides the original 1984 book with the Golitschek article, either of these might have the algorithm

[RonDoerfler]

Hi Glen,

Here are the Golitschek and Cheney articles. Unfortunately, it appears that Cheney defaults back to the Diliberto-Straus case here, too.

http://www.myreckonings.com/Temp/Golitschek.doc
http://www.myreckonings.com/Temp/Cheney.pdf

If you'd still like the de Boor book excerpt, just let me know. It's in a different university library and I can get it in about a week. While I was at this library I poked around in the indexes of the other books in this field, but I didn't see any other references to Golitschek.

So I gather that you are using these algorithms to find the best combination of linear curves to fit statistical data so you can create nomograms easily for them, right? Last year I borrowed a copy of "Best Approximation by Linear Superpositions (Approximate Nomography)" by Khavinson that you had recommended. Wow, was I in over my head! I had no idea that abstract algebra and graph theory would be related to the practical application of linear approximations to curves. On the other hand, Khavinson's book and these articles steadfastly refuse to provide a single example (despite my pleas) or explanatory figure to a degree that seems purposefully distant, maybe disdainful. Or maybe it's just me. As Cheney says at the start of his fourth paragraph, "Let us proceed now to subspaces in tensor product spaces." Okay.

Ron

[Leif]

I have had not time to go into these articles, but I have a simple question:

Would't any curve fitting algorithm work? If one has a function and data, curve fitting finds best match with given error function.
For example least-squares fitting.

Computer's in general use are quite new in perspective of nomography. So are these question practical or kind of academic?

\leif

[Glen]

Would't any curve fitting algorithm work? If one has a function and data, curve fitting finds best match with given error function.
For example least-squares fitting.

Computers in general use are quite new in perspective of nomography. So are these question practical or kind of academic?

I am attempting to deal with an entirely practical question, ultimately aiming to produce working code.

Least squares fitting minimizes the sum of squares of error, which is fine if that's your loss function. I can solve many of these problems via least squares; for example, I can call canned routines to fit something like z = f(x) + g(y) via least squares where f and g are smooth functions in some sense, and I can do it in a couple of different ways. (Actually I can achieve more than that with LS, but let's discuss that one. In effect the "working code" part of this issue is done.)

However, if your aim is to minimize the maximum error, well, least squares doesn't do that; it minimizes the L-2 norm of the errors.

Diliberto-Straus does do that. That is, it minimizes the L-infinity norm of the errors.

D-S will fit z = f(x) + g(y) (without a specified form for f and g) such as to minimize the worst case error. I have implemented it and it works as advertised, quite rapidly (a very simple algorithm that converges in a very small number of iterations in the cases I tried), and if z(x,y) is a continuous function then the estimated f and g will also be guaranteed to be continuous (though I only compute it on a grid in my implementation). In effect the "working code" part of this is done.

If I solve the same problem via LS, I am guaranteed to end up with some point(s) where the fit is "worse", in the sense that the error is larger there. Usually it won't matter much, but if you're after say a maximum error of half a percent and LS gives you a maximum error of 0.7%, then trying to minimize the thing you're actually wanting to minimize may get you there - and if it doesn't, you know it can't be achieved with that kind of model, which is useful information if you must get a better fit.

Golitschek generalizes Diliberto-Straus to the case where we minimize the maximum error in the fit to z of h(z) = f(x).u(y) + g(y).v(x)
i.e. to minimize max| z - hinv[ f(x).u(y) + g(y).v(x) ] | for specified u,v and hinv .

This is still not quite what I'd like to have but I was hoping to understand how it worked in order to include it within a larger iterative scheme in order to be able to also estimate v and h (setting u to a constant) while minimizing maximum error rather than least squares, thus giving me a minimized-maximum error genus-I nomogram. I don't know if this will work but I have good reasons to suppose that it will.

At the same time, I discovered a really simple way to fit a genus II nomogram that won't minimize either the L-2 or the L-infinity norm (but could probably be used as a good starting point for either resulting non-linear least-squares or nonlinear least maximum deviation). Of course, if the fit is good enough - and in a lot of practical cases it will be - then the exact norm involved doesn't matter as much.

(One of the things I want to do with D-S and Golitschek is to see if I can get an iterative approximation to it by using iterative reweighted least squares, which, even if it works, will be slower to converge in the base case but gives me more scope to play with it in other situations. Ultimately I hope to be able to extend a genus-II nomogram fit to the L-infinity-norm case. If I can do that, I will regard the "fit nomograms to data" issue as pretty much resolved, and it then comes down to making it into something people will want to use.)

Code: Select all

                              Norm
Nomo              don't care     L2               L-infinity
-type
genus 0            code         code             code
genus I            code         kinda-done       extension of Golitschek?
genus II           proposal     nonlinearLS         ??


where "proposal" is my proposed really simple algorithm for the genus-II nomogram (that I haven't explained here yet).

So while the papers might sometimes look unbearably esoteric, my aim is to use them (if I can actually figure out what it's all about) to do something entirely practical.

[Leif]

So this is actually an optimization problem: which algorithm to use to fit data for a given or guessed function. Least squares is of course only one choice. For me using python, I would hope to find a ready algorithm in:

http://docs.scipy.org/doc/scipy/reference/optimize.html

Minimizing maximum error sounds like a good error function. Is there is Diliberto-Strauss for python? That could be the choice if making approximative nomographs in the future.

br,

\leif

[Glen]

So this is actually an optimization problem: which algorithm to use to fit data for a given or guessed function. Least squares is of course only one choice. For me using python, I would hope to find a ready algorithm in: http://docs.scipy.org/doc/scipy/reference/optimize.html

Minimizing maximum error sounds like a good error function. Is there is Diliberto-Strauss for python? That could be the choice if making approximative nomographs in the future.
\leif

Of the optimizers listed there, I believe only the global ones are likely to work very well on this problem (at least they should work with some care). The issue is that the usual optimizers rely on either specifying or building up derivative information that will be essentially useless on this problem

You can set it up as a form of linear programming problem, and there surely will be some of those for Python.

But the D-S algorithm itself is pretty simple, if you only need a parallel-scale nomogram. (The Golitschek one is more complicated, being a special version of a shortest-path algorithm, but it solves a slightly more complicated problem. I haven't got it figured out yet.)

[joe marasco]

Hi Glen,

I published an algorithm with working C code back in 1986, implementing a Variable Metric Minimizer. Here are the bibliographic details:

---------------------------------------------------
A Variable Metric Minimizer

CONTRIBUTORS: Author: Marasco, Joe (b. 1945, d. ----)

JOURNAL: Dr. Dobb's journal of software tools for the professional programmer, 11(3), 24 - 34.

YEAR: 1986
PUB TYPE: Journal Article
SUBJECT(S): Minimization algorithms; variable metric minimization; implementation of variable metric minimization algorithms in C;
DISCIPLINE: Computer Science
HTTP: http://portal.acm.org/citation.cfm?id=12635&jmp=indexterms&dl=GUIDE&dl=ACM
LANGUAGE: English
PUB ID: 103-412-101 (Last edited on 2005/01/25 12:41:03 US/Mountain)

ABSTRACT:
This article describes a variable metric minimizer, a program that finds the set of parameters to a function that will produce the smallest output value from that function. The program uses methods now accepted as both robust and efficient. These methods can handle a wide variety of functions and data without failing, and they can find a minimum in a shorter time (fewer iterations) than other methods. They are called quasi-Newton positive definite secant update methods. The variable metric part comes from looking at the global topology of the problem in addition to the local information given by the derivatives. Complete code is given in C, starting on page 74 through page 86. The rest of the code listing is continued in the following month's issue, 11 (4) or #114, which appeared in April 1986, starting on page 84.
----------------------------------------------------------------------------

The quantity that is minimized is the least squares error, so it is not exactly what you are looking for. On the other hand, you can provide the system with any function of your choosing, and it will fit parameters quite nicely and quickly.

Although this work was done a long time ago -- almost 25 years ago -- it was well received at the time, and used as shareware with some success. Later, the article and some additional material were published as a book chapter. Here is the bibliographic reference for that:

-----------------------------------------------------------------------------
A Variable Metric Minimizer

CONTRIBUTORS: Editor: Holub, Allen
Contributor: Ashdown, Ian
Contributor: Fox, David
Author: Marasco, Joe (b. 1945, d. ----)

BOOK TITLE: C chest and other C treasures from Dr. Dobb's journal (1987) Holub, Allen I.. Redwood City, Calif.: M&T Books.

YEAR: 1987
PUB TYPE: Book Chapter
PAGES: 365 - 423
SUBJECT(S): Minimization; variable metric minimization; computer code to implement variable metric minimization;
DISCIPLINE: Computer Science
HTTP: http://www.amazon.com/exec/obidos/tg/detail/-/0934375402/qid=1106689492/sr=1-1/ref=sr_1_1/102-2124552-5187364?v=glance&s=books
LANGUAGE: English
PUB ID: 103-412-098 (Last edited on 2005/01/25 14:45:32 US/Mountain)

ABSTRACT:
This chapter describes a variable metric minimizer, a program that finds the set of parameters to a function that will produce the smallest output value from that function.

The program uses methods now accepted as both robust and efficient. That is, these methods can handle a wide variety of functions and data without failing, and they can find a miniumum in a shorter time (fewer iterations) than other methods.

The methods are called quasi-Newton positive definite secant update methods. The variable metric part comes from looking at the global topology of the problem in addition to the local information given by the derivatives.

Complete C code is given. The user may choose an arbitrary function to minimize subject to his or her data.

A simplified explanation of the method is also included.
--------------------------------------------------------------------------------------------------

You should be able to find one or the other of these in your library.

Thanks.

Joe

[Glen]

Hi Joe, thanks for that.

I'm reasonably familiar with quasi-Newton methods; I studied them during my computing major (years ago), and they're used in a variety of problems I work with. They're sometimes used in statistics; we were even discussing them in a seminar I was at a few weeks ago.

Indeed, Quasi-Newton methods would be potentially useful if derivatives existed ... for the infinity norm they don't, or rather not everywhere (including at the optimum) and not in a way that's usually useful for gradient methods. The three cases I care about are L1, L2 and L-infinity, and you only get derivatives everywhere with L2. L1 and L-infinity norms lead to functions (of the parameters) to minimize that consist of polytopes, if I have understood things right.

As I mentioned earlier, you can write infinity-norm problems as linear programming problems; the D-S and Golitschek algorithms should be more efficient than using LP, because they are taking advantage of some special aspects of the problem structure.

For (nonlinear) least squares problems, there are plenty of robust minimizers around - the usual ones are based on some variation of Gauss-Newton-Marquardt (and are generally faster than quasi-Newton methods on least squares problems). I don't lack for these.

More recently, Marquardt methods have been combined with secant methods / quasi-Newton methods in several ways (e.g. Broyden did a secantized version of Marquardt for when second derivatives are unavailable, and there's also been G-N-M methods that switch over to a quasi-Newton approach when that would be faster, switching back when indicated).

[Minor edits for accuracy and clarity]