Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need to compare two curves f(x) and g(x). They are in the same x range (say -30 to 30). f(x) may have some sharp peaks or smooth peaks and valleys. g(x) may have the same peaks and valleys. If so I want a measure on how well these features coincide without visual inspection. I have tried to solve this problem in the following way.

  1. Normalize both functions by dividing each data point by the total area of the function. Now the area of the normalized function is 1.0
  2. At each x get the minimum value out of f(x) and g(x). This will give me a new function that is basically the overlapping area between f(x) and g(x).
  3. When I integrate the resulting function of step 2 I get the total overlapping area out of 1.0

However this does not tell me whether the peaks and valleys coincide or not. I am not sure if this can be done but if someone knows a method I would appreciate your help.

==EDIT== For clarification I have included an image.

Sample curves

The difference between the two curves (black and blue) may not be the same but will have complementing shapes.

Background: The functions are projected density of states (PDOS) of atomic orbitals of a compound. So I have states for s,p,d orbitals. I want to determine whether the material has s-p, p-d or d-d hybridizations (orbital mixing). The only data I have is the PDOS. If say the PDOS of s orbital (function f(x)) has the peaks and valleys as at the same energies (x values) of the PDOS of p orbital (function g(x)) then there is s-p mixing in that material.

share|improve this question
1  
Maybe take it to mathoverflow.net ? –  Euphoric Nov 22 '13 at 21:19
1  
I wonder if the digital audio folks have similar problems? –  Dan Pichelman Nov 22 '13 at 21:26
    
Thanks Euphoric, I will ask the question at mathoverflow.net as well –  laalee Nov 22 '13 at 21:30
    
@laalee Please don't ask your question on more than one site on the Stack Exchange network. Also Math Overflow is Research-level math. Math Stack Exchange is non-Research level. I can migrate this to Math or somewhere else if you want. –  World Engineer Nov 22 '13 at 21:43
    
I apologize. I tried to delete it in mathoverflow but I could not find a way. I would appreciate if you could delete it. Thanks –  laalee Nov 22 '13 at 21:56
show 1 more comment

5 Answers

This is just "off the top of my head", so I could be misunderstanding the problem entirely, but maybe you could apply a root-mean-square distance (RMSD) to the functions. If you're just interested in the peaks and valleys, then apply it to areas around those peaks and valley (that is, for some x +/- some epsilon where the derivative of either function is zero). If the RMSD of that range is near zero, then you have a good match, I think.

share|improve this answer
    
Thanks dbc60. I will try your solution –  laalee Nov 22 '13 at 21:56
    
This considers difference between values,which may not be zero although the shapes are similar. –  laalee Nov 22 '13 at 22:10
add comment

This is a common and often difficult problem in analytical chemistry, physics, spectroscopy, etc. The approaches used can range from simple RMSD comparison to very sophisticated methods. If the task isn't easy to do by visual inspection (humans are exquisitely developed for feature recognition), then it will likely be hard to do computationally.

One approach is to try to remove the "baselines" so that the functions are zero-valued except where there are peak or valley features. This is best done with curve fitting using a low-order polynomial, or, better yet, a more appropriate principled model of what the baseline can and should look like. If the peaks are very sharp, you can simply smooth the function and subtract the smoothed function from the original function.

After removing the baseline, you can normalize and generate residuals or do RMSD (simple approachs) or try to detect peak/valley features by fitting a gaussian (or whatever model is appropriate) to eachfeature you seek. If you are able to fit the peaks, then you can compare the peak locations and half-widths.

Take a look at SciPy if you know Python. Good luck.

share|improve this answer
    
Thanks for your answer. However I am not clear on how to find a baseline. Each case will have a different function which I cannot predict ahead of time. –  laalee Nov 22 '13 at 22:29
add comment

Brute force: find out smallest non-zero float value with this value as step, go through the whole domain and check if values are equal?

== EDIT ==

Hmmm... If by "the same shape" you mean g(x)=c*f(x), this solution should be modified - for each element of domain you calculate f(x)/g(x) and check whether result is the same for each point (of course, if g(x) == 0, then you check if f(x) == 0, you're not trying to divide).

If "the same shape" mean "local optimums and bending points are the same"... Well, find local optimums and bending points for f(x) and g(x) (as sets of domain elements) and check, if those sets are equal.

Third option: f(x) = g(x)+c. Just check if each element of domain has the same difference f(x)-g(x). It is almost identical as first case, but instead of division you have difference.

== YET ANOTHER EDIT ==

Well... Second approach from edit above may be useful. Also, you can merge it with comparing sign of first dervative (not symbolic, but calculated as df(x) = f(x) - f(x-step) ). If both functions have the same sign of derivative in the whole domain, check optimas and bending points, just to be sure. I'd say this conditions should be enough to do what you need.

share|improve this answer
    
Thanks Filip for your reply. But the functions may not have equal values but have the same shape. –  laalee Nov 22 '13 at 21:26
    
I move this comment to answer as edit. Check it out. –  FilipMalczak Nov 22 '13 at 21:34
    
Thanks Filip for your answer. I have added an image to clarify my problem. –  laalee Nov 22 '13 at 21:57
    
Thanks Filip I will try your suggestions. –  laalee Nov 23 '13 at 6:27
add comment

As I undesrtand it, the information you are looking for is conveyed by the “tableau des variations” of the function—I am very sorry that I do not know the english name for this!

This table is associated to a differentiable function f and you construct it by finding the roots of f' and determine the sign of f' on each interval between these zeroes.

So, if the zeroes of f' and g' more or less coincide and the signs of theses functions agree, they will have a similar profile.

The first thing I would try to program would be:

  1. Select a small ε
  2. Draw randomly a large number N of points x[i] in the interval where the functions are defined.

  3. For each node, compute the differences F[i] = f(x[i] + ε) - f(x[i] - ε) and G[i] = g(x[i] + ε) - g(x[i] - ε).

  4. If at each node, F[i] and G[i] are both smaller than ε² OR have both the same sign, conclude that the two functions nearly have the same profile.

Does it work?

share|improve this answer
    
Thanks michipili for your insightful answer. Currently I am trying to meet a deadline. But I will implement this as soon as I can and let you know –  laalee Nov 25 '13 at 20:55
add comment

how well these features coincide without visual inspection.

Probably the most straightforward way is to calculate Pearson's correlation coefficient. That is, use your f(x) as X and g(x) as Y. Effectively "plot g(x) as function of f(x) and see how well it forms a straight line".

Correlation coefficient is popular because it's easy to calculate, and is often justified merely by waving hands. It may be a good initial approximation for some uses, but is definitely not a panacea.

To get better results in real-world applications, you need to understand what's going on in the data, i.e. the process that generates the data. Often there's some sort of background, and the interesting features ride on top of that background. If you throw the whole data into a black box, you may end up comparing mostly the backgrounds: the black box doesn't know which part of the data is the interesting part. So, to get better results, it's often a good idea to remove the backgrounds somehow, and then compare what you have left. Fitting lines or curves or averages and subtracting or dividing by them, low-, band- or highpass filtering, feeding the data through some nonlinear function... you name it.

There's definitely no single right answer. You'll get as many different results as you try methods. But, some of the results are better than some ofters. Theoretical reasoning may help getting started in the right direction, but how to set parameters and fine-tune your method, can ultimately be found only by trying them out and comparing the real-world results.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.